計算機程序思維邏輯 (48)：ArrayDeque 循環數組實現深度剖析

計算機程序思維邏輯 (48)：ArrayDeque 循環數組實現深度剖析

ArrayDeque 是基於動態擴展的循環數組實現 Deque 接口，頭尾操作均攤 O(1)，性能優於 LinkedList。本文從用法、核心字段、循環數組原理、擴容機制、關鍵操作源碼、特點總結六個維度深度解析。

基本用法

// 作為隊列（FIFO）
Queue<String> q = new ArrayDeque<>();
q.offer("a"); q.offer("b"); q.offer("c");
while (q.peek() != null) System.out.print(q.poll() + " "); // a b c

// 作為棧（LIFO）
Deque<String> s = new ArrayDeque<>();
s.push("a"); s.push("b"); s.push("c");
while (s.peek() != null) System.out.print(s.pop() + " "); // c b a

// 雙端操作
Deque<String> d = new ArrayDeque<>();
d.addFirst("a"); d.offerLast("b"); d.addLast("c"); d.addFirst("d");
d.getFirst(); // d
d.peekLast(); // c

核心字段與循環數組概念

private transient E[] elements; // 存儲數組，長度為 2 的冪
private transient int head;     // 隊首索引
private transient int tail;     // 隊尾索引（指向下一個可插入位置）

循環數組：邏輯上首尾相連，head == tail 表示空；(tail + 1) % len == head 表示滿。必須保留至少一個空槽區分滿/空。

四種佈局：

1. 空：head == tail
2. tail > head：元素連續分佈 [head, tail)
3. tail == 0：元素佔據數組末尾與開頭
4. tail < head：元素分兩段 [head, len) + [0, tail)

關鍵操作源碼精讀

構造與擴容

// 默認構造：長度 16
public ArrayDeque() { elements = (E[]) new Object[16]; }

// 指定容量：分配 ≥ numElements+1 且為 2 的冪
private void allocateElements(int numElements) {
    int initialCapacity = 8;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>> 1);
        initialCapacity |= (initialCapacity >>> 2);
        initialCapacity |= (initialCapacity >>> 4);
        initialCapacity |= (initialCapacity >>> 8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        if (initialCapacity < 0) initialCapacity >>>= 1;
    }
    elements = (E[]) new Object[initialCapacity];
}

// 雙倍擴容
private void doubleCapacity() {
    int p = head, n = elements.length, 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;
}

位運算 | (>>> n) 將最高位 1 向右傳播，++ 得到下一個 2 的冪，極其高效。

頭尾增刪

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

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

// pollFirst
public E pollFirst() {
    int h = head;
    E result = elements[h];
    if (result == null) return null;
    elements[h] = null;
    head = (h + 1) & (elements.length - 1);
    return result;
}

// pollLast
public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    E result = elements[t];
    if (result == null) return null;
    elements[t] = null;
    tail = t;
    return result;
}

索引計算均用 & (length-1) 替代 % length，利用 2 的冪特性實現 O(1) 取模。

size 計算

public int size() {
    return (tail - head) & (elements.length - 1);
}

ArrayDeque vs LinkedList 選型指南

總結

ArrayDeque 以循環數組 + 位運算實現高效雙端操作，體現了「數據結構與算法在工程中的藝術」。掌握其原理，不僅能正確選型，更能啟發設計高性能緩衝區、環形隊列等基礎組件。