堆疊在日常生活中的應用俯拾皆是,像是搭電梯、堆積木、疊衣服…等等,對於我們來說這些事情非常直覺,所以其實不太容易察覺到,而以概念來說堆疊不難理解,只是它跟陣列還有指標息息相關,如果還不熟悉的話記得回去複習一下!
思考時間:大家來想想看,上述這些事情有什麼共同點嗎?
答案會在後面的介紹中揭曉 。
現在,就先開始介紹堆疊 (Stack)!
堆疊 (Stack) 是什麼?
Stack 是一個有序的串列,在 Stack 上的所有操作都會在同一個端點進行,而這個端點通常會被稱為 – top 。
回想一下上面的問題,不知道大家想到了什麼?
發現了嗎~上述的事情都有一個特性 – 後進先出 (LIFO, Last-In-First-Out)
舉個例子:
搭電梯的時候,最後進來的人通常會站在最外面,因此如果後面的人想要出電梯,一定要最後進來的人先出去,這就是後進先出的概念。
也就是 Stack 最大的特性!

p.s. 頂端稱為top,底部稱為bottom!
Stack的基礎 – 區域變數(以C語言為例)
重要概念#1:全域變數 v.s. 區域變數
- 全域變數 (global variable) – 在編譯階段配置記憶體空間。
- 區域變數 (local variable) – 在執行階段進入function之後才配置記憶體空間。
*** 區域變數在function結束執行之後,記憶體空間也就隨之釋放 ***
重要概念#2:function的參數屬於區域變數
C語言在呼叫function的時候,會需要處理function的參數和其中的區域變數,這時候就會將變數和參數都用Stack儲存,在程式呼叫function之前,會把區域變數、參數、程式返回位址全都存入Stack,等到需要的時候,再從Stack把值一一取出來,回復到原來的狀態。
Stack 實作方法?
方式#1:利用陣列
#define MAX_STACK_SIZE 50
typedef struct {
int age;
char name[10];
} person;
person stack[MAX_STACK_SIZE];
int top = -1;
top 一開始會設為 -1,表示stack為空。
方式#2:利用鏈結串列 (Linked list)
這邊先附上程式碼,關於鏈結串列 (Linked list) 的教學我之後會盡快補上!
那時,大家可以先去看看 Linked list 的概念之後,再回來看這段程式碼。
#define MAX_STACKS 10
typedef struct {
int age;
char name[10];
} person;
typedef struct stack *stackPointer;
typedef struct stack {
person data;
stackPointer link;
};
stackPointer top[MAX_STACKS];
Stack最常用到的4個function
Function#1:Push (Insert)
目的:將資料放進 Stack 的『最上面』。

void push(person data) {
if (top >= MAX_STACK_SIZE-1)
stackFull();
stack[++top] = data;
}
Function#2:Pop (Delete)
目的:將『最上面』的資料從 Stack 中移除。

void pop() {
if (top == -1)
return stackEmpty();
return stack[top--];
}
p.s. pop其實並沒有真正移除資料,只是將top的值-1,因為之後作push的時候,自然就會將舊的資料蓋過去了。
Function#3:isFull(判斷Stack是否已滿)
int isFull() {
if (top >= MAX_STACK_SIZE-1)
return true;
return false;
}
有發現嗎?上面在push之前,我們先檢查了Stack是不是滿了!
如果滿了,就不能再push。
Function#4:isEmpty(判斷Stack是否已空)
int isEmpty() {
if (top == -1)
return true;
return false;
}
這邊也同樣,在pop前,要先檢查Stack是否為空!
如果空了,就不能pop。
如果Stack已滿,繼續push會發生什麼事呢?
這就會發生非常著名的 Stack Overflow

Stack的廣泛應用
Stack最大的特性是『後進先出』,換句話說就是『儲存先前的資訊』,所以時常會被用來處理需要『回復到先前狀態』的問題,因為最近的資訊會被儲存在最上方,而這類的問題也被稱為Back-Tracking(回溯)Problem。
像是:文書軟體(Word, Excel, Powerpoint, Notion…)中的上一步功能、Google瀏覽器的上一頁功能…等等,就是這個概念!
#1:字串反轉
概念:將字串中的字元,逐一push進去Stack,全部結束後,再pop出來。

#2:老鼠走迷宮
假設:
迷宮共有8個方位可以走,而行走的優先順序是上、下、左、右、右上、右下、左上、左下,行走方式是依照上述八個方向的優先順序嘗試,每走一步,如果是死路,那麼就要透過Stack回溯,直到找出正確的路。

#3:河內塔問題(Tower of Hanoi)
規則:
- 每次只可以移動一個圓盤。
- 不論什麼情況,圓盤必須保持上小下大的原則。
玩法:將A柱上所有的圓盤移到C柱。

當圓盤數=3,示範步驟如下:
step 1
從A柱將1號圓盤移到C柱。
step 2
從A柱將2號圓盤移到B柱。
step 3
從C柱將1號圓盤移到B柱。
step 4
從A柱將3號圓盤移到C柱。
step 5
從B柱將1號圓盤移到A柱。
step 6
從B柱將2號圓盤移到C柱。
step 7
從A柱將1號圓盤移到C柱。
Done!
實際操作看看吧!
#4:function的呼叫與返回

當Program A呼叫Program B的時候,會將返回位址a存進Stack中,當在Program B呼叫Program C的時候,會再將返回位址b存進Stack中,當Program C結束執行的時候,就會從Stack取初返回位址的值,因此就會先回到b,再回到a。
總結
以上就是堆疊 (Stack) 的基本觀念跟應用,希望大家理解之後能夠去思考如何靈活運用,因為Stack只是工具,而能夠使用工具來達成目的才是最重要的!
對文章有任何問題的話,都歡迎在下面留言讓我知道哦!
By Hani
太難了啦大學唯一被當過的一科
哈哈哈哈,看來我太晚創立Hani CS Daily了!
一個簡單堆疊得背後,原來有這麼深奧的邏輯與應用,內容也寫得很詳盡,很好的文章。
謝謝你,希望對你有幫助!
對於程式語言完全沒有涉略的我
都可以因為你的圖示而讓我比較知道這些是用在哪裡
非常用心!
謝謝版主細心分享。
圖真的畫了很久XDD,對你有幫助我很開心!
這對於程式有興趣的人,真的是很好的資訊欸! 感謝分享ㄋㄟ~~
謝謝你~
剛好最近在自學程式語言,看完文章的介紹後,真的會對函數的應用更加上手
謝謝你~如果有想要看的主題也可以跟我說喔!
大學有學過程式語言過,這對有在學語言的會有幫助,謝站長分享
程式語言設計是一個好深好深的技能
版主能夠整理得這麼淺顯易懂真的很威!
通常學習一個簡單的語言,大概需要花費多少時間才能有個基礎呢?
Hi Brian,其實程式語言的學習非常的深且廣,而語言本身只是工具,主要還是要看你想要透過語言來達成什麼目的。
如果只是想要了解一個語言的基礎,其實不會花非常多的時間!