Java 數據結構精講：棧（Stack）原理、實現與經典應用場景

什麼是棧？

棧 是一種先進後出（LIFO, Last In First Out）的線性表。只允許在一端（棧頂）進行插入和刪除操作。生活類比：疊盤子、瀏覽器歷史記錄、函數調用棧。

核心操作與複雜度

陣列實現（教學版）

public class ArrayStack<E> {
    private E[] data;
    private int top = -1; // -1 表示空

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        data = (E[]) new Object[capacity];
    }

    public void push(E e) {
        if (top + 1 == data.length) throw new IllegalStateException("Stack full");
        data[++top] = e;
    }

    public E pop() {
        if (isEmpty()) throw new IllegalStateException("Stack empty");
        E e = data[top];
        data[top--] = null; // 幫助 GC
        return e;
    }

    public E peek() { return isEmpty() ? null : data[top]; }
    public boolean isEmpty() { return top == -1; }
    public int size() { return top + 1; }
}

鏈表實現（無容量上限）

public class LinkedStack<E> {
    private static class Node<E> { E val; Node<E> next; }
    private Node<E> head;
    private int size;

    public void push(E e) {
        Node<E> n = new Node<>(); n.val = e; n.next = head;
        head = n; size++;
    }
    public E pop() {
        if (head == null) throw new IllegalStateException("Stack empty");
        E val = head.val; head = head.next; size--; return val;
    }
    // peek/isEmpty/size 類似
}

JDK 內建類：Deque 接口替代 Stack

java.util.Stack 繼承自 Vector（同步、效能差），官方建議使用 Deque<E>：

Deque<String> stack = new ArrayDeque<>();
stack.push("A"); stack.push("B");
System.out.println(stack.pop()); // B
System.out.println(stack.peek()); // A

經典應用場景與代碼

1. 字符串反轉

public String reverse(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) st.push(c);
    StringBuilder sb = new StringBuilder();
    while (!st.isEmpty()) sb.append(st.pop());
    return sb.toString();
}

2. 括號匹配驗證

public boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' && (st.isEmpty() || st.pop() != '(')) return false;
        else if (c == ']' && (st.isEmpty() || st.pop() != '[')) return false;
        else if (c == '}' && (st.isEmpty() || st.pop() != '{')) return false;
    }
    return st.isEmpty();
}

3. 中綴表達式求值（雙棧法：操作數棧 + 運算符棧）

// 略：參考 Dijkstra 兩棧算法，支援 + - * / ( ) 優先級

4. 瀏覽器前進/後退、編輯器撤銷/重做

維護兩個棧：backStack、forwardStack，跳轉時在兩棧間移動元素。

避坑指南

• 陣列實現需處理擴容（倍增策略）或拋出異常；
• pop() 後將陣列位置置 null，避免記憶體洩漏；
• 多線程環境下使用 ConcurrentLinkedDeque 或自行加鎖；
• 遞歸深度過大導致 StackOverflowError 時，改用顯式棧模擬遞歸（尾遞歸優化）。