Java Deque 實現高性能棧：ArrayDeque 替代 Stack 的最佳實踐

為什麼不用 java.util.Stack？

Stack 繼承自 Vector，**所有方法同步**，單線程下性能低下；且繼承導致接口污染（暴露 add/remove/indexOf 等非棧操作）。官方文檔明確建議：使用 Deque 及其實現 ArrayDeque 替代。

ArrayDeque 核心優勢

• 非線程安全、無同步開銷：單線程性能比 Stack 快 3-5 倍
• 雙端隊列：同時支持棧（LIFO）與隊列（FIFO）操作
• 動態數組：初始容量 16，按 2 倍擴容，無容量上限（Integer.MAX_VALUE）
• 實現 Deque 接口：語義清晰，push/pop/peek 對應 addFirst/removeFirst/peekFirst

標準棧封裝類

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

public class ArrayDequeStack<E> {
    private final Deque<E> data = new ArrayDeque<>();

    /** 入棧：O(1) */
    public void push(E element) {
        data.addFirst(element);
    }

    /** 出棧：O(1)，空棧拋出 NoSuchElementException */
    public E pop() {
        return data.removeFirst();
    }

    /** 查看棧頂：O(1)，空棧返回 null */
    public E peek() {
        return data.peekFirst();
    }

    /** 檢查是否為空 */
    public boolean isEmpty() {
        return data.isEmpty();
    }

    /** 獲取大小 */
    public int size() {
        return data.size();
    }

    /** 清空棧 */
    public void clear() {
        data.clear();
    }

    @Override
    public String toString() {
        return "Stack[" + data + "]"; // 顯示順序：棧頂 → 棧底
    }

    // ========== 測試主方法 ==========
    public static void main(String[] args) {
        ArrayDequeStack<Integer> stack = new ArrayDequeStack<>();
        for (int i = 0; i < 5; i++) stack.push(i);
        System.out.println("入棧 0-4：" + stack); // Stack[[4, 3, 2, 1, 0]]

        int popped = stack.pop();
        System.out.println("出棧：" + popped + " → " + stack); // 4 → Stack[[3, 2, 1, 0]]

        int peeked = stack.peek();
        System.out.println("查看棧頂：" + peeked + " → " + stack); // 3 → Stack[[3, 2, 1, 0]]
    }
}

進階用法：棧在算法題中的經典應用

1. 括號匹配驗證

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

private boolean match(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

2. 逆波蘭表達式求值

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        if ("+".equals(t)) stack.push(stack.pop() + stack.pop());
        else if ("-".equals(t)) { int b = stack.pop(); stack.push(stack.pop() - b); }
        else if ("*".equals(t)) stack.push(stack.pop() * stack.pop());
        else if ("/".equals(t)) { int b = stack.pop(); stack.push(stack.pop() / b); }
        else stack.push(Integer.parseInt(t));
    }
    return stack.pop();
}

3. 單調棧：下一個更大元素

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // 存索引
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

性能基準測試（JMH 片段）

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public void stackPushPop_ArrayDeque() {
    Deque<Integer> d = new ArrayDeque<>();
    for (int i = 0; i < 1000; i++) d.push(i);
    for (int i = 0; i < 1000; i++) d.pop();
}

@Benchmark
public void stackPushPop_Stack() {
    Stack<Integer> s = new Stack<>();
    for (int i = 0; i < 1000; i++) s.push(i);
    for (int i = 0; i < 1000; i++) s.pop();
}
// 典型結果：ArrayDeque ~15,000 ns/op | Stack ~65,000 ns/op（快 4 倍+）

避坑指南

總結

ArrayDeque 是 Java 中實現棧的**首選方案**：非同步、動態擴容、雙端操作、豐富 API、性能卓越。封裝薄薄一層 ArrayDequeStack<E> 即可獲得語義純粹、類型安全、高性能的棧結構。算法題、表達式求值、瀏覽器歷史、撤銷重做等場景，請毫不猶豫選擇它，徹底拋棄古老的 Stack。