C++ 實現堆疊類完整教學：從原理到代碼

堆疊資料結構核心概念

堆疊是**後進先出（LIFO, Last In First Out）**的線性結構。只允許在一端（棧頂）插入（Push）與刪除。生活類比：疊盤子——只能在最頂放新盤、拿最頂的盤。

核心操作：

• Push：元素入棧，top++ 後存入。
• Pop：取出棧頂元素，存入暫存，原位置清空，top--，返回值。
• Top：檢視棧頂元素不彈出。
• Empty/Full：狀態查詢。

陣列實現固定容量堆疊

#include 
using namespace std;

const int MAX = 10;  // 最大容量

class Stack {
    int data[MAX];
    int top;  // -1 表示空

public:
    Stack() : top(-1) {}

    void push(int val) {
        if (top == MAX - 1) {
            cout << "STACK FULL!!\n";
            return;
        }
        data[++top] = val;
    }

    int pop() {
        if (top == -1) {
            cout << "STACK IS EMPTY!!!\n";
            return -1;  // 或拋出異常
        }
        return data[top--];
    }

    int peek() const {
        if (top == -1) return -1;
        return data[top];
    }

    bool empty() const { return top == -1; }
    bool full() const { return top == MAX - 1; }
    int size() const { return top + 1; }
};

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

    cout << s.pop() << " popped\n";  // 1
    cout << s.pop() << " popped\n";  // 10
    cout << s.pop() << " popped\n";  // 3
    return 0;
}

輸出驗證 LIFO 特性

3 pushed
10 pushed
1 pushed

1 popped
10 popped
3 popped

最後進入的 1 最先彈出，符合 LIFO。

進階：動態陣列堆疊（可擴容）

#include 
#include   // copy
#include 

template
class DynamicStack {
    T* data;
    int capacity;
    int top;

    void expand() {
        capacity *= 2;
        T* newData = new T[capacity];
        std::copy(data, data + top + 1, newData);
        delete[] data;
        data = newData;
    }

public:
    DynamicStack(int initCap = 10) : capacity(initCap), top(-1) {
        data = new T[capacity];
    }
    ~DynamicStack() { delete[] data; }

    void push(const T& val) {
        if (top == capacity - 1) expand();
        data[++top] = val;
    }

    T pop() {
        if (top == -1) throw std::underflow_error("Stack empty");
        return data[top--];
    }

    T& peek() {
        if (top == -1) throw std::underflow_error("Stack empty");
        return data[top];
    }

    bool empty() const { return top == -1; }
    int size() const { return top + 1; }
};

標準庫 std::stack 使用示範

#include 
#include 
#include 

int main() {
    std::stack history;
    history.push("home");
    history.push("products");
    history.push("detail");

    while (!history.empty()) {
        std::cout << "Back to: " << history.top() << '\n';
        history.pop();
    }
    return 0;
}

std::stack 以 deque 為預設底層容器，也可指定 vector 或 list。

堆疊經典應用場景

常見陷阱與最佳實踐

1. 上溢/下溢：必須檢查 full()/empty()，或使用異常/可選返回值。
2. 固定容量限制：生產代碼優先用動態擴容或 std::stack。
3. 拷貝語意：自定義類需遵循 Rule of Three/Five（析構、拷貝建構、拷貝賦值、移動建構、移動賦值）。
4. 執行緒安全：多執行緒環境需外部鎖或無鎖棧實現。