使用 ArrayDeque 實現高效能 Stack：替代舊版 Vector 懶人包

為何選擇 ArrayDeque？

JDK 1.6 引入 ArrayDeque 實現 Deque 介面（雙端佇列）。相比老舊的 Stack（繼承自 Vector，所有方法 synchronized），ArrayDeque 非線程安全、無同步開銷、效能更優，且提供豐富的雙端操作，是單線程環境下棧/佇列的首選。

自定義 IntegerStack 實現

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

public class IntegerStack {
    private final Deque<Integer> data = new ArrayDeque<>();

    public void push(Integer element) { data.addFirst(element); }
    public Integer pop() { return data.removeFirst(); }
    public Integer peek() { return data.peekFirst(); }

    @Override public String toString() { return data.toString(); }

    public static void main(String[] args) {
        IntegerStack stack = new IntegerStack();
        for (int i = 0; i < 5; i++) stack.push(i);
        System.out.println("初始棧: " + stack);           // [4, 3, 2, 1, 0]
        System.out.println("彈出: " + stack.pop());       // 4
        System.out.println("彈出後: " + stack);           // [3, 2, 1, 0]
        System.out.println("查看棧頂: " + stack.peek());  // 3
        System.out.println("最終棧: " + stack);           // [3, 2, 1, 0]
    }
}

關鍵方法對應：push ↔ addFirst、pop ↔ removeFirst、peek ↔ peekFirst。

ArrayDeque 核心源碼解析

底層為循環陣列，維護 head（隊頭索引）與 tail（隊尾索引）。

擴容機制 doubleCapacity()

private void doubleCapacity() {
    int p = head, n = elements.length;
    int r = n - p;                    // 右側元素數
    int newCapacity = n << 1;         // 容量翻倍
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);  // 右段複製到新陣列頭部
    System.arraycopy(elements, 0, a, r, p);  // 左段接在後面
    elements = (E[]) a;
    head = 0; tail = n;               // 重置指針
}

擴容時將邏輯順序「拉直」存放，head 歸零，tail 指向原大小，保證後續操作連續性。

入棧 addFirst(E e)

public void addFirst(E e) {
    if (e == null) throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail) doubleCapacity();
}

位運算 (head - 1) & (length - 1) 實現循環遞減（length 為 2 的冪次）。初始 head=0，首次插入後 head=15（預設容量 16）。

出棧 removeFirst()

public E removeFirst() {
    E x = pollFirst();
    if (x == null) throw new NoSuchElementException();
    return x;
}
public E pollFirst() {
    int h = head;
    E result = elements[h];
    if (result == null) return null;
    elements[h] = null;                              // 釋放引用助 GC
    head = (h + 1) & (elements.length - 1);          // 指針循環遞增
    return result;
}

效能對比總結

多線程場景請使用 ConcurrentLinkedDeque 或 Collections.synchronizedDeque() 包裝。