Java 數據結構基礎：Stack 棧詳解與五大核心操作實戰

前言

java.util.Stack 繼承自 Vector，實現經典的後進先出（LIFO）數據結構。雖屬舊集合框架，但其語義清晰、API 簡單，在表達式求值、括號匹配、遞歸回溯等場景仍具教學與實用價值。本文詳解五大核心方法、源碼實現機制及現代替代方案。

一、類結構與構造器

public class Stack extends Vector {
    // 唯一構造器：創建空棧
    public Stack() { }
}

繼承 Vector 意味著：

• 底層數組自動擴容
• 所有 Vector 方法可用（如 get()、size()、contains()）
• 線程安全（方法級 synchronized），但性能較差

二、五大核心棧操作

三、完整演示代碼

import java.util.Stack;

public class StackDemo {
    static void showPush(Stack st, int a) {
        st.push(a);
        System.out.println("push(" + a + ") → stack: " + st);
    }

    static void showPop(Stack st) {
        System.out.print("pop → ");
        Integer a = st.pop();
        System.out.println(a + " | stack: " + st);
    }

    public static void main(String[] args) {
        Stack st = new Stack<>();
        System.out.println("初始: " + st); // []

        showPush(st, 42); // [42]
        showPush(st, 66); // [42, 66]
        showPush(st, 99); // [42, 66, 99]

        showPop(st); // 99 → [42, 66]
        showPop(st); // 66 → [42]
        showPop(st); // 42 → []

        try {
            showPop(st); // 拋出 EmptyStackException
        } catch (Exception e) {
            System.out.println("empty stack");
        }
    }
}

輸出結果

初始: []
push(42) → stack: [42]
push(66) → stack: [42, 66]
push(99) → stack: [42, 66, 99]
pop → 99 | stack: [42, 66]
pop → 66 | stack: [42]
pop → 42 | stack: []
empty stack

四、source 關鍵點解析

push 實現（Vector.addElement）

public E push(E item) {
    addElement(item); // Vector 末尾添加
    return item;
}

pop 實現

public synchronized E pop() {
    int len = size();
    if (len == 0) throw new EmptyStackException();
    E obj = elementAt(len - 1); // 獲取最後一個
    removeElementAt(len - 1);   // 刪除最後一個
    return obj;
}

search 實現（從頂向下，1-based）

public synchronized int search(Object o) {
    int i = lastIndexOf(o); // Vector 從尾部查找
    if (i >= 0) return size() - i; // 轉為棧頂起始索引
    return -1;
}

五、現代替代方案：Deque (推薦)

JDK 1.6+ 官方文檔明確建議：

"A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

ArrayDeque 替代示例

import java.util.ArrayDeque;
import java.util.Deque;

Deque stack = new ArrayDeque<>();
stack.push(1);        // 入棧
stack.push(2);
int top = stack.peek(); // 查看頂部 2
int popped = stack.pop(); // 出棧 2
boolean empty = stack.isEmpty(); // false

ArrayDeque 優勢

• 非線程安全 → 單線程性能更高
• 實現 Deque 接口，支持雙端操作
• 無容量上限（動態擴容），無 Vector 同步開銷
• 支持 forEach、stream() 等現代 API

六、典型應用場景

七、總結

• Stack 提供經典 LIFO 語義，五大方法 push/pop/peek/empty/search 覆蓋核心需求
• 繼承 Vector 帶來線程安全但性能代價，新項目首選 ArrayDeque
• 理解 search 的 1-based 從棧頂索引規則，避免 off-by-one 錯誤
• 棧是解決「最近相關」「嵌套結構」「回溯」問題的利器，靈活運用能簡化復雜邏輯