今天要來進到新的單元~還記得我們在第一天有簡單提到 Stack 嗎?
接下來要更加了解他

堆疊(Stack)是什麼?

堆疊是一種只能在同一端(稱為頂端,Top)進行新增跟刪除的資料結構,
遵守後進先出(Last In First Out, LIFO) 的規則 最後放進去的資料,會最先被拿出來。

常見的 Stack例子 :

*圖片來源 https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcTjfwOqmUeFJBanPmdOSpzOixlcdafCUwCcnydBr8OYsA&s=10
一疊盤子，你只能從 最上面 拿，也只能從 最上面 放
不可能從中間抽或底下拿

這就是堆疊的特性 : 進去的順序,跟出來的順序是相反的。
如下圖

堆疊的基本操作

堆疊只有幾個固定的操作,不像陣列或鏈結串列有那麼多種運算方式:

用陣列實作堆疊

class Stack {
private:
    int arr[100];    // 固定大小的陣列
    int topIndex;     // 記錄目前頂端的索引
 
public:
    Stack() {
        topIndex = -1;   // 初始化為-1,代表堆疊是空的
    }
 
    void push(int value) {
        topIndex++;
        arr[topIndex] = value;
    }
 
    int pop() {
        int value = arr[topIndex];
        topIndex--;
        return value;
    }
 
    int top() {
        return arr[topIndex];
    }
 
    bool isEmpty() {
        return topIndex == -1;
    }
};

為什麼初始化要設成 -1,不是 0?
回想 Day06 陣列索引 的規則(合法範圍是 0 到 n-1)
如果堆疊是空的,代表還沒有任何元素,topIndex 設成 -1 剛好可以配合 isEmpty() 判斷,而且第一次 push 進來時,topIndex 從 -1 變成 0,剛好對應到陣列的第一個合法索引。

用陣列實作的限制:大小固定

上面的寫法用了 int arr[100] 這種固定大小的陣列,
如果元素數量超過100,會發生堆疊溢位(Stack Overflow)
這正好呼應 Day09 提過的陣列缺點，如果不確定資料量上限,用陣列實作堆疊會有這個風險。

C++ STL(標準模板庫) Stack

在 C++ 中，可以直接使用 STL 提供的 stack。

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.top() << endl;

    s.pop();

    cout << s.top() << endl;
}

輸出：

3
2

Stack 的時間複雜度

因為所有操作都只會接觸最上面的元素，所以效率非常高。

堆疊的實際應用

呼叫堆疊

還記得 Day05 遞迴 那篇提過的「呼叫堆疊(Call Stack)」嗎?
那其實就是堆疊這個資料結構最經典的實際應用，函式呼叫函式時,每一層呼叫都會被 push 進呼叫堆疊,函式執行完畢後才被 pop 出去,這也是為什麼遞迴呼叫太深會發生「Stack Overflow」的原因,名字就是直接借用堆疊溢位這個概念。

瀏覽器上一頁

最後進來的頁面最先離開
當你瀏覽網頁時：(push)
A → B → C → D

按上一頁：(pop)
D → C

再按一次：
C → B

文字編輯器的復原(Undo)功能

每個操作都(push)進堆疊,復原時(pop)出最近一次的操作

那接下來,我們會用一題LeetCode的括號匹配題目,實際把堆疊的概念用到解題上。

參考資料和書籍

1. 圖解資料結構×演算法:運用C++ 胡昭明
2. https://www.programiz.com/dsa/stack
3. https://www.wscubetech.com/resources/dsa/stack-data-structure