### 一、棧的定義 棧（stack）是限定盡在表尾進行插入和刪除操作的**線性表**。 我們把允許插入和刪除的一端成為棧頂（top），另一端成為棧底（bottom），不含任何數據元素的棧稱為空棧。棧又稱為后進先出（LIFO)的線性表。 圖示出棧入棧操作：  ### 二、棧的抽象數據類型 圖示棧的各項操作：  由于棧本身就是一個線性表，那么上一章我們討論了線性表的順序存儲和鏈式存儲，對于棧來說也是同樣適用的。 ### 三、棧的順序存儲結構及實現 來看一下棧的結構定義：  若存儲棧的長度為StackSize,則棧頂位置top必須小于StackSize。當棧存在一個元素時，top等于0，因此常把空棧的判定條件定位top等于-1。 看一下示意圖：  下面看一下push操作的代碼：  出棧pop，代碼如下：  兩者都沒有涉及到任何循環語句，因此時間復雜度均為O（1）。 ### 四、棧的鏈式存儲結構及實現 棧的鏈式存儲結構，簡稱鏈棧。 鏈棧的結構代碼如下：  進棧操作：    出棧操作：   上述操作也不包含循環，因此時間復雜度都是O（1）。 對于順序棧和鏈棧的選擇：如果棧的使用過程中元素變化不可預料，有時很小，有時非常大，那么最好用鏈棧，反之，如果它的變化在可控范圍內，建議使用順序棧會更好些。 ### 五、棧的應用-遞歸 遞歸的最經典例子：（斐波那契額數列）  代碼如下：  遞歸的定義：我們把一個直接調用自己或通過一系列的調用語句間接地調用自己得函數，稱為遞歸函數。 遞歸程序最可怕的就是陷入永不結束的無窮遞歸中，所以，每個遞歸定義必須至少有一個條件，滿足時遞歸不再進行，即不再引用自身而是返回值退出。 ### 六、棧的應用-四則運算表達式求值 我們介紹一種不需要括號的后綴表達法，我們把它稱為逆波蘭（RPN）。 我們來看一個例子：對于運算:9+(3-1)*3+10/2,其逆波蘭表達式為：9 3 1 - 3 * 10 2 / +??? 這種表達式是反人類的表達式，但是是順計算機的，我們也就忍忍吧！ 計算規則：從左到右遍歷表達式的每個數字和符號，遇到數字就進棧，遇到符號就將處于棧頂的兩個數字出棧，進行計算，將計算結果再入棧，一直重復直到獲取結果。 ### 七、隊列的定義 定義：隊列是只允許在一段進行插入操作，而在另一端進行刪除操作的線性表。 隊列是一種先進先出（FIFO）的線性表。 隊列的抽象數據類型：  循環隊列的定義：我們把隊列的這種頭尾相連的順序存儲結構稱為循環隊列。 判斷隊列滿的條件是：（rear+1)%QueueSize==front 計算隊列長度的公式：（rear-front+QueueSize）%QueueSize 循環隊列的順序存儲結構代碼如下：  循環隊列的初始化代碼如下：  循環隊列求隊列長度代碼如下：   循環隊列的入隊操作代碼如下：  循環隊列的出隊操作代碼如下：  循環隊列面臨著數組可能會溢出的問題，我們還要研究一下不用擔心隊列長度的鏈式存儲結構。 ### 八、隊列的鏈式存儲結構及實現 隊列的鏈式存儲結構，其實就是線性表的單鏈表，只不過它只能尾進頭出而已，我們把它簡稱為鏈隊列。  鏈隊列的結構為：  隊列鏈式存儲結構--入隊操作  代碼如下：  隊列鏈式存儲結構--出隊操作  代碼如下：  總的來說，在可以確定隊列長度最大值的情況下，建議用循環隊列，如果你無法預估隊列的長度時，則用鏈隊列。 ### 九、總結回顧 棧是限定僅在表尾進行插入和刪除操作的線性表。 隊列是只允許在一段進行插入操作，而在另一端進行刪除操作的線性表。 它們均可以使用線性表的順序存儲結構來實現，但都存在著順序存儲的一些弊端。 對于隊列來說，為了避免數組插入和刪除時需要移動數據，于是就引入了循環隊列，使得隊頭和隊尾可以在數組中循環變化。解決了移動數據的時間損耗，使得本來插入和刪除是O（n）的時間復雜度編程了O（1）。