堆疊（Stack）#

基本概念#

堆疊是一種操作受限的線性表，只允許在一端插入和刪除資料。

核心特性：後進先出（LIFO, Last In First Out）

就像一疊盤子，從上往下放，取的時候也是從上往下取。

基本操作：

• 入堆疊（push）：將資料放入堆疊頂
• 出堆疊（pop）：從堆疊頂取出資料

為什麼需要堆疊？#

陣列和鏈結串列可以替代堆疊的功能，但堆疊的「操作受限」正是它的優勢：

特定的資料結構是對特定場景的抽象。陣列/鏈結串列介面太多，使用時容易出錯。當資料集合只需要在一端插入和刪除，且滿足後進先出特性時，首選堆疊。

實現方式#

時間複雜度： 入堆疊、出堆疊都是 O(1)

空間複雜度： O(1)（存儲空間是必須的，不算額外開銷）

public class ArrayStack {
    private String[] items;  // 陣列
    private int count;       // 堆疊中元素個數
    private int n;           // 堆疊的大小

    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }

    // 入堆疊
    public boolean push(String item) {
        if (count == n) return false;  // 堆疊滿
        items[count] = item;
        ++count;
        return true;
    }

    // 出堆疊
    public String pop() {
        if (count == 0) return null;  // 堆疊空
        String tmp = items[count - 1];
        --count;
        return tmp;
    }
}

動態擴容的均攤分析#

當堆疊滿時，申請 2 倍大小的陣列，搬移 K 個資料。

• 最好情況：O(1)
• 最壞情況：O(n)
• 均攤時間複雜度：O(1)

K 次入堆疊操作中，只有 1 次需要 O(K) 的搬移，其餘 K-1 次都是 O(1)。把 K 次搬移均攤到 K 次入堆疊，每次入堆疊的均攤複雜度為 O(1)。

堆疊的應用場景#

1. 函式呼叫堆疊#

作業系統給每個執行緒分配獨立的記憶體空間，組織成「堆疊」結構：

• 進入函式 → 臨時變數作為堆疊幀入堆疊
• 函式返回 → 堆疊幀出堆疊

int main() {
    int a = 1;
    int ret = add(3, 5);  // add 的堆疊幀入堆疊
    // add 返回後，堆疊幀出堆疊
    return 0;
}

2. 表達式求值#

用兩個堆疊實現：操作數堆疊 + 運算子堆疊

計算 3+5*8-6：

1. 遇到數字 → 壓入操作數堆疊
2. 遇到運算子 → 與運算子堆疊頂比較優先順序
   • 優先順序高 → 壓入運算子堆疊
   • 優先順序低或相等 → 取出運算子和兩個操作數計算，結果壓回操作數堆疊

3. 括號匹配#

檢查 {[()]}、[{()}] 等表達式是否合法：

1. 遇到左括號 → 入堆疊
2. 遇到右括號 → 取出堆疊頂左括號匹配
3. 最終堆疊空 → 合法；否則不合法

4. 瀏覽器前進後退#

用兩個堆疊 X 和 Y：

• 瀏覽新頁面 → 壓入 X
• 後退 → 從 X 彈出，壓入 Y
• 前進 → 從 Y 彈出，壓入 X
• 從中間跳轉新頁面 → 清空 Y

佇列（Queue）#

基本概念#

佇列也是一種操作受限的線性表。

核心特性：先進先出（FIFO, First In First Out）

就像排隊買票，先來的先買，後來的站末尾。

基本操作：

• 入隊（enqueue）：放資料到隊尾
• 出隊（dequeue）：從隊頭取資料

實現方式#

佇列需要兩個指標：

• head：指向隊頭
• tail：指向隊尾

陣列實現的問題#

隨著入隊出隊操作，head 和 tail 不斷後移。當 tail 到達陣列末端時，即使前面有空間也無法入隊。

解決方案：

1. 在入隊時觸發資料搬移（而非每次出隊都搬移）
2. 使用迴圈佇列

迴圈佇列#

把陣列首尾相連，形成環狀結構。

關鍵判定條件：

• 隊空：head == tail
• 隊滿：(tail + 1) % n == head

迴圈佇列會浪費一個陣列位置，因為需要區分隊空和隊滿的狀態。

public class CircularQueue {
    private String[] items;
    private int n = 0;
    private int head = 0;
    private int tail = 0;

    public CircularQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    // 入隊
    public boolean enqueue(String item) {
        if ((tail + 1) % n == head) return false;  // 隊滿
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    // 出隊
    public String dequeue() {
        if (head == tail) return null;  // 隊空
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
}

進階佇列#

阻塞佇列#

在基本佇列上增加阻塞操作：

• 隊空時，取資料會阻塞，直到有資料
• 隊滿時，存資料會阻塞，直到有空位

這就是生產者-消費者模型的實現基礎。

並發佇列#

執行緒安全的佇列。最簡單的做法是加鎖，但並發度低。

基於迴圈佇列 + CAS 原子操作，可以實現高效的無鎖並發佇列。這也是迴圈佇列比鏈式佇列應用更廣泛的原因之一。

佇列的應用場景#

執行緒池請求排隊#

當執行緒池沒有空閒執行緒時，如何處理新請求？

1. 非阻塞方式：直接拒絕
2. 阻塞方式：請求排隊

排隊的實現方式：

• 鏈式佇列（無界）：可無限排隊，但響應時間可能過長
• 陣列佇列（有界）：超過佇列大小則拒絕，對響應時間敏感的系統更合適

對於大部分資源有限的場景，當沒有空閒資源時，都可以通過「佇列」來實現請求排隊。例如：執行緒池、資料庫連線池等。

小結#