C++ 堆疊資料結構原理與實作完整教學

堆疊核心概念：後進先出 (LIFO)

堆疊 是一種線性資料結構，僅允許在一端（堆疊頂）進行插入與刪除操作。類似一疊書：只能在最上方放入新書、取出最上方的書。若要取第 3 本，必須先移走前 2 本。

關鍵術語

• Push（入堆疊/推入）：在堆疊頂插入新元素
• Pop（出堆疊/彈出）：移除並返回堆疊頂元素
• Top（堆疊頂）：指向最新元素的索引/指標

系統層面的堆疊：呼叫堆疊

每個程序擁有自己的呼叫堆疊，儲存函數呼叫鏈、區域變數、返回位址。ESP（Stack Pointer）暫存器指向堆疊頂。函數呼叫時壓入返回位址與區域變數；返回時彈出。此機制超出資料結構教學範圍，但理解有助於除錯。

陣列實作固定容量堆疊

#include 
using namespace std;

#define MAX 10

class Stack {
    int arr[MAX];
    int top;  // -1 表示空堆疊
public:
    Stack() : top(-1) {}

    void push(int a) {
        if (top + 1 >= MAX) {
            cout << "STACK FULL!!" << endl;
            return;
        }
        arr[++top] = a;
    }

    int pop() {
        if (top == -1) {
            cout << "STACK IS EMPTY!!!" << endl;
            return 0;  // 或拋出例外
        }
        return arr[top--];
    }
};

int main() {
    Stack a;
    a.push(3);  cout << "3 Pushed\n";
    a.push(10); cout << "10 Pushed\n";
    a.push(1);  cout << "1 Pushed\n\n";

    cout << a.pop() << endl;  // 1
    cout << a.pop() << endl;  // 10
    cout << a.pop() << endl;  // 3
    return 0;
}

輸出驗證 LIFO 特性：最後推入的 1 最先彈出。

實作缺點與改進方向

• 固定容量：陣列大小編譯期決定，無法動態擴充。
• 溢位處理：僅輸出訊息，建議拋出例外或返回 std::optional。
• 型別侷限：僅支援 int，現代 C++ 應使用模板實作泛型堆疊。

標準庫 std::stack 使用範例

#include 
#include 
#include 

int main() {
    std::stack stk;
    stk.push("first");
    stk.push("second");
    stk.push("third");

    while (!stk.empty()) {
        std::cout << stk.top() << std::endl;  // third, second, first
        stk.pop();
    }
    return 0;
}

std::stack 為容器配接器，預設以 std::deque 為底層容器，支援動態增長、泛型、標準介面，生產代碼首選。