C++ 數據結構實戰：鏈式棧的完整實現與封裝

棧的抽象數據類型 (ADT) 定義

棧是一種後進先出 (LIFO) 的線性表，僅允許在表的一端（棧頂）進行插入（入棧 Push）和刪除（出棧 Pop）操作。核心操作：

• init()：初始化空棧
• push(x)：元素 x 入棧
• pop()：彈出並返回棧頂元素
• top()：獲取棧頂元素 (不彈出)
• empty()：判斷棧是否為空
• size()：返回元素個數

鏈式存儲結構設計

使用單向鏈表實現，棧頂對應鏈表頭節點。每個節點包含數據域 num 和指針域 next。引入頭節點 簡化邊界條件處理（空棧時 head->next == nullptr）。

[頭節點] → [棧頂元素] → [次頂元素] → ... → [棧底元素] → NULL
  head        top              ...                    (head->next 指向棧頂)

完整 C++ 封裝實現 (現代 C++ 風格)

#include <iostream>
#include <stdexcept>
#include <memory> // for std::unique_ptr (可選)

class LinkStack {
private:
    // 內部節點結構
    struct Node {
        int data;
        Node* next;
        Node(int val, Node* nxt = nullptr) : data(val), next(nxt) {}
    };
    
    Node* head_;      // 頭節點 (哨兵)
    size_t size_;     // 元素計數
    
    // 禁用拷貝 (淺拷貝導致雙重釋放)，如需拷貝請實現深拷貝
    LinkStack(const LinkStack&) = delete;
    LinkStack& operator=(const LinkStack&) = delete;

public:
    // 構造函數：創建頭節點
    LinkStack() : head_(new Node(0)), size_(0) {} // 頭節點數據無意義
    
    // 析構函數：釋放所有節點
    ~LinkStack() {
        clear();
        delete head_;
    }
    
    // 移動語義支持
    LinkStack(LinkStack&& other) noexcept : head_(other.head_), size_(other.size_) {
        other.head_ = new Node(0);
        other.size_ = 0;
    }
    LinkStack& operator=(LinkStack&& other) noexcept {
        if (this != &other) {
            clear();
            delete head_;
            head_ = other.head_;
            size_ = other.size_;
            other.head_ = new Node(0);
            other.size_ = 0;
        }
        return *this;
    }

    // 入棧：頭插法 O(1)
    void push(int x) {
        head_->next = new Node(x, head_->next);
        ++size_;
    }
    
    // 出棧：刪除頭節點後首個節點 O(1)
    int pop() {
        if (empty()) throw std::underflow_error("Stack underflow: pop from empty stack");
        Node* topNode = head_->next;
        int val = topNode->data;
        head_->next = topNode->next;
        delete topNode;
        --size_;
        return val;
    }
    
    // 獲取棧頂元素 (不修改棧)
    int top() const {
        if (empty()) throw std::underflow_error("Stack empty: no top element");
        return head_->next->data;
    }
    
    // 判空
    bool empty() const { return head_->next == nullptr; }
    
    // 大小
    size_t size() const { return size_; }
    
    // 清空棧
    void clear() {
        while (!empty()) pop(); // 或手動遍歷刪除
    }
    
    // 顯示棧內元素 (從棧頂到棧底)
    void display() const {
        Node* cur = head_->next;
        std::cout << "Stack (top -> bottom): ";
        while (cur) {
            std::cout << cur->data << " ";
            cur = cur->next;
        }
        std::cout << std::endl;
    }
};

