從Python認識資料結構(五)．堆疊

5-1、堆疊的基本操作

在Python語言中，堆疊的實作會與陣列相同，分別可以以靜態結構-串列(List)和動態結構 - 鏈結串列(Linked List)來建構。首先我們先來介紹堆疊的幾個基本操作。

1. 創建(create)：顧名思義，建立一個新的空堆疊。
2. 新增(push)：將資料放入堆疊中，該資料會成為最頂部的資料。
3. 拿取(pop)：將最頂部的資料移出。
4. 是否為空堆疊(isEmpty)：用來檢查某堆疊是否為空。
5. 是否為滿堆疊(isFull)：用來檢查某堆疊是否為滿。

---

5-2、以串列方式來建立堆疊

以串列來建立堆疊的方式十分簡單，首先設計一個變數用來判斷目前堆疊內的資料儲存高度，我們選用top這個變數來儲存，並在創建新堆疊時將top變數賦值0，代表目前沒有任何資料。如同我們在陣列實作時的情況，若所需儲存空間未知，透過串列方式所建立的堆疊會造成記憶體空間的浪費。為了讓讀者們更了解堆疊的內容，我們直接定義幾種不同的函數來實作堆疊。

• 是否為滿堆疊(isFull)：為了避免資料新增時超出堆疊上限，我們必須先判斷當前堆疊是否已為滿堆疊，做法為判斷top和max之間的關係，如果top大於max，代表堆疊已滿，此時便不可再加入任何資料。
• 新增(push)：新增資料前要先判斷完是否為滿堆疊，若否，則可將資料放入堆疊中。做法為list[top]=欲新增的元素，新增完成後要將頂端往上疊，所以還要再讓top=top+1。
• 是否為空堆疊(isEmpty)：為了避免拿取資料時發生錯誤，我們也要避免在空堆疊中發生拿取的命令，故我們判斷當前的堆疊情況，此時我們同樣可以運用上面提到的top變數，當top等於0時，代表當前沒有任何資料，也就是堆疊為空。
• 拿取(push)：拿取資料前同樣要判斷堆疊是否為空，若否，則可取出資料。與新增做法雷同，拿取的話可用Python內建的語法pop，做法為list.pop()，最後再將top=top-1。

---

5-3、以鏈結串列來建立堆疊

同樣的，若要以鏈結串列的方式來建立堆疊，我們一樣要和實作上述的功能，不同的是，因為我們採用動態結構，不用事先給定記憶體空間，所以無需設計isFull這個函數，因為鏈結串列中並不會有滿堆疊的情況發生。

我們同樣設計top變數來儲存堆疊狀況，預設None代表目前沒有任何資料節點，當有新資料進入時，將新資料的next屬性連接到top，完成新資料堆到頂部的設置，接著再把top改為新節點位置，如此一來便完成了push的功能。

pop同理，我們只須將top改為top的next屬性指向的節點位置，也就是將top下移一層，此時雖然我們沒有刪除最上層的節點，但也透過刻意丟失的技巧將最頂部節點移除，完成pop的功能。

以上部分就是Python中建立堆疊的方式介紹，因為堆疊的實作與陣列很像，部分細節就不再贅述，下一節我們會介紹堆疊的應用，有任何問題歡迎寄信至我的信箱或於底下留言和我討論。

• Institute of Education, NYCU
• clay.jz.huang@gmail.com

---

參考書目

1. 圖解資料結構 - 使用Python(第二版)
2. 圖書演算法 - 使用Python
3. Python3 物件導向程式設計 第二版
4. 精通Python (第二版)