ArrayDeque 源码解析

简介

ArrayDeque 是 Deque（双端队列）的基于数组的实现，底层是一个循环数组（环形缓冲区），可同时作为栈和队列使用。

• 不是线程安全的；并发双端队列请用 ConcurrentLinkedDeque 或 LinkedBlockingDeque。
• 不允许 null 元素（否则无法区分「空槽」与「元素」）。
• 作为栈比 Stack 快，作为队列比 LinkedList 更省内存、性能更好（连续数组缓存友好）。
• 容量按需翻倍扩缩，且容量始终是 2 的幂，以便用位运算 (i & (length-1)) 代替取模。

官方推荐：需要栈时用 ArrayDeque 替代遗留的 Stack；需要队列时优先 ArrayDeque 而非 LinkedList。

底层数据结构分析

ArrayDeque 用 elements 数组存储元素，head 指向队首，tail 指向队尾下一个可写位置；两者在数组上循环移动，当 head == tail 时表示「满」，触发扩容。

transient Object[] elements; // 循环数组，容量恒为 2 的幂
transient int head;          // 队首下标
transient int tail;          // 队尾下一个可写位置的下标

因为是 2 的幂，下标计算用位与代替取模，效率更高：

// 在 head 前插入：head 减 1 后对长度取模（位运算）
elements[head = (head - 1) & (elements.length - 1)] = e;

核心成员变量

transient Object[] elements; // 循环数组
transient int head;          // 队首指针
transient int tail;          // 队尾指针（下一个写入位置）

源码分析

写入：addFirst / addLast

public void addFirst(E e) {
    if (e == null) throw new NullPointerException(); // 不允许 null
    // head 前移一位（循环），写入
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)        // 满则扩容为 2 倍
        doubleCapacity();
}

public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    elements[tail] = e;      // 在 tail 处写入
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();    // 满则扩容
}

读取：pollFirst / pollLast

public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    if (result == null) return null; // 空队列
    elements[h] = null;              // 取出后置空（避免内存泄漏）
    head = (h + 1) & (elements.length - 1); // head 后移
    return result;
}

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

扩容：doubleCapacity

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p;            // head 右侧元素个数
    int newCapacity = n << 1; // 容量翻倍（仍保持 2 的幂）
    Object[] a = new Object[newCapacity];
    // 把循环数组「拉直」复制到新数组前半部分，再接上后半部分
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0; tail = n;      // 重置为 head=0
}

与 LinkedList / Stack 的对比

维度	LinkedList	Stack（遗留）	ArrayDeque
结构	双向链表	数组（Vector 子类）	循环数组
线程安全	否	是（方法级锁，慢）	否
用作队列	可以	不推荐	推荐
用作栈	可以	可用但慢	推荐
允许 null	允许	允许	否

经典 Demo

import java.util.ArrayDeque;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addLast("b"); deque.addFirst("a"); // 双端插入
        System.out.println(deque);      // [a, b]
        deque.push("x");                // 作为栈：入栈
        System.out.println(deque.pop()); // x 出栈
        System.out.println(deque.poll()); // a 作为队列：出队
    }
}