// 測試主程序
int main() {
    LinkStack st;
    int choice, val;
    
    std::cout << "=== 鏈式棧演示程序 ===\n";
    while (true) {
        std::cout << "\n1. 入棧  2. 出棧  3. 顯示棧頂  4. 顯示所有  5. 退出\n選擇: ";
        if (!(std::cin >> choice)) break;
        
        try {
            switch (choice) {
                case 1:
                    std::cout << "輸入入棧值: ";
                    std::cin >> val;
                    st.push(val);
                    std::cout << "入棧成功。";
                    break;
                case 2:
                    val = st.pop();
                    std::cout << "出棧元素: " << val;
                    break;
                case 3:
                    std::cout << "棧頂元素: " << st.top();
                    break;
                case 4:
                    st.display();
                    break;
                case 5:
                    return 0;
                default:
                    std::cout << "無效選項。";
            }
        } catch (const std::exception& e) {
            std::cerr << "\n錯誤: " << e.what();
        }
    }
    return 0;
}

關鍵實現細節解析

1. 頭節點哨兵模式

head_ 不存儲有效數據，其 next 指向棧頂。優勢：

• push/pop 統一操作 head_->next，無需特判空棧。
• empty() 簡單判斷 head_->next == nullptr。

2. 內存管理與異常安全

• 構造函數分配頭節點，析構函數釋放所有數據節點再釋放頭節點。
• pop() 先保存數據，再調整指針，最後 delete，防止內存洩漏。
• 空棧操作拋出 std::underflow_error，調用者可 try-catch 處理。
• 禁用拷貝構造/賦值，避免淺拷貝導致雙重 delete；提供移動語義支持高效轉移所有權。

3. 時間複雜度

對比：順序棧 vs 鏈式棧

STL std::stack 適配器用法

#include <stack>
#include <vector>
#include <deque>
#include <list>

std::stack<int> s1;                    // 默認底層容器: deque
std::stack<int, std::vector<int>> s2; // 底層用 vector
std::stack<int, std::list<int>> s3;   // 底層用 list

s1.push(1); s1.push(2);
std::cout << s1.top(); // 2
s1.pop();
std::cout << s1.size(); // 1

注意：std::stack 是容器適配器，封裝了底層容器的 push_back/pop_back/back，不提供迭代器遍歷。

擴展：模板化通用棧

template <typename T>
class GenericStack {
    struct Node { T data; Node* next; Node(T v, Node* n) : data(v), next(n) {} };
    Node* head_ = new Node(T{}, nullptr);
    size_t size_ = 0;
public:
    ~GenericStack() { clear(); delete head_; }
    void push(const T& v) { head_->next = new Node(v, head_->next); ++size_; }
    T pop() { if (empty()) throw std::underflow_error(""); Node* n=head_->next; T v=n->data; head_->next=n->next; delete n; --size_; return v; }
    const T& top() const { if (empty()) throw std::underflow_error(""); return head_->next->data; }
    bool empty() const { return head_->next == nullptr; }
    size_t size() const { return size_; }
    void clear() { while(!empty()) pop(); }
};

總結

鏈式棧通過動態內存分配實現了無容量上限的 LIFO 結構，適合元素數量不可預知、頻繁增減的場景。本文實現涵蓋了封裝性、異常安全、資源管理 (RAII)、移動語義 等現代 C++ 核心實踐。理解其內部機制有助於在無法使用 STL、需自定義行為（如內存池分配、持久化、線程安全鎖）時靈活構建高性能棧組件。

1. 上一篇文章： C++ I/O 流體系全景解析：從標準流到流緩衝區底層操作
2. 下一篇文章： C++ STL 核心容器與算法深度掌握：string、vector、list、set、map 實戰指南

關於C++

C++11 Lambda 表達式入門詳解：語法、捕獲、可變性、轉換與實戰

Lambda 為什麼有用？ 在函數內部快速定義「一次性」可調

LeetCode 56 Merge Intervals：區間合併排序掃描法

LeetCode 56「Merge Intervals」：給

設計模式實作系列（五）：Singleton 單例模式 - 確保全域唯一實例與存取點

模式意圖 保證一個類別僅有一個實例，並提供一個存取它的全域存

數值積分：矩形法與梯形法 C++ 實現求定積分

基本原理 將積分區間 [a, b] 均分為 n 份，寬度 h