Java集合ArrayDeque高性能实现原理深度剖析

在Java集合框架中，有一个名为 Stack 的类，却找不到名为 Queue 的类（Queue 只是一个接口）。实际上，当需要栈结构时，Java官方已不推荐使用古老的 Stack，而是推荐使用性能更佳的 ArrayDeque；既然 Queue 是接口，当需要队列时，同样首选 ArrayDeque（其次考虑 LinkedList）。在云栈社区的技术讨论中，ArrayDeque也常被提及，作为Java集合框架中高效双端队列的典型实现。

总体介绍

要理解栈和队列的现代用法，首先要了解 Deque 接口。Deque 意为“双端队列”，它既可以作为栈使用，也可以作为队列使用。下面的表格列出了 Deque 接口中与 Queue 接口相对应的方法：

下表则列出了 Deque 与 Stack 类相对应的方法：

上面两个表共定义了 Deque 的12个核心接口。可以看到，添加、删除、取值操作都各有两套方法，它们功能相同，区别在于对操作失败情况的处理不同：一套接口在失败时会抛出异常，另一套则返回特殊值（false 或 null）。除非实现类对容量有特殊限制，否则添加操作通常不会失败。

虽然 Deque 接口方法众多，但本质上都是对容器的两端进行操作，或增、或删、或查。 理解了这一点，后续的分析就会清晰许多。

ArrayDeque 和 LinkedList 是 Deque 的两个通用实现。由于官方更推荐使用 ArrayDeque 作为栈和队列，且 LinkedList 已有诸多分析，本文将聚焦于 ArrayDeque 的具体实现。

从名称可知，ArrayDeque 底层基于数组实现。为了满足在数组两端高效插入和删除元素的需求，这个数组必须是循环数组，即数组的任何位置都可以被视作起点或终点。ArrayDeque 是非线程安全的，在多线程环境下需要手动同步。此外，该容器不允许放入 null 元素。

如上图所示，head 指向队列头部的第一个有效元素，tail 指向队列尾部第一个可供插入元素的空位。由于是循环数组，head 不一定从0开始，tail 也不一定总是大于 head。

方法剖析

addFirst()

addFirst(E e) 方法的作用是在双端队列的头部插入元素，即在 head 指针的前一个位置插入。理想情况下，只需执行 elements[--head] = e 即可。

但实际编码中需考虑：1. 空间是否充足；2. 下标是否越界。例如上图中，若 head 为0时再次调用 addFirst()，虽然有空位，但 head 会变成-1，导致下标越界。以下源码优雅地解决了这两个问题。

//addFirst(E e)
public void addFirst(E e) {
    if (e == null) //不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e; //2.下标越界处理
    if (head == tail) //1.空间是否够用
        doubleCapacity(); //扩容
}

这段代码揭示了一个关键点：空间不足的判断是在插入之后进行的。因为 tail 总是指向下一个空位，意味着数组至少有一个空位，所以插入瞬间无需担心空间。

下标越界的处理非常巧妙：head = (head - 1) & (elements.length - 1)。这相当于对数组长度取模，同时完美处理了 head 减为负值（即-1）的情况。因为 elements.length 必须是2的幂次方，elements.length - 1 的二进制低位全为1，与 head - 1 进行按位与操作，效果等同于取模。

下面重点分析扩容函数 doubleCapacity()。它的逻辑是申请一个双倍大小的新数组，然后将原数组的元素复制过去。过程如下图所示：

如图所示，复制过程分为两步：首先复制 head 指针右侧的元素，然后复制 head 左侧的元素。

//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1; //原空间的2倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    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;
}

addLast()

addLast(E e) 方法的作用是在双端队列的尾部插入元素，即在 tail 指针的当前位置插入。由于 tail 总是指向空位，只需 elements[tail] = e; 即可。插入后检查空间，若已满则扩容。

public void addLast(E e) {
    if (e == null) //不允许放入null
        throw new NullPointerException();
    elements[tail] = e; //赋值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head) //下标越界处理
        doubleCapacity(); //扩容
}

下标越界的处理逻辑与 addFirst() 类似，不再赘述。

pollFirst()

pollFirst() 的作用是删除并返回双端队列头部的元素，即 head 位置的元素。若容器非空，直接返回 elements[head] 即可，同时需处理下标。由于不允许 null 元素，因此 elements[head] == null 就意味着容器为空。

public E pollFirst() {
    E result = elements[head];
    if (result == null) //null值意味着deque为空
        return null;
    elements[head] = null; //let GC work
    head = (head + 1) & (elements.length - 1); //下标越界处理
    return result;
}

pollLast()

pollLast() 的作用是删除并返回双端队列尾部的元素，即 tail 指针前一个位置的元素。

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1); //tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null) //null值意味着deque为空
        return null;
    elements[t] = null; //let GC work
    tail = t;
    return result;
}

peekFirst()

peekFirst() 的作用是返回但不删除双端队列头部的元素，即直接返回 elements[head]。

public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}

peekLast()

peekLast() 的作用是返回但不删除双端队列尾部的元素，即 tail 指针前一个位置的元素。

public E peekLast() {
    return elements[(tail - 1) & (elements.length - 1)];
}

通过以上对核心方法的剖析，我们可以看到 ArrayDeque 利用循环数组和位运算，实现了在两端高效、简洁的增删查操作。其设计是算法/数据结构中利用数组实现循环队列的一个经典范例，也是理解Deque接口及其高性能实现的关键。