《數據結構與算法分析》學習筆記：棧 ADT 及鏈表實現

棧 ADT 定義

棧 是限制插入和刪除只能在一端（棧頂）進行的線性表。遵循 **後進先出 (LIFO)** 原則。

核心操作

• `isEmpty()`：判斷棧是否為空
• `push(x)`：元素 x 入棧（棧頂）
• `pop()`：刪除並返回棧頂元素
• `top()`：返回棧頂元素不刪除
• `makeEmpty()`：清空棧

鏈表實現

用單鏈表頭插法實現，頭指針即為棧頂。結構：

struct Node {
    ElementType element;
    Node* next;
};

class Stack {
private:
    Node* topPtr;
public:
    Stack() : topPtr(nullptr) {}
    ~Stack() { makeEmpty(); }
    bool isEmpty() const { return topPtr == nullptr; }
    void push(const ElementType& x) {
        Node* newNode = new Node{x, topPtr};
        topPtr = newNode;
    }
    void pop() {
        if (isEmpty()) throw UnderflowException();
        Node* oldTop = topPtr;
        topPtr = topPtr->next;
        delete oldTop;
    }
    const ElementType& top() const {
        if (isEmpty()) throw UnderflowException();
        return topPtr->element;
    }
    void makeEmpty() {
        while (!isEmpty()) pop();
    }
};

圖示

棧頂指針指向最新插入節點，`push` 在頭部插入，`pop` 刪除頭部節點，均為 O(1)。

應用場景

• 函數調用棧（遞歸實現）
• 表達式求值（中綴轉後綴、括號匹配）
• 深度優先搜索 (DFS) 迭代實現
• 瀏覽器前進/後退歷史
• 撤銷/重做功能

學習建議

初學者自學數據結構需掌握：
1. C/C++ 指針與動態內存管理
2. 遞歸思維
3. 基本算法分析（時間/空間複雜度）
4. 熟練使用標準庫容器（`std::stack`, `std::vector` 等）驗證思路