C++ 實現循序堆疊：模板類完整實作與操作詳解

循序堆疊 (Array-based Stack) 設計

• 底層：動態陣列 Type* base。
• 核心指標：top 指向下一個可寫入位置 (即元素個數)。
• 擴容策略：滿時 capacity *= 2 重新配置 (本範例為教學簡化固定容量)。

完整模板類實作

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

template <typename Type>
class SeqStack {
    static const size_t INIT_SIZE = 8;
    Type* base;
    size_t capacity;
    size_t top; // 當前元素數，也是下一個插入索引
public:
    explicit SeqStack(size_t sz = INIT_SIZE)
        : capacity(sz > INIT_SIZE ? sz : INIT_SIZE), top(0) {
        base = new Type[capacity];
    }
    ~SeqStack() { destroy(); }

    // 禁止複製 (或實作深拷貝)
    SeqStack(const SeqStack&) = delete;
    SeqStack& operator=(const SeqStack&) = delete;

    bool empty() const { return top == 0; }
    bool full() const { return top >= capacity; }
    size_t size() const { return top; }

    // 入堆
    void push(const Type& x) {
        if (full()) {
            // 簡易擴容示範
            size_t newCap = capacity * 2;
            Type* nb = new Type[newCap];
            for (size_t i = 0; i < top; ++i) nb[i] = base[i];
            delete[] base;
            base = nb;
            capacity = newCap;
        }
        base[top++] = x;
    }
    // 出堆
    void pop() {
        if (empty()) { cerr << "Stack underflow\n"; return; }
        --top; // 僅移動指標，析構由覆寫處理
    }
    // 取堆頂 (不移除)
    bool getTop(Type& x) const {
        if (empty()) return false;
        x = base[top - 1];
        return true;
    }
    // 清空
    void clear() { top = 0; }
    // 銷毀
    void destroy() {
        delete[] base;
        base = nullptr;
        capacity = top = 0;
    }
    // 顯示 (堆頂→堆底)
    void show() const {
        if (empty()) { cout << "Stack empty\n"; return; }
        for (size_t i = top; i-- > 0; )
            cout << base[i] << '\n';
    }
};

// 測試
int main() {
    SeqStack st;
    st.push(10); st.push(20); st.push(30);
    cout << "Size: " << st.size() << '\n'; // 3
    st.show(); // 30 20 10
    int topVal;
    st.getTop(topVal); cout << "Top: " << topVal << '\n'; // 30
    st.pop(); st.show(); // 20 10
    st.clear(); st.show(); // empty
    return 0;
}

關鍵函數行為說明

常見錯誤與最佳實踐

1. 忘記擴容：固定容量易溢位，生產碼必須實作動態擴容 (如 vector 策略)。
2. pop 不檢查空堆疊：導致 top 變負 (size_t 無號數下繞)。
3. 淺拷貝問題：預設複製構造會複製指標，雙重釋放崩潰。刪除複製操作或實作深拷貝/移動語意。
4. 類型為類別時：pop 應顯式呼叫析構 base[--top].~Type()，或用 std::vector 替代手動管理。

對比：為何實務上用 std::vector / std::stack？

#include <vector>
#include <stack>
vector v; v.push_back(1); v.pop_back(); // 當堆疊用
stack s; s.push(1); s.top(); s.pop(); // 標準容器介面

• 標準庫經過嚴格測試、支援移動語意、例外安全、除錯器友善。
• 手寫堆疊僅供教學理解底層機制、嵌入式無 STL 環境、或特殊記憶體配置器需求。