棧

閑聊?

棧是一個線性表

棧的特點是后進先出

然后是一個公式

?比如123要入棧，一共有5種排列組合的出棧

棧的數組實現

這里有兩種情況，，一個是有下標為-1的，一個沒有

代碼不用看，真題不會考

?棧的鏈式存儲結構

L -> 4 ->3 ->2 -> 1

歸并所有的操作都在表頭進行，用鏈表實現

做題區

1

相當簡單，fedc出棧了4次了

2?

?

可以看見，除了它本身取不到，其他都能取到，也就是n-1的取值個數

3

這題目不難，必要陷入題目的陷阱了，?意思是in和out可以隨便取

可以看出來可以判斷出來能不能出棧

過程是一樣的，看看能不能找到出棧，可以判斷

C：一定不同就幽默了，

D：確實可能互為倒序

隊列

閑聊

也是操作受限的線性表

操作特點是先進先出 FIFO

記住這句話，rear有點大病

?入隊的話是從尾部隊列，上面的圖就是當front走到最上面，發現數組中還有空位置，就很浪費，所以就有了循環隊列，就是可以重頭開始

循環隊列

循環隊列是用數組實現的，所以它屬于存儲結構（物理結構），邏輯結構反映不出來是用什么實現的

下面一共會畫4種圖，兄弟們

第一種

front和rear都會指向0

然后假設第一個元素放入A【0】

入隊我們要做的就是尾指針先放后移

就可以發現

第二種

front和rear都會指向倒數倒數第一個

那就只能先移動在放了

尾指針終于指向隊尾了

頭指針就很屎了，在隊頭前一個

第三種

頭指針在倒數第一個，尾指針在第一個（圖已分裂！）

肯定是先放后移了

尾指針肯定是隊尾下一個

頭指針是隊頭的前一個，永遠是這樣記住，若頭指針移動到下一個元素出棧，那頭指針仍然是隊頭的前一個

第四種

隊頭是0，隊尾是倒數第一個

先移再放不多說

尾指針指向隊尾

頭指針指向隊頭，爽了

然后看一下題目就知道該怎么用了

這里就是第四種情況了，選B

判斷隊空隊滿

拿第一個舉例子

后面就是先放再移動，移啊移啊，變成了下面的樣子

就能發現 空是 front == rear

? ? ? ? ? ? ? ? 滿是 front == rear

可以發現居然一樣的，我不能接受！

所以犧牲一個單元

?

就變成了 （rear + 1）% M == front

看題目

?這里頭指向隊首元素，隊尾指向隊尾后一個也是隊頭元素

后面又說最多能容納M-1個，也就是說，他犧牲了一個單元，非常感動

選A

計算元素個數

如果? rear > front? 那rear - front

如果? front出隊，rear又入隊

就變成了?rear <?front? 那就是 rear + n - front

所以，如果要整一個匯總就是

(rear - front + n)%n?

雙端隊列

?輸出受限雙端隊列：就是2邊能隨便進，但輸出受限了

??輸入受限雙端隊列：就是2邊能隨便輸出，但輸入受限了

做個題

只讓從一端出，也就是圖這個樣子，最后只要能入成選項的樣子就可以了，因為最后直接順序輸出就結束了

C選項無法入成我想要的樣子，所以錯

一模一樣的題

?選D