從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
- clay.jz.huang@gmail.com
參考書目
4會員
8內容數
本專題將以Python程式語言來實作資料結構，依序從陣列(Array)、堆疊(Stack)、佇列(Queue)、樹(Tree)到圖(Graph)，透過不同方式來建立資料結構，並討論部分細節如：建構難度、記憶體空間、效率等等。
留言0
查看全部
你可能也想看
Google News 追蹤
/
大家現在出門買東西還會帶錢包嗎
鴨鴨發現自己好像快一個禮拜沒帶錢包出門
還是可以天天買滿買好回家(?
因此為了記錄手機消費跟各種紅利優惠
鴨鴨都會特別注意銀行的App好不好用！
像是介面設計就是會很在意的地方
很多銀行通常會為了要滿足不同客群
會推出很多App讓使用者下載
每次
在資料結構與演算法裡，
最簡單的線性資料結構除了list之外就是linked list鏈結串列了。
Linked list又有分為單向Singly linked list 和雙向Doubly linked list
在這篇文章，會從最基礎的Singly linked list開始講起。
定義
Array可以說是各種語言除了基本型別之外，最常用的資料型別與容器之一了。
Array 這種連續格子狀的資料結構，在Python要怎麼表達呢?
建立一個空的陣列
最簡單也最直接的寫法就是
array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
NumPy（Numeric Python）是Python中用於科學計算的核心庫之一。它提供了高性能的多維陣列對象（即ndarray）以及用於處理這些陣列的各種函數和工具。
在NumPy中，有幾個常用的指令可以用來創建陣列
這篇文章，會帶著大家複習以前學過的配對模型與Stack框架，
並且以括弧配對的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
首先，Stack本身具有Last-In First-Out 後進先出的特質。
再根據題目所需要的資訊利用Stack去儲存索引
這篇文章，會帶著大家複習以前學過的遞回框架，
並且鏈結串列的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
遞回框架
尋找共通模式(common pattern)，對應到演算法的General case
確立初始條件(initial conditio
在Python中，queue是一個非常有用的模块。
它提供了多種佇列（queue）實現，用於在多線程環境中安全地交換信息或者數據。
佇列（queue）是一種先進先出（FIFO）的數據結構，允許在佇列的一端插入元素，另一端取出元素。(FIFO 是First In, First Out 的縮寫)
本文介紹了Python中zip與enumerate函式的使用，以及它們的語法說明和程式範例。zip函式允許同時迭代多個可迭代對象，這使得程式碼更簡潔；而enumerate函式則在迭代時，提供元素的索引，使得實用工具，尤其是當需要追蹤元素的位置時。
本文介紹了串列運算式的應用，以及與Lambda匿名函式方法的比較，並提供了程式範例。串列運算式提供了一種簡潔的語法，用於創建、轉換和過濾列表。lambda函式用於創建匿名函式，通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。
列表（List）和元組（Tuple）都是 Python 中用來存儲集合元素的數據結構，兩者看起來很像，在初學時很容易搞混，所以觀念要建立好。
可以把列表（List）和元組（Tuple）想像成是一個容器，什麼元素都可以塞
/
大家現在出門買東西還會帶錢包嗎
鴨鴨發現自己好像快一個禮拜沒帶錢包出門
還是可以天天買滿買好回家(?
因此為了記錄手機消費跟各種紅利優惠
鴨鴨都會特別注意銀行的App好不好用！
像是介面設計就是會很在意的地方
很多銀行通常會為了要滿足不同客群
會推出很多App讓使用者下載
每次
在資料結構與演算法裡，
最簡單的線性資料結構除了list之外就是linked list鏈結串列了。
Linked list又有分為單向Singly linked list 和雙向Doubly linked list
在這篇文章，會從最基礎的Singly linked list開始講起。
定義
Array可以說是各種語言除了基本型別之外，最常用的資料型別與容器之一了。
Array 這種連續格子狀的資料結構，在Python要怎麼表達呢?
建立一個空的陣列
最簡單也最直接的寫法就是
array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
NumPy（Numeric Python）是Python中用於科學計算的核心庫之一。它提供了高性能的多維陣列對象（即ndarray）以及用於處理這些陣列的各種函數和工具。
在NumPy中，有幾個常用的指令可以用來創建陣列
這篇文章，會帶著大家複習以前學過的配對模型與Stack框架，
並且以括弧配對的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
首先，Stack本身具有Last-In First-Out 後進先出的特質。
再根據題目所需要的資訊利用Stack去儲存索引
這篇文章，會帶著大家複習以前學過的遞回框架，
並且鏈結串列的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
遞回框架
尋找共通模式(common pattern)，對應到演算法的General case
確立初始條件(initial conditio
在Python中，queue是一個非常有用的模块。
它提供了多種佇列（queue）實現，用於在多線程環境中安全地交換信息或者數據。
佇列（queue）是一種先進先出（FIFO）的數據結構，允許在佇列的一端插入元素，另一端取出元素。(FIFO 是First In, First Out 的縮寫)
本文介紹了Python中zip與enumerate函式的使用，以及它們的語法說明和程式範例。zip函式允許同時迭代多個可迭代對象，這使得程式碼更簡潔；而enumerate函式則在迭代時，提供元素的索引，使得實用工具，尤其是當需要追蹤元素的位置時。
本文介紹了串列運算式的應用，以及與Lambda匿名函式方法的比較，並提供了程式範例。串列運算式提供了一種簡潔的語法，用於創建、轉換和過濾列表。lambda函式用於創建匿名函式，通常用於簡單的操作。建議在比較複雜的情況下使用一般for迴圈加if來表示。
列表（List）和元組（Tuple）都是 Python 中用來存儲集合元素的數據結構，兩者看起來很像，在初學時很容易搞混，所以觀念要建立好。
可以把列表（List）和元組（Tuple）想像成是一個容器，什麼元素都可以塞