數據結構基礎：鏈式棧完整實現（無上溢、動態擴展）

鏈式棧優勢

• 無上溢風險：只要內存足夠，理論無容量上限
• 無需「搬家」：順序棧滿時需重新分配並拷貝，鏈棧僅需分配新節點
• 代價：每個節點額外一個指針（next）

實現方式：單鏈表 + 頭插法，規定所有操作在表頭進行，top 直接指向棧頂元素（無頭哨兵）。

節點與棧定義

template <typename Type>
class ChainNode {
    template <typename T>
    friend ostream &operator<<(ostream &os, const LinkStack<T> &stack);
    friend class LinkStack<Type>;

private:
    ChainNode(const Type &_data, ChainNode *_next = nullptr) 
        : data(_data), next(_next) {}
    Type data;
    ChainNode *next;
};

template <typename Type>
class LinkStack {
    template <typename T>
    friend ostream &operator<<(ostream &os, const LinkStack<T> &stack);

public:
    LinkStack() : m_top(nullptr) {}
    ~LinkStack() { makeEmpty(); }
    
    bool isEmpty() const { return m_top == nullptr; }
    void push(const Type &data);
    void pop() throw(std::out_of_range);
    const Type &top() const throw(std::out_of_range);
    void makeEmpty();

private:
    ChainNode<Type> *m_top;
};

三大核心操作

1. 入棧 push - 關鍵點

template <typename Type>
void LinkStack<Type>::push(const Type &data) {
    // 新節點 next 指向舊棧頂，m_top 指向新節點
    // 首次 push 時 m_top 為 nullptr，新節點 next 自然為 nullptr
    m_top = new ChainNode<Type>(data, m_top);
}

2. 讀棧頂 top

template <typename Type>
const Type &LinkStack<Type>::top() const throw(std::out_of_range) {
    if (isEmpty()) throw std::out_of_range("stack is empty, can't get data");
    return m_top->data;
}

3. 出棧 pop

template <typename Type>
void LinkStack<Type>::pop() throw(std::out_of_range) {
    if (isEmpty()) throw std::out_of_range("stack is empty, can't delete");
    ChainNode<Type> *del = m_top;
    m_top = m_top->next;
    delete del;
}

輔助操作

// 清空棧
template <typename Type>
void LinkStack<Type>::makeEmpty() {
    while (!isEmpty()) pop();
}

// 輸出所有元素（棧頂到棧底）
template <typename Type>
ostream &operator<<(ostream &os, const LinkStack<Type> &stack) {
    for (ChainNode<Type> *p = stack.m_top; p != nullptr; p = p->next)
        os << p->data << ' ';
    return os;
}

測試代碼

int main() {
    LinkStack<int> st;
    for (int i = 0; i < 10; ++i) st.push(rand() % 100);
    cout << st << endl;

    cout << "top = " << st.top() << endl;
    st.pop();
    cout << "top = " << st.top() << endl;
    st.push(1);
    cout << "top = " << st.top() << endl;

    while (!st.isEmpty()) st.pop();
    cout << st << endl;

    st.push(11); st.push(22); st.push(33);
    cout << st << endl;
    st.makeEmpty();
    try { cout << "top = " << st.top() << endl; }
    catch (const exception &e) { cerr << e.what() << endl; }
    return 0;
}

總結

鏈式棧通過頭插法實現 O(1) 入棧/出棧/取頂，動態分配節點消除上溢風險，適合無法預估最大容量的場景。代碼簡潔，異常處理完善，是棧的經典動態實現。