Java ArrayDeque 實現棧與隊列雙重功能詳解

前言

Java 6 引入 ArrayDeque，作為 Deque 接口的可變長數組實現，完全可以替代 老舊的 Stack (同步開銷大) 和 LinkedList (記憶體碎片化)。本文演示其作為棧/隊列的高效用法。

ArrayDeque 核心特性

• 底層：循環數組 (transient E[] elements)
• 雙端操作：addFirst/addLast, removeFirst/removeLast, getFirst/getLast 均攤 O(1)
• 無容量上限：自動擴容 (2倍)
• 非線程安全：單線程/并發外部同步場景性能極佳
• 實現 Deque、Queue、Cloneable, Serializable

作為棧 (LIFO) 使用

public class ArrayDequeStack {
    private final Deque deque = new ArrayDeque<>();
    
    public void push(E e) { deque.addFirst(e); }
    public E pop() { return deque.removeFirst(); }
    public E peek() { return deque.peekFirst(); }
    public boolean isEmpty() { return deque.isEmpty(); }
    public int size() { return deque.size(); }
}

// 測試
ArrayDequeStack stack = new ArrayDequeStack<>();
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.peek());    // 3

作為隊列 (FIFO) 使用

public class ArrayDequeQueue {
    private final Deque deque = new ArrayDeque<>();
    
    public void offer(E e) { deque.addLast(e); }
    public E poll() { return deque.removeFirst(); }
    public E peek() { return deque.peekFirst(); }
    public boolean isEmpty() { return deque.isEmpty(); }
}

// Queue 接口標準方法
Queue queue = new ArrayDeque<>();
queue.offer("a"); queue.offer("b");
queue.poll(); // "a"
queue.peek(); // "b"

源碼關鍵邏輯剖析

// 核心字段
transient E[] elements;
transient int head; // 隊首索引
transient int tail; // 隊尾索引 (下一個插入位置)

// addFirst 邏輯
public void addFirst(E e) {
    if (e == null) throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e; // 循環數組取模
    if (head == tail) doubleCapacity(); // 觸發擴容
}

// 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;
}

// 擴容策略：2倍，保持元素邏輯順序
private void doubleCapacity() {
    int h = head, n = elements.length;
    int r = n - h; // head 到末尾的元素數
    E[] a = (E[]) new Object[n << 1];
    System.arraycopy(elements, h, a, 0, r);
    System.arraycopy(elements, 0, a, r, h);
    elements = a;
    head = 0;
    tail = n;
}

經典算法題應用：Callatz 猜想關鍵數去重

// 題目：找出不被其他數"覆蓋"的關鍵數，降序輸出
// 核心邏輯：用 ArrayDeque 存輸入，TreeSet 自動去重排序

public class CallatzKeyNumbers {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        Deque input = new ArrayDeque<>(k);
        for (int i = 0; i < k; i++) input.add(sc.nextInt());
        
        Set covered = new HashSet<>();
        for (int n : input) {
            int t = n;
            while (t != 1) {
                t = (t % 2 == 0) ? t / 2 : (3 * t + 1) / 2;
                if (input.contains(t)) covered.add(t); // 被覆蓋
            }
        }
        
        // TreeSet 自然升序，最後反轉輸出
        Set keys = new TreeSet<>();
        for (int n : input) if (!covered.contains(n)) keys.add(n);
        
        keys.stream().sorted(Comparator.reverseOrder())
            .forEach(n -> System.out.print(n + " "));
    }
}

性能對比基準 (JMH 大致數據)

最佳實踐總結

1. 首選 ArrayDeque 實現棧/隊列，除非需要線程安全
2. 線程安全場景：ConcurrentLinkedDeque 或外部鎖保護 ArrayDeque
3. 預估大小構造：new ArrayDeque<>(initialCapacity) 減少擴容
4. 避免 Stack 類 (Java 官方文檔建議用 Deque 替代)