【資料結構】堆疊 (Stack) 是什麼？３張圖馬上搞懂

堆疊在日常生活中的應用俯拾皆是，像是搭電梯、堆積木、疊衣服…等等，對於我們來說這些事情非常直覺，所以其實不太容易察覺到，而以概念來說堆疊不難理解，只是它跟陣列還有指標息息相關，如果還不熟悉的話記得回去複習一下！

思考時間：大家來想想看，上述這些事情有什麼共同點嗎？

答案會在後面的介紹中揭曉 。

現在，就先開始介紹堆疊 (Stack)！

堆疊 (Stack) 是什麼？

Stack 是一個有序的串列，在 Stack 上的所有操作都會在同一個端點進行，而這個端點通常會被稱為 – top 。

回想一下上面的問題，不知道大家想到了什麼？

發現了嗎～上述的事情都有一個特性 – 後進先出 (LIFO, Last-In-First-Out)

舉個例子：

搭電梯的時候，最後進來的人通常會站在最外面，因此如果後面的人想要出電梯，一定要最後進來的人先出去，這就是後進先出的概念。

也就是 Stack 最大的特性！

p.s. 頂端稱為top，底部稱為bottom！

Stack的基礎 – 區域變數（以Ｃ語言為例）

重要概念#1：全域變數 v.s. 區域變數

• 全域變數 (global variable) – 在編譯階段配置記憶體空間。
• 區域變數 (local variable) – 在執行階段進入function之後才配置記憶體空間。

*** 區域變數在function結束執行之後，記憶體空間也就隨之釋放 ***

重要概念#2：function的參數屬於區域變數

Ｃ語言在呼叫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）

規則：

1. 每次只可以移動一個圓盤。
2. 不論什麼情況，圓盤必須保持上小下大的原則。

玩法：將Ａ柱上所有的圓盤移到Ｃ柱。

當圓盤數=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