棧
一、棧的定義
棧是(stack)是限定盡在表尾進行插入和刪除操作的線性表。
棧又稱為后進先出（Last In First Out）的線性表，簡稱LIFO結構。
二、進棧出棧變化形式
注意： 并不是最新進棧的元素只能最后處棧。如，我們現在有三個元素一次進棧，次序會有以下5種：
1. 1、2、2進，再3、2、1出，出棧次序為321；
2. 1進，1出，2進，2出，3進，3出，出棧次序為123；
3. 1進，2進，2出，1出，3進，3出，出棧次序為213；
4. 1進，1出，2進，3進，3出，2出，出棧次序為132；
5. 1進，2進，2出，3進，3出，1出，出棧次序為231。
三、棧的順序存儲結構及實現
（一）棧的順序存儲結構
棧是線性表的特例，棧的順序存儲結構也是線性表存儲結構的簡化。線性表是用數組實現的，用下標為0的那一端作為棧底使棧變化最小。
我們定義一個top變量來指示棧頂元素在數組中的位置。若存儲棧的 長度為StackSize，則棧頂位置top必須小于StackSize。當棧存在一個元素時，top=0.因此，通常把空棧的判定條件定位top=-1.
進棧：push；出棧：pop。（就像子彈的壓和彈）。
沒有涉及循環，兩者的時間復雜度均為1.
兩棧共享空間：兩個類型相同的棧，則可以共享存儲空間。讓一個棧的棧底為數組的始端，即下標為0處，另一個棧為數組的末端，即下標為數組長度n-1處。這樣，兩個棧如果增加元素，就是兩端點向中間延伸。兩個棧見面之時，也就是兩個棧指針相差1，即top1+1==top2為棧滿。
（二）棧的鏈式存儲結構
棧的鏈式存儲結構，簡稱為鏈棧。
鏈棧的棧頂和單鏈表的頭指針重合，不需要頭結點。
對于鏈棧來說，不存在棧滿的情況，除非內存已經沒有可以使用的空間。如果真的發生，就是操作系統已經面臨死機崩潰的情況，而不是這個鏈棧是否真的溢出。
對于空棧來說，鏈表原定義是頭指針指向空，那么鏈棧的空其實就是top=NULL的時候。
對比順序棧和鏈棧，它們在時間復雜度上是一樣的，均為O(1)。對于空間性能，順序棧要事先確定一個固定的長度，可能會存在內存空間浪費的問題，但它的優勢是存取時定位很方便，而鏈棧則要求每個元素都有指針域，這同時也增加了一定的內存開銷，但對于棧的長度無限制。所以它們的區別和線性表中討論的一樣，如果棧的使用過程中元素變化不可預料，有時候很小，有時候很大，那么最好是用鏈棧，如果它們的變化在可控范圍內，建議使用順序棧會更好一些。
四、棧的作用
有的人可能會問，用數組或鏈表直接實現功能不就行了嗎？為什么還要引入棧這個數據結構呢？
其實這和我們明明有兩只腳可以走路，干嘛還要乘汽車、火車、飛機一樣。理論上，陸地上的任何地方，你都是可以用雙腳走到的，可那需要多長時間和精力呢？我們更關注的是到達而不是如何去的問題。
棧的引入簡化了程序設計的問題，劃分了不同關注層次，使得思考范圍縮小，更加聚焦于我們要解決的核心問題。反之，像數組等，因為要分散精力去考慮數組下標的增減問題，反而掩蓋了問題的本質。
所以，現在的許多高級語言，比如Java，C#等都有對棧結構的封裝，你可以不關注它的實現細節，就可以直接使用Stack的push和pop方法，非常方便。
五、棧的應用
（一） 遞歸
斐波那契數列
（二）四則運算表達式求值
后綴（逆波蘭）表示法：從左到右遍歷表達式的每個數字和符號，遇到是數字就進棧，遇到是符號，就將處于棧頂兩個數字出棧，進行運算，運算結果進棧，一直到最終獲得結果。
中綴表示法：從左到右遍歷中綴表達式的每個數字和符號，若是數字就輸出，即成為中綴表達式的一部分；若是符號，則判斷其與棧頂符號的優先級，是右括號有優先級不高于棧頂符號（乘除有限加減）則棧頂元素依次出棧并輸出，并將當前符號進棧，直到最終輸出后綴表達式為止。
隊列
一、隊列定義
隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
隊列是一種先進先出（First In First Out）的線性表，簡稱FIFO。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。
二、隊列的抽象數據類型
同樣是線性表，隊列也有類似線性表的各種操作，不同的就是插入數據只能在隊尾進行，刪除數據只能在隊頭進行。
三、循環隊列
隊列也有線性表的兩種存儲方式：順序存儲和鏈式存儲。
入隊操作是在隊尾增加一個元素，時間復雜度為O(1)。但是，出隊時，如果規定隊列中的元素都放在前n個位置，則第一個元素出隊后，后面的元素都要向前移動，以保證對頭不為空，也就是下標為0的位置不為空，此時時間復雜度為O(n)。
但是，我們可以想，如果沒有隊列的元素都必須放在前n個位置的規定，出隊的性能就會大大增加。于是，我們因為兩個指針，front指向對頭元素，rear指針指向隊尾的下一個元素，當front==rear，隊列為空。這樣，當出隊時，只需移動front指針即可。但是，這樣也會有一個問題，一個隊列不可能只有出隊，當繼續進行入隊操作致使隊尾已經填滿，rear指針指向隊列外時，繼續入隊就可能產生數組越界的錯誤。但是，由于前面已經進行過出隊操作，所以這個隊列前面會有空位置，這種現象稱為“假溢出”。這里舉個例子，現實生活中，當你上了一輛公交車，發現前面有兩個空位置，但后排的座位都已經滿了。這是，你不會告訴自己，后面沒座了，立馬下車，等待下一輛。我們都不會這么笨，而都會坐在前面的位置。
這時，就引入了循環隊列的概念。循環隊列就是首尾相接的順序存儲結構。
那么，問題又來了，前面提到當front==rear時，隊列為空，但在循環隊列中，這個結論顯然不成立。所以，如何判斷隊列是空還是滿呢？以下給出兩種方法：
1. 設置一個標志變量flag，當front==rear，且flag=0時隊列為空，當front==rear，且flag=1時隊列滿。
2. 當隊列空時，條件就是front=rear，當隊列滿時，我們修改條件，保留一個元素空間。也就是說，隊列滿時，數組中還有一個空閑單元。
我們來重點討論第二種方法，由于rear可能比front大，也可能比front小，所以它們只相差一個位置時就是滿的情況，但也可能是相差整整一圈。所以，若隊列的最大尺寸是QueueSize，那么隊滿的條件是（rear+1）%QueueSize==front（取模%的目的就是為了整合front和rear大小為一個問題）
通用的計算隊列長度的公式為（rear-front+QueueSize）%QueueSize
循環隊列的相關條件和公式：
1. 隊空條件：rear==front
2. 隊滿條件：(rear+1) %QueueSIze==front，其中QueueSize為循環隊列的最大長度
3. 計算隊列長度：（rear-front+QueueSize）%QueueSize
4. 入隊：（rear+1）%QueueSize
5. 出隊：（front+1）%QueueSize
到這里，大家可以發現，但是順序存儲，若不是循環隊列，算法的時間性能是不高的，但循環隊列有面臨著數組可能會溢出的問題，所以我們還需要研究一樣不需要擔心隊列長度的鏈式存儲結構。
四、隊列的鏈式存儲結構及實現
隊列的鏈式存儲結構，其實就是線性表的單鏈表，只不過它只能尾盡頭出而已，稱為鏈隊列。將隊頭指針指向鏈隊列的頭結點，隊尾指針指向終端結點。
空隊列是，front和rear都指向頭結點。
入隊操作：就是在鏈尾插入結點。
出隊操作，就是頭結點的后繼結點出隊，將頭結點的后繼改為它后面的結點，若鏈表除頭結點外只剩一個元素時，則需將rear指向頭結點。
對比循環隊列和鏈隊列，時間上，其實它們基本操作都是常數時間，即都為O(1)的。不過循環隊列是事先申請好空間，使用期間不釋放，而對于鏈隊列，每次申請和釋放結點也會存在一些時間開銷，如果入隊出隊頻繁，則兩者還是存在細微差異。對于空間上來說，循環隊列不存在這個問題，盡管它需要一個指針域，會產生一些空間上的開銷，但也可以接受。所以在空間上，鏈隊列更加靈活。
總的來說，在可以確定隊列長度最大值的情況下，建議使用循環隊列，如果無法預估隊列長度，則用鏈隊列。
