一、棧的定義
棧（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）。