一、棧的定義
後進先出，即後進棧的元素先出棧。
每次進棧的元素都作為新棧頂元素，每次出棧的元素只能是當前棧頂元素。
棧也稱為後進先出表或者先進後出表。
例題：一個棧的進棧序列是a、b、c、d、e，則棧的不可能的輸出序列是（C）。
A.edcba B.decba
C.dceab D.abcde
棧的順序儲存結構及其基本運算演算法實現
順序棧實現
順序棧
順序棧的四要素如下：
① 棧空條件：len(data)==0或者not data。
② 棧滿條件：由於data列表可以動態擴充套件，所以不必考慮棧滿。
順序棧類SqStack
順序棧的基本運算演算法
（1）判斷棧是否為空empty()
（2）進棧push(e)
（3）出棧pop()
（4）取棧頂元素gettop()
順序棧的應用演算法設計示例
設計一個演算法利用順序棧檢查使用者輸入的表示式中括號是否配對（假設表示式中可能含有圓括號、中括號和大括號）。並用相關資料進行測試。
設計一個演算法利用順序棧判斷使用者輸入的字串表示式是否為迴文。並用相關資料進行測試。
用str存放表示式，其中含n個字元。若str的前半部分的反向序列與str的後半部分相同，則是迴文，否則不是迴文。判斷過程如下：
共享棧問題
設有兩個棧S1和S2，它們都採用順序棧儲存，並且共享一個固定容量的儲存區s[0..M-1]，為了儘量利用空間，減少溢位的可能，請設計這兩個棧的儲存方式。
解：為了儘量利用空間，減少溢位的可能，可以讓兩個的棧頂相向即進棧元素迎面增長的儲存方式，為此設定兩個棧的棧頂指標分別為top1和top2（均指向對應棧的棧頂元素）。
棧的鏈式儲存結構及其基本運算演算法實現
初始時只含有一個頭結點head並置head.next為None。這樣鏈棧的四要素如下：
棧空的條件：head.next==None。
由於只有在記憶體溢位才會出現棧滿，通常不考慮這種情況。
元素e進棧操作：將包含該元素的結點s插入作為首結點。
和單鏈表一樣，鏈棧中每個結點的型別LinkNode如下
鏈棧類LinkStack
鏈棧的基本運算演算法
（1）判斷棧是否為空empty()
（2）進棧push(e)
（3）出棧pop()
（4）取棧頂元素gettop()
問題1：在以下幾種儲存結構中，哪個最適合用作鏈棧？
（1）帶頭結點的單鏈表
（2）不帶頭結點的迴圈單鏈表
（3）帶頭結點的雙鏈表
問題2：在一個演算法中需要建立多個棧時可以選用以下三種方案之一，試問這三種方案之間相比各有什麼優缺點？
（1）分別用多個順序儲存空間建立多個獨立的順序棧。
（2）多個棧共享一個順序儲存空間。
（3）分別建立多個獨立的鏈棧。
答：
（1）優點是每個棧僅用一個順序儲存空間時，操作簡單。缺點是分配空間小了，容易產生溢位，分配空間大了，容易造成浪費，各棧不能共享空間。
（2）優點是多個棧僅用一個順序儲存空間，充分利用了儲存空間，只有在整個儲存空間都用完時才會產生溢位。缺點是當棧個數大於等於3時其中一個棧滿時需要向左、右查詢有無空閒單元的過程複雜且十分耗時。
（3）優點是多個鏈棧一般不考慮棧的溢位，採用動態空間分配具有良好的適應性。缺點是棧中元素要以指標相連結，比順序儲存多佔用了儲存空間。
鏈棧的應用演算法設計示例
設計一個演算法利用棧的基本運算將一個整數鏈棧中所有元素逆置。例如鏈棧st中元素從棧底到棧頂為（1，2，3，4），逆置後為（4，3，2，1）。
解：這裡要求利用棧的基本運算來設計算法，所以不能直接採用單鏈表逆置方法。先出棧st中所有元素並儲存在一個數組a中，再將陣列a中所有元素依次進棧。
有一個含1～n的n個整數的序列a，透過一個棧可以產生多種出棧序列，設計一個演算法採用鏈棧判斷序列b（為1～n的某個排列）是否得為一個合適的出棧序列，並用相關資料進行測試。
解：建立一個整型鏈棧st，用i、j分別遍歷a、b序列（初始值均為0），在a序列沒有遍歷完時迴圈：
① 將a[i]進棧，i++。
② 棧不空並且棧頂元素與b[j]相同時迴圈：出棧元素e，j++。
在上述過程結束後，如果棧空返回True表示b序列是a序列的出棧序列，否則返回False表示b序列不是a序列的出棧序列。
棧的綜合應用
求解問題中需要臨時儲存一些資料元素：
先儲存的後處理：棧
先儲存的先處理：佇列
exp求值過程
將表示式exp轉換成字尾表示式postexp。
對該字尾表示式求值。
設計求表示式值的類ExpressClass
字尾表示式postexp求值
使用運算數棧opand
求表示式值的兩個步驟可以合併起來，不必產生字尾表示式：
將所有遇到的運算數進opand棧。
在opor出棧一個運算子op時，從opand中依次出棧兩個運算數a、b，執行c = b op a運算，將c進opand棧。