從Python認識資料結構(五)．堆疊
閱讀時間約 3 分鐘
大家好，本章會介紹以Python語言來實作第二種資料結構 - 堆疊(Stack)，堆疊的概念很簡單，就如同疊盤子，通常會依序一個一個往上疊高，如果要取出時，也會拿最上面的那個盤子，這樣的形態我們將它命名為後進先出(Last In First Out)，最早被放置的盤子放在最底下，越晚被放置的盤子則越靠上，而且會被優先拿取。
5-1、堆疊的基本操作
在Python語言中，堆疊的實作會與陣列相同，分別可以以靜態結構-串列(List)和動態結構 - 鏈結串列(Linked List)來建構。首先我們先來介紹堆疊的幾個基本操作。
- 創建(create)：顧名思義，建立一個新的空堆疊。
- 新增(push)：將資料放入堆疊中，該資料會成為最頂部的資料。
- 拿取(pop)：將最頂部的資料移出。
- 是否為空堆疊(isEmpty)：用來檢查某堆疊是否為空。
- 是否為滿堆疊(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
- [email protected]
參考書目
留言0
查看全部