### 6.5.2 堆棧 堆棧（stack）也是一種數據集合體，其中的數據構成一種具有“后進先出（LIFO）”性 質的數據結構，即最后加入堆棧的數據總是首先取出。現實中堆棧的例子俯拾皆是，例如碗櫥里的一摞碗、紙箱里的一摞書、彈夾中的子彈等等（圖 6.10），他們共同的特點是先放進 去的東西墊底，最后放進去的東西在頂上，而取東西的順序正好相反。  圖 6.10 現實中的堆棧例子 如果忽略各種具體堆棧中無關緊要的成分，如所堆放的東西（碗、書、子彈）、容器（紙箱、碗櫥、彈夾）和放入/取出的具體實現（人工、機械），那么我們可以抽象地定義堆棧。 所謂堆棧，是以如下兩個操作進行處理的數據結構： + push(x)：在堆棧頂部推入一個新數據 x，x 即成為新的棧頂元素； + pop()：從堆棧中取出棧頂元素，顯然被取出的元素只能是最后加入堆棧的元素。 為了完善這兩個操作，還需提供一些輔助操作，如： + isFull()：檢查堆棧是否已滿。如果堆棧具有固定大小，那么滿了之后是無法執行 push()的； + isEmpty()：檢查堆棧是否為空。如果堆棧是空的，那么 pop()操作將出錯。 此前介紹的數據類型大多是具體的，即它們的實現方式是給定的，例如 int 類型是以 4 個字節來表示，字符串類型是特定編碼的字節串等等。而現在我們所討論的堆棧則是抽象數 據類型，因為我們只規定了堆棧的操作方式，并沒有規定操作的具體實現方式。 在具體應用中，可以采用多種不同的方式來實現堆棧這個抽象數據類型。例如，可以采 用列表來實現堆棧。令列表 stack 是存放數據的堆棧，按照堆棧的要求，對 stack 只能執行 push 和 pop 操作，不能像列表那樣可以隨機存取任何一個元素。假設以列表頭為棧底，以 列表尾為棧頂，那么向堆棧中放入元素就只能在尾部添加，Python 列表對象提供的 append 方法正好提供堆棧所需的功能，因此可以用 append 來實現 push()，形如： ``` def push(stack,x): stack.append(x) ``` 另外，Python 列表對象的 pop()方法的功能是取出列表的最后一個元素，恰好符合堆棧的 pop()方法的要求，因此可以這樣實現堆棧 pop 操作： ``` def pop(stack): return stack.pop() ``` 為了防止從空堆棧中取數據的錯誤，我們定義一個檢測堆棧是否為空的函數： ``` def isEmpty(stack): return (stack == []) ``` 利用上述以列表實現堆棧的技術，程序 6.5 首先通過用戶輸入數據創建一個堆棧，然后 再逐個取出堆棧成員。輸出恰好是輸入的逆序，這是由堆棧的 LIFO 性質決定的。可見，利 用堆棧來逆序顯示列表數據是非常容易的。 【程序 6.5】stack.py ``` def push(stack,x): stack.append(x) def pop(stack): return stack.pop() def isEmpty(stack): return (stack == []) def main(): stack = [] print "Pushing..." x = raw_input("Enter a string: ") while x != "": push(stack,x) x = raw_input("Enter a string: ") print "Popping..." while not isEmpty(stack): print pop(stack), main() ``` 下面是程序 6.5 的一次執行情況： ``` Pushing... Enter a string: 1st Enter a string: 2nd Enter a string: 3rd Enter a string: 4th Enter a string: Popping... 4th 3rd 2nd 1st ``` 堆棧在計算機科學中非常有用，一個常見的用例是實現表達式的計算。 讀者都熟悉算術表達式的中綴形式，但在用計算機處理表達式時常將表達式寫成后綴形式，例如“1 + 2”可寫成“1 2 +”、“3 + 4 * 5”可寫成“3 4 5 * +”。后綴形式的表達式可以 利用堆棧來非常方便地求值，算法如下： 1\. 掃描后綴形式的表達式，每次讀一個符號（運算數或者運算符）； 2\. 如果讀到的是運算數，則 push 到堆棧中；如果讀到的是運算符，則從堆棧 pop 兩個運算 數，并執行該運算，然后將運算結果 push 入堆棧； 3\. 重復 1、2，直至到達表達式尾。這時堆棧中應該只剩一個運算數，就是表達式的結果值。 圖 6.11 顯示的是“3 4 5 * +”的計算過程。  圖 6.11 利用堆棧對后綴表達式求值 以上求值部分非常容易實現，但要想對用戶輸入的中綴形式的算術表達式進行求值，還 需要先對輸入進行語法分析，拆分出運算符和運算數，然后改成后綴形式。這部分編程有點 復雜，所以在此我們就不實現這個程序了。有興趣的讀者可以嘗試解決這個問題。