從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]
參考書目
4會員
8內容數
本專題將以Python程式語言來實作資料結構，依序從陣列(Array)、堆疊(Stack)、佇列(Queue)、樹(Tree)到圖(Graph)，透過不同方式來建立資料結構，並討論部分細節如：建構難度、記憶體空間、效率等等。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Faker昨天真的太扯了，中國主播王多多點評的話更是精妙，分享給各位
王多多的點評
「Faker是我們的處境，他是LPL永遠繞不開的一個人和話題，所以我們特別渴望在決賽跟他相遇，去直面我們的處境。
我們曾經稱他為最高的山，最長的河，以為山海就是盡頭，可是Faker用他28歲的年齡...
在程式中，了解資料型態是相當重要的。
為什麽？
因為許多error，常常都是因為資料型態不正確所導致的。
舉個例子，在python中：
a = 1 + 2
print(a)
結果就是3
a = = "1"+"2"
print(a)
結果就是12
是不是差很多？
所以今天我來介
本文詳細解說了 Python print() 函數的各種隱藏語法，包括 value、sep、end、file 和 flush。作者以清晰的範例和解說，讓從未接觸程式語言的人也能夠理解。而最後提到了訂閱房間的付費方式，並歡迎大家訂閱。文章內容較為詳細，提供了豐富的資訊。
我從追星AKB48開始燃起了學語言的熱情。
又在研究Python的程式語言原理，撬開了語言學的大門。
在21世紀的技術浪潮中，「Python」不僅是程式設計的代表性語言，更是從初學者到資深工程師的共同選擇。除了在網頁開發、大數據和AI等專業領域中的應用，Python在全球的開發者社群中也建立了一個繁榮的生態系統，推動技術進步。然而，背後還隱藏著許多鮮為人知的故事和趣味，等待著我們去探索與發掘。
馬克•庫班（NBA獨行俠隊老闆，億萬富翁）說過：「人工智慧、深度學習和機器學習，不論你現在是否能夠理解這些概念，你都應該學習。否則三年內，你就會像被滅絕的恐龍一樣被社會淘汰。現在不開始，以後就來不及了。」
最近因為眼睛出了問題，再加上政策提案等等大事件交雜而停更了好一陣子。這篇會提到的漫畫跟遊戲作品幾部：咒術迴戰、進擊的巨人、鬼滅之刃、怪獸8號、巫師（狩魔人）
俗話說「養樹護根，養人護足。」足部是我們步行走路時的唯一接觸點，足部不穩，上面的身體也會跟著歪。在我們治療理念裡，最重視的就是「脊」與「足」。
在前幾篇文章中，透過許多生活例子，如：經過幾分後，計算火鍋湯溫度對時間的平均變化率；又或者計算植物的平均生長速度，讓讀者了解，斜率是由兩個變量相除計算而來，對於「斜率」有深刻了解。此篇文章則將帶領讀者，由生活中的時間間隔，進一步思考「瞬時」與「平均」變化率之間的差異。
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Faker昨天真的太扯了，中國主播王多多點評的話更是精妙，分享給各位
王多多的點評
「Faker是我們的處境，他是LPL永遠繞不開的一個人和話題，所以我們特別渴望在決賽跟他相遇，去直面我們的處境。
我們曾經稱他為最高的山，最長的河，以為山海就是盡頭，可是Faker用他28歲的年齡...
在程式中，了解資料型態是相當重要的。
為什麽？
因為許多error，常常都是因為資料型態不正確所導致的。
舉個例子，在python中：
a = 1 + 2
print(a)
結果就是3
a = = "1"+"2"
print(a)
結果就是12
是不是差很多？
所以今天我來介
本文詳細解說了 Python print() 函數的各種隱藏語法，包括 value、sep、end、file 和 flush。作者以清晰的範例和解說，讓從未接觸程式語言的人也能夠理解。而最後提到了訂閱房間的付費方式，並歡迎大家訂閱。文章內容較為詳細，提供了豐富的資訊。
我從追星AKB48開始燃起了學語言的熱情。
又在研究Python的程式語言原理，撬開了語言學的大門。
在21世紀的技術浪潮中，「Python」不僅是程式設計的代表性語言，更是從初學者到資深工程師的共同選擇。除了在網頁開發、大數據和AI等專業領域中的應用，Python在全球的開發者社群中也建立了一個繁榮的生態系統，推動技術進步。然而，背後還隱藏著許多鮮為人知的故事和趣味，等待著我們去探索與發掘。
馬克•庫班（NBA獨行俠隊老闆，億萬富翁）說過：「人工智慧、深度學習和機器學習，不論你現在是否能夠理解這些概念，你都應該學習。否則三年內，你就會像被滅絕的恐龍一樣被社會淘汰。現在不開始，以後就來不及了。」
最近因為眼睛出了問題，再加上政策提案等等大事件交雜而停更了好一陣子。這篇會提到的漫畫跟遊戲作品幾部：咒術迴戰、進擊的巨人、鬼滅之刃、怪獸8號、巫師（狩魔人）
俗話說「養樹護根，養人護足。」足部是我們步行走路時的唯一接觸點，足部不穩，上面的身體也會跟著歪。在我們治療理念裡，最重視的就是「脊」與「足」。
在前幾篇文章中，透過許多生活例子，如：經過幾分後，計算火鍋湯溫度對時間的平均變化率；又或者計算植物的平均生長速度，讓讀者了解，斜率是由兩個變量相除計算而來，對於「斜率」有深刻了解。此篇文章則將帶領讀者，由生活中的時間間隔，進一步思考「瞬時」與「平均」變化率之間的差異。