Java ArrayDeque 雙端隊列核心原理與高性能應用實戰

ArrayDeque 核心定位

ArrayDeque<E> 是 JDK 6 引入的 可變長度雙端隊列，基於循環數組實現，同時實現 Deque、Queue、Cloneable、Serializable。核心優勢：

• 無容量上限：動態擴容 (2倍)，理論支持 Integer.MAX_VALUE 元素
• 雙端 O(1) 操作：頭尾增刪查均為常數時間
• 無鎖非線程安全：單線程性能極高，多線程需外部同步或用 ConcurrentLinkedDeque
• 內存效率高：數組連續存儲，無節點對象開銷，GC 友好
• 替代 Stack/Vector：官方推薦作為棧 (LIFO) 和隊列 (FIFO) 首選

核心 API 速查

底層原理深度解析

循環數組結構

transient Object[] elements; // 存儲數組，長度始終為 2 的冪
transient int head;          // 隊首索引 (指向第一個元素)
transient int tail;          // 隊尾索引 (指向下一個插入位置)

// 邏輯大小
public int size() { return (tail - head) & (elements.length - 1); }
public boolean isEmpty() { return head == tail; }

雙端操作核心邏輯

// 隊首插入：head 向左移動 (環繞)
public void addFirst(E e) {
    if (e == null) throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail) doubleCapacity(); // 已滿，擴容
}

// 隊尾插入：tail 向右移動 (環繞)
public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    elements[tail] = e;
    if ((tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();
}

// 隊首刪除
public E removeFirst() {
    int h = head;
    E result = (E) elements[h];
    if (result == null) throw new NoSuchElementException();
    elements[h] = null; // GC 友好
    head = (h + 1) & (elements.length - 1);
    return result;
}

// 隊尾刪除
public E removeLast() {
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null) throw new NoSuchElementException();
    elements[t] = null;
    tail = t;
    return result;
}

擴容機制 doubleCapacity()

private void doubleCapacity() {
    int oldCapacity = elements.length;
    int newCapacity = oldCapacity << 1; // 2倍
    if (newCapacity < 0) throw new IllegalStateException("Deque too large");
    
    Object[] newElements = new Object[newCapacity];
    // 複製兩段：head->end, 0->tail
    int headSize = oldCapacity - head;
    System.arraycopy(elements, head, newElements, 0, headSize);
    System.arraycopy(elements, 0, newElements, headSize, tail);
    elements = newElements;
    head = 0;
    tail = oldCapacity;
}

迭代器實現

public Iterator<E> iterator() {
    return new DeqIterator();
}

private class DeqIterator implements Iterator<E> {
    private int cursor = head;
    private int fence = tail;
    
    public boolean hasNext() { return cursor != fence; }
    
    @SuppressWarnings("unchecked")
    public E next() {
        if (cursor == fence) throw new NoSuchElementException();
        E result = (E) elements[cursor];
        cursor = (cursor + 1) & (elements.length - 1);
        return result;
    }
    
    public void remove() { throw new UnsupportedOperationException(); }
}

性能基準測試 (JMH)

結論：ArrayDeque 在單線程雙端操作上全方位碾壓 LinkedList，內存效率高 3 倍。

經典應用場景實戰

1. 高性能棧 (LIFO) - 替代 Stack

Deque<String> stack = new ArrayDeque<>();
stack.push("A"); // addFirst
stack.push("B");
stack.push("C");
System.out.println(stack.pop());  // C - removeFirst
System.out.println(stack.peek()); // B - getFirst
// 優勢：無同步開銷、動態擴容、支持 null 檢查

2. 高性能隊列 (FIFO) - 替代 LinkedList/ArrayBlockingQueue (單線程)

Queue<Task> queue = new ArrayDeque<>();
queue.offer(task1); // addLast
queue.offer(task2);
Task t = queue.poll(); // removeFirst - 返回 null 而非拋異常
// 優勢：無鎖、無節點對象、批量處理吞吐極高

3. 滑動窗口 / 固定大小緩存

public class SlidingWindow<T> {
    private final ArrayDeque<T> window;
    private final int maxSize;
    
    public SlidingWindow(int maxSize) {
        this.maxSize = maxSize;
        this.window = new ArrayDeque<>(maxSize);
    }
    
    public synchronized void add(T item) {
        if (window.size() == maxSize) window.removeFirst(); // 捨棄最舊
        window.addLast(item);
    }
    
    public synchronized List<T> getWindow() {
        return new ArrayList<>(window); // 複製快照
    }
    
    // 應用：最近 N 次請求延遲、移動平均、限流計數器
}

4. 表達式求值 / 語法解析 (Shunting Yard 算法)

public class ExpressionEvaluator {
    public double evaluate(String expr) {
        ArrayDeque<Double> values = new ArrayDeque<>();
        ArrayDeque<Character> ops = new ArrayDeque<>();
        // ... 解析邏輯，利用雙端隊列特性高效處理運算符優先級
        return values.pop();
    }
}

5. 瀏覽器前進後退 / 撤銷重做

public class HistoryManager {
    private final ArrayDeque<String> backStack = new ArrayDeque<>();
    private final ArrayDeque<String> forwardStack = new ArrayDeque<>();
    private String current;
    
    public void visit(String url) {
        if (current != null) backStack.push(current);
        current = url;
        forwardStack.clear();
    }
    
    public String back() {
        if (backStack.isEmpty()) return current;
        forwardStack.push(current);
        return current = backStack.pop();
    }
    
    public String forward() {
        if (forwardStack.isEmpty()) return current;
        backStack.push(current);
        return current = forwardStack.pop();
    }
}

6. BFS 圖遍歷 / 層序遍歷

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.pollFirst();
            level.add(node.val);
            if (node.left != null) queue.offerLast(node.left);
            if (node.right != null) queue.offerLast(node.right);
        }
        result.add(level);
    }
    return result;
}

多線程環境下的選擇

常見誤區與避坑

1. 作為棧用 push/pop 但混用 add/remove：語義混淆，統一使用 push/pop/peek 或 addFirst/removeFirst/getFirst
2. 多線程直接共享 ArrayDeque：非線程安全，必須外部加鎖或換用並發類
3. 假設初始容量固定：構造函數 new ArrayDeque(100) 會調整為 2 的冪 (128)，非精確容量
4. 迭代器中調用 remove()：拋 UnsupportedOperationException，需用索引遍歷或複製快照
5. 存儲 null 元素：NullPointerException，設計上不允許 null

源碼級優化技巧

// 1. 預估大小避免擴容
ArrayDeque<Task> queue = new ArrayDeque<>(estimatedSize);

// 2. 批量操作優化 (JDK 10+)
queue.addAll(Collection); // 內部優化批量複製
List<Task> batch = new ArrayList<>(queue); // toArray 內部優化

// 3. 清理引用加速 GC
queue.clear(); // 內部將元素位置置 null

// 4. 反序列化後修正 transient 字段
// ArrayDeque 實現 Serializable，反序列化自動重建數組結構

ArrayDeque 是 Java 集合框架中「性能與通用性平衡最好」的雙端隊列實現。掌握其循環數組原理、擴容機制、雙端 API 語義、適用邊界，能在單線程高吞吐場景 (解析器、緩存、窗口、遍歷) 中發揮極致效能，是每個 Java 開發者必備的工具箱利器。