双端队列 ArrarDeque

封面来源：碧蓝航线 破晓冰华 活动CG

0. 前言

经历高温和疫情双重居家的一个多月后迎来了 2022 年第四季度的第一个月，这个月我没有再做一些无聊的、枯燥的、与实际业务紧密相关的任务，取而代之是与图、树等数据结构相关的工作（话虽这么说，但也不是什么高大上的东西）。在与这些略显复杂的数据结构打交道的过程中，使用最多的基础数据结构是栈和队列。

比如，层序遍历二叉树需要使用到队列，获取图中两个顶点之间的所有路径需要使用到栈。

那么 Java 中提供了哪些类来实现队列和栈呢？

1. 队列与栈

1.1 Java 中的队列

按照前言中的顺序，先来聊聊队列，队列翻译成英文是 Queue，读音为 [kjuː]。

那直接在 IDEA 里 Double Shift Search EveryWhere（双击 Shift 进行搜索），看看 Java 里有没有这个类。

public interface Queue<E> extends Collection<E> {

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

在 Java 中 Queue 被设计为一个接口，这很容易理解，队列的种类有很多，比如阻塞队列和非阻塞队列，又比如普通队列和双端队列，因此设计成一个接口对队列的行为进行规范是再合适不过的了。

在接口的头部注释中可以看到，Queue 是在 JDK 1.5 引入的，作者是 Doug Lea 大神。

Queue 接口继承了 Collection 接口，也是集合的一员。Queue 接口中有 6 个方法，按照功能可以划分为三组，按照是否抛异常可以划分为两组：

功能	抛异常	返回特殊值
增	add(e)	offer(e)
删	remove()	poll()
瞧	element()	peek()

“增”是指增加，即：使指定元素入队；“删”是指删除，即：使指定元素出队。那么“瞧”是什么意思？

单词 peek 可翻译为“窥视、瞥、偷看”，根据其含义，将这一组功能命名为“瞧”。那具体含义是什么？

简单来说就是获取队首元素，与“删”不同的是，“删”是移除队首元素并返回，而“瞧”只返回队首元素，并不会删除。

再说说抛异常的场景，如果操作队列是空队列（is empty），执行 remove() 和 element() 时会抛出 NoSuchElementException 异常，而执行 poll() 和 peek() 时仅仅返回 null。那增加元素为什么还要抛异常呢？

某些队列会有容量的限制（比如阻塞队列 BlockingQueue），在达到最大容量时，这些队列不会扩容，此时再执行 add() 来增加元素就会抛出 IllegalStateException 异常，而执行 offer() 时仅仅返回 false。

应需要根据需求确定是否需要抛出异常以选取合适的 API，并且使用同组 API，保持前后统一，不要一会抛异常一会又不抛异常。

一个怪家伙：PriorityQueue

队列应当符合“先进先出”，但有一个名为 PriorityQueue （优先级队列）的怪家伙，尽管它名字中带有 Queue，也确实实现了 Queue 接口，但它并不是按照入队的时间先后进行出队的。

PriorityQueue 的底层实现是最小堆，也就是说队列中“最小”的元素最先出队。

PriorityQueue 不是本文的主要内容，其更多内容可在本站搜索【二叉堆】和【优先级队列】进行查看。

1.2 Java 中的栈

栈翻译成英文是 Stack，读音为 [stæk]，同样在 IDEA 下搜索看看有没有这个类。

public class Stack<E> extends Vector<E> {
	// 省略实现，这不重要...
}

与队列 Queue 不同，Java 中的 Stack 并不是一个接口，而是一个具体的类，继承至 Vector。

Vector 与 ArrayList 的区别

Vector 和动态数组 ArrayList 类似，主要有两个区别：

1、Vector 是线程安全的，ArrayList 是线程不安全的；

2、默认扩容大小不一样。ArrayList 默认扩容为当前容量的 1.5 倍，Vector 可以指定扩容的大小，在没有显式指定的情况下，扩容为当前容量的 2 倍（扩容的具体实现可以前往对应的类中查看 grow() 方法）。

线程安全的 Vector 看似很美好，然而在单线程无竞争的场景下就是额外的开销了。如果需要线程安全的 ArrayList，可以使用在 JDK 1.5 引入的 CopyOnWriteArrayList，因此 Vector 不再被推荐使用。

不推荐使用 Stack

既然如此，继承至 Vector 的 Stack 也不再推荐使用。你要相信，当一个东西不再被推荐时，肯定不会只有一个原因。不推荐 Stack 作为栈的实现的原因主要有以下两点：

1、Stack 继承至 Vector，它们都是线程安全的，在多数情况下并不需要保证线程安全，一味地使用线程安全的数据结构会造成额外的系统开销；

2、Vector 实现了接口 List，List 提供了 set() 和 get() 方法，使得 Vector 可以进行随机位置的访问，Stack 也继承了这些特性，这显然与栈只能在栈尾进行数据增删的特性是相悖的。

Stack 没了，总得给点替代方案吧？😱

答案就在 Stack 的头部注释中：

A more complete and consistent set of LIFO stack operations is
provided by the Deque interface and its implementations, which
should be used in preference to this class.  For example:

	Deque<Integer> stack = new ArrayDeque<Integer>();

Deque 接口及其实现类提供了一组更完整的、更一致的先进后出的栈操作，比如：ArrayDeque。

1.3 双端队列 Deque

Deque 译为双端队列，读音为 [dek]，是 double ended queue 的缩写。JDK 中的实现：

/** 
 * @author Doug Lea
 * @author Josh Bloch
 * @since  1.6
 * @param <E> the type of elements held in this collection
 */
public interface Deque<E> extends Queue<E> {
    // 省略抽象方法
}

Deque 接口继承至 Queue 接口，可以认为 Deque 拓展了 Queue。除此之外，还可以看到 Deque 接口是在 JDK 1.6 中引入的，作者是 Doug Lea 和 Josh Bloch，前者不必多说，老面孔了，那 Josh Bloch 又是哪位大神呢？

他是 Java 集合框架的创办人，是 Java 圣经之一 《Effective Java》的作者，是 Java 中链表的实现 LinkedList 的作者，更多信息查看 Josh Bloch。

与普通队列相比，双端队列可以在队列的两端进行添加或删除元素。

Deque 与 Queue 类似，根据是否抛出异常可以分成两组：

功能	抛异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)、add(E e)	offerLast(E e)、offer(E e)
删除队首	removeFirst()、remove()	pollFirst()、poll()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()、peek()
查询队尾元素	getLast()	peekLast()

除此之外，Deque 也提供了与操作栈相关的 API，这些 API 的使用与 Stack 中提供的 API 含义一致：

功能	对应 API
入栈	push(E e)
出栈	pop()
瞧	peek()

注意： 提供的与操作栈相关的 API 都会抛出异常。比如入栈元素是 null 时，push() 会抛出异常；当栈是空栈时，pop() 和 peek() 也会抛出异常。peek() 沿用 Queue 提供的方法。

也就是说，Deque 又可以作为栈、也可以作为队列，那使用哪个具体的实现类呢？

查看 Deque 的实现类时，可以看到一个熟面孔：LinkedList，除此之外还有在 Stack 顶部注释提到的 ArrayDeque。

2. 链表 VS 数组

2.1 彼此的特点

LinkedList 和 ArrayDeque 都是 Deque 的实现类，那应该怎么选择呢？

先看看它们的特点，对于 LinkedList 来说 （忽略 LinkedList 实现 List 接口的特性）：

• 它是基于双向链表的数据结构来存储元素的，长度没有限制，不会有扩容机制；
• 可以存储 null；
• 非线程安全的集合

对于 ArrayDeque 来说：

• 它是基于数组的数据结构来存储元素的，长度存在限制，当可用容量为 0 时，会进行扩容，扩容至原数组容量的 2 倍，存在预留的容量空间时会造成空间浪费；
• 不能存储 null；
• 非线程安全的集合

2.2 复杂度对比

通常来说，队列和栈只有三种操作，即：增、删、瞧。这些操作要么是作用在首节点，要么作用在尾节点，不像动态数组或链表那样，可以在任意位置执行添加或删除操作。

在添加元素时：

• LinkedList 额外维护的首指针和尾指针使得复杂度为 O(1)；
• ArrayDeque 与 ArrayList 不同，ArrayDeque 中还记录了首位元素的索引信息，使得在不发生扩容的情况下，添加元素的复杂度为 O(1)；就算出现了扩容操作，其均摊复杂度依旧是 O(1)。

LinkedList 和 ArrayDeque 都能精准地定位到首尾元素，因此它们在删除元素时的时间复杂度也是 O(1)。

这样看来，似乎 LinkedList 更好，因为它不会有额外的扩容开销。

非也，别忘了本文的标题是什么。

2.3 链表赢了？

参考链接：java - Why is ArrayDeque better than LinkedList - Stack Overflow

相比于 ArrayDeque，LinkedList 中每个节点除了存储节点值以外，还需要存储其前驱和后继节点的地址，为了存储这三种信息，需要额外的 Node 对象来存储。向 LinkedList 中添加元素时，需要 new 一个 Node 对象，这会造成额外的内存空间占用，而执行 new 操作还会经历类加载过程和对象创建过程，造成额外的性能损耗。尽管 ArrayDeque 存在扩容过程，但均摊时间复杂度依旧是 O(1)，而 LinkedList 每次插入数据时需要申请新的堆空间的操作，反而使得均摊性能相对更慢。

不仅如此，由于 LinkedList 在添加元素时会创建额外的 Node 对象，后续释放 Node 对象时也会有额外的 GC 成本，甚至还有可能让 GC 迭代整个 LinkedList，虽然没有扩容了性能的损耗，但将更高的损耗转移到了 GC 中。

CPU 在访问某个内存地址时，会查看这个元素对应的内存地址在不在 CPU 的缓存中，如果存在就直接访问，否则先加载到缓存中再访问。CPU 会把当前访问的内存地址所在的那一块信息都加载到缓存中（按块加载）。ArrayDeque 底层采用数组实现，LinkedList 底层采用链表实现。数组中元素的内存地址是连续的，而链表中元素的内存地址 不一定 是连续的。相对于链表而言，数组的缓存命中率更高。

因此在两端添加、删除元素时，ArrayDeque 的性能更好，链表唯一更好的操作是在迭代期间（使用 Iterator）删除当前元素。

综上所述，在项目中基本不会用到 LinkedList。如果想要使用 List 类型的数据结构，可以选择 ArrayList，它还支持高效的随机元素访问；如果想要使用栈、队列类型的数据结构，可以选择 ArrayDeque。或许这一段话不够权威，但 LinkedList 的作者 Josh Bloch 说过：真的有人用过 LinkedList 吗？我写了它，但我从没用过。

而在栈和队列的使用上，Josh Bloch 更建议使用 ArrayDeque：

一无是处的 LinkedList

难道 LinkedList 就真的一无是处，没有任何适用场景？

如果编写的程序依赖于 JDK 1.6 以前的版本，可以使用 LinkedList，因为那时候还没有 ArrayDeque。🤣

又或者想要在队列或链表中添加 null，也可以选择 LinkedList。

再或者想要在迭代过程中删除当前元素，选择 LinkedList 也是可以的。

3. ArrayDeque 的源码分析

3.1 字段信息

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    /**
     * 存储 Deque 中元素的数组。数组的长度即为 Deque 的容量，总是 2 的幂。
     * 数组永远不会被元素填满，尽管可以使用 addX 方法让其暂时填满，但在填满
     * 后又会立即扩容，从而避免 head 与 tail 相等导致 Deque 首尾缠绕。
     * 不包含元素的数组单元始终为 null。
     */
    transient Object[] elements;

    /**
     * 首元素索引。Deque 为空时，等于 tail。
     */
    transient int head;

    /**
     * 下一个将添加到 Deque 尾部的元素的索引。
     * 注意是下一个，不是当前 Deque 中尾元素的索引。
     */
    transient int tail;

    /**
     * 创建 Deque 时的默认最小容量。必须是 2 的幂。
     */
    private static final int MIN_INITIAL_CAPACITY = 8;
    
}

从上述注释中可以得知以下信息：

• ArrayDeque 继承了抽象类 AbstractCollection，内部存在操作集合的方法；

• ArrayDeque 的底层结构是数组，并且长度总是 2 的幂；

• ArrayDeque 引入了 head 和 tail，用于标识首尾。head 为首元素的索引，tail 为下一个尾元素的索引，而不是尾元素的索引；

• ArrayDeque 的最小容量是 8。

得到这些信息的同时也产生出一些疑问：

• ArrayDeque 是怎么保证其内部数组的长度总是 2 的幂？
• tail 为什么不是尾元素的索引，而是下一个尾元素的索引？

带着这些疑问看看 ArrayDeque 提供了哪些构造方法。

3.2 构造方法

public ArrayDeque() {
    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

ArrayDeque 提供了三个构造方法。当调用无参构造方法时，将创建一个能够容纳 16 个元素的数组；还可以传入元素的数量，通过调用 allocateElements() 方法来创建一个能够容纳一定数量的数组；最后还能传入一个集合，先构建数组再把原集合中的元素添加到 ArrayDeque 中。

虽然这些构造方法很简单，但也带来了不少疑问：

• 不是说 ArrayDeque 的最小容量是 8 吗，怎么无参构造方法中指定的容量是 16 呢？最小容量在哪里体现？
• ArrayDeque 提供了指定元素个数的构造方法方法，但传入的元素个数很有可能不会是 2 的幂，ArrayDeque 会怎么保证其内部数组的长度总是 2 的幂呢？

一个疑问都没解决，反而又遇到了新的疑问。三个构造方法有两个都调用了 allocateElements() 方法，这个方法会与“保证内部数组的长度总是 2 的幂”的实现有关吗？

3.3 容量的计算

看看 allocateElements() 的源码：

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

显然重点也不是它，allocateElements() 的内部又调用了 calculateSize()：

private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

瞟一眼 calculateSize() 方法的实现顿时感觉事情变得有趣起来。😈

一眼下去就能发现 calculateSize() 的内部实现使用了大量的位运算，提到位运算就不想到二进制，而二进制又和 2 的幂的计算息息相关，直觉告诉我，就是这个方法保证了 ArrayDeque 的内部数组长度总是 2 的幂。

calculateSize() 方法中使用的位运算

calculateSize() 方法的源码中使用了两种位运算：

• 按位或
• 无符号右移

先说说“按位或”运算：按位或 | 是一个双目运算符，先求出参与运算的两个数的补码，然后使用两补码对应的二进位相或，即：有 1 为 1，全 0 才为 0。

无符号右移：先求出参与运算的数的补码，然后将得到的补码的所有位向右移动指定的位数，左方空缺的位用 0 补充。

计算机中的位运算都是基于补码的，正数的补码与原码相同，负数的补码将其原码除符号位外的所有位按位取反，然后加一。0 的补码、反码、原码都是 0。

calculateSize() 的具体实现

前置知识介绍完毕，再来看看 calculateSize() 的具体实现。

首先令初始容量等于 MIN_INITIAL_CAPACITY，当传入的元素个数大于初始容量时，才进行多次位运算，否则直接构造容量为 MIN_INITIAL_CAPACITY 的数组。

原来 MIN_INITIAL_CAPACITY 真的是 ArrayDeque 的最小容量，只是并不能直接通过无参构造方法构造出最小容量的 ArrayDeque。

以举例的形式来看看 calculateSize() 方法中多次进行的位运算究竟做了什么事。

假设传入的 numElements 值为 17，大于常量 MIN_INITIAL_CAPACITY，然后令初始容量为传入的 numElements，再进行多次无符号右移与按位或运算。

执行 initialCapacity |= (initialCapacity >>> 1); 时，17 的二进制表示形式为 0001 0001，无符号右移 1 位后得到 0000 1000，使用这个值与 0001 0001 进行按位或运算：

    0000 1000
  | 0001 0001
----------------
    0001 1001

运算结果为 0001 1001，十进制表示为 25。

再执行 initialCapacity |= (initialCapacity >>> 2);，25 无符号右移 2 位后得到 0000 0110，使用这个数与 0001 1001 进行按位或运算：

    0000 0110
  | 0001 1001
----------------
    0001 1111

运算结果为 0001 1111，十进制表示为 31。

再执行 initialCapacity |= (initialCapacity >>> 4);，31 无符号右移 4 位得到 0000 0001，使用这个数与 0001 1111 进行按位或运算：

    0000 0001
  | 0001 1111
----------------
    0001 1111

得到的结果依旧是 0001 1111，十进制表示为 31。

再执行 initialCapacity |= (initialCapacity >>> 8);，31 无符号右移 8 位得到 0000 0000，使用这个数与 0001 1111 进行按位或运算：

    0000 0000
  | 0001 1111
----------------
    0001 1111

得到的结果还是 0001 1111，十进制表示为 31。

然后还剩 initialCapacity |= (initialCapacity >>> 16); 没有执行，31 无符号右移 16 位得到的也是 0000 0000，因此最终得到的结果还是 0001 1111，即 31。

再使用 31 自增一，得到 32，32 不小于 0，最终构造的数组长度为 32。

这一番操作下来，或许还没有看懂，那再回到最开始，将传入的 numElements 和每次进行位运算后的结果写在一起进行观察：

位运算次数	二进制表示	十进制表示
0	0001 0001	17
1	0001 1001	25
2	0001 1111	31
3	0001 1111	31
4	0001 1111	31
5	0001 1111	31

在进行第一次位运算后，从左往右数，在忽略补位的 0 的情况下，由 10001 变为了 11001，即左边第二个二进制位变成了 1；进行第三次位运算后，又由 11001 变为了 11111，即左边第三位和第四位的二进制位也变成了 1。 此时得到的 11111 相比于原来的 10001，最高位以下的二进制位都变成了 1。

那为什么要这么做呢？别忘了 ArrayDeque 的内部数组长度总是 2 的幂，那 2 的幂使用二进制会表示成什么样子呢？

十进制的 2 的幂	二进制的 2 的幂
8	0000 1000
16	0001 0000
32	0010 0000
64	0100 0000
128	1000 0000

calculateSize() 方法中多次位运算后的结果并不是 2 的幂，而是要自增一后才是 2 的幂，那 2 的幂减一会是什么样子呢？

十进制的 2 的幂	二进制的 2 的幂	二进制的 2 的幂减一
8	0000 1000	0000 0111
16	0001 0000	0000 1111
32	0010 0000	0001 1111
64	0100 0000	0011 1111
128	1000 0000	0111 1111

减一的结果是最高位变为 0，最高位以下的二进制位都变成了 1。

因此不难知道：calculateSize() 中多次进行的位运算就是为了 找出大于给定的 numElements 的最小 2 的幂减一的值。

那怎么找呢？给定的 numElements 的最高位以下的二进制位都变成 1 就行了，而按位或运算和无符号右移恰好可以达到这个目的。

但还是有几个疑问：

• 为什么无符号右移的位数要按照 1、2、4、8、16 呢？
• 为什么无符号右移的最高位数到 16 就停止了呢？
• 为什么最后还要判断 initialCapacity 是否小于 0 呢？

为什么无符号右移的位数要按照 1、2、4、8、16 呢？

给定一个正数，将其用二进制数表示，左边不补位 0，从左向右看，第一位一定是 1，这是毋庸置疑的。

先无符号右移 1 位，原本给定的数相比于得到的结果，“第一位一定是 1”变成了“第二位一定是 1”，此时使用这两个数进行按位或运算，那么得到的结果相比于原本给定的数，第一位和第二位都一定是 1。

再无符号右移 2 位，此时左边第一位和第二位一定是 1 的位跑到了左边第三位和第四位，此时使用这两个数进行按位或运算，那么得到的结果的左边四位都变成了 1。

再无符号右移 4 位，最后得到的结果的左边八位都变成了 1。

进行了最终的无符号右移 16 位后，最终结果的左边三十二位都会变成 1。

为什么无符号右移的最高位数到 16 就停止了呢？

刚说过，在进行了最终的无符号右移 16 位后，最终结果的左边三十二位都会变成 1。

calculateSize() 方法的返回值类型是 int，int 能表示的最大正数为 2³¹ - 1，加上符号位刚好 32 位，也就是说 int 是占 32 位的（这也是 Java 基础），因此到无符号右移 16 位刚好，再继续无符号右移 32 位也没有意义。

为什么最后还要判断 initialCapacity 是否小于 0 呢？

这下与 calculateSize() 方法的参数类型有关，当传入的参数恰好是 int 类型能表示的最大正数 2³¹ - 1 时，一系列位运算并不会影响这个值，因为这个值就是最大的，而到接下来的自增一时，就会超出 int 能表示的最大值，自增一得到的结果会是 int 类型能表示的最小负数 -2³¹，数组长度显然不能是负数，因此判断一下 initialCapacity 是否小于 0，如果小于 0，无符号右移一位，构建一个容量为 2³⁰ 的数组（也就是说，ArrayDeque 的最大容量为 2³⁰）。在这种情况下，OOM 的概率将会大大提升，正如注释所说，Good luck，祝您好运。😜

3.4 首位添加元素

告别构造方法的实现，遇到的第一个 public 方法就是 addFirst()：

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

addFirst() 方法的源码很简单：

• 首先判断添加元素是否为 null，如果是 null，抛个异常；
• 如果不为 null，设置 head 的值为 (head - 1) & (elements.length - 1)，之后将元素添加到数组下标为 head 的位置；
• 如果 head 等于了 tail，表示双向链表首尾缠绕，数组容量立即扩容为原来的 2 倍。

很显然，addFirst() 的核心就是 (head - 1) & (elements.length - 1) 的计算和 doubleCapacity() 方法的实现。

(head - 1) & (elements.length - 1) 的计算

根据 addFirst() 方法的名称可知，这个运算肯定是求出当前 ArrayDeque 中首元素所在索引的前一个索引。

假设有这样一段代码：

@Test
public void testAddFirst() {
    Deque<String> deque = new ArrayDeque<>();
    deque.addFirst("默烦");
    deque.forEach(System.out::println);
}

除去最后的遍历打印，主体就两行代码，调用 ArrayDeque 的无参构造方法，之后在它的首位添加字符串“默烦”。

调用 ArrayDeque 的无参构造方法后，创建一个容量为 16 的数组，数组结构与 head、tail 的关系如下图：

当执行 addFirst() 方法添加字符串“默烦”到首位时，计算 (head - 1) & (elements.length - 1) 的值：

• head 指向 0，因此 head - 1 = -1；
• 数组长度为 16，16 - 1 = 15；
• 最后计算 -1 & 15 的值即为字符串“默烦”存放的索引位置。

这里的 & 表示按位与运算，它也是一个双目运算符，先求出参与运算的两个数的补码，然后使用两补码对应的二进制位相与，即：全 1 为 1，否则为 0。

计算 -1 & 15 的值时，15 的二进制表示为 0000 1111，-1 的二进制可表示为 1000 0001，两二进制数左边第一位都是符号位。1000 0001 除符号位外按位取反，得到 1111 1110，然后加一得到 1111 1111 即为 -1 的补码，使用 0000 1111 与 1111 1111 进行按位与运算：

    0000 1111
  & 0001 1111
----------------
    0000 1111

因此 -1 & 15 = 15，那么字符串“默烦”会存放在索引为 15 的位置，即：

结果有点出乎意料，原本以为向空的 ArrayDeque 中添加首位元素时会将这个元素放在索引为 0 的位置，结果却放在了索引为 15 的位置。

那再执行 addFirst() 添加一个元素呢？

此时 head 为 15，head - 1 = 14，14 和 15 进行按位与运算：

    0000 1111
  & 0000 1110
----------------
    0000 1110

14 & 15 = 14，因此新添加的元素存放的索引位置是 14。

经过这番分析后，不难得出：head 的前一个索引位置是 (head - 1) & (elements.length - 1)。

按照常理，接下来应该介绍 doubleCapacity() 方法的源码，但现在介绍还稍有欠妥，不能更好地展示它的实现方式，而且 doubleCapacity() 也不会只在 addFirst() 中出现，后面还会遇到它。

我知道你很急，但你先别急。

3.5 末位添加元素

紧接着 addFirst() 方法下的是第二个 public 方法：addLast()，顾名思义，这个方法是添加元素到末位。

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

addLast() 方法的源码也很简单，甚至和 addFirst() 的实现很相似：

• 当添加的元素为 null 时，抛出异常；
• 如果添加的元素不为 null，将添加的元素放到数组索引为 tail 的位置；
• 最后同样是当 tail 等于 head 时，数组扩容为原来的两倍。

在向末位添加元素时，不会像 addFirst 那样计算出索引位置，而是直接将其放到索引为 tail 的位置，这是因为最开始就说过的：head 表示首元素的索引，而 tail 表示下一个将添加到 Deque 尾部的元素的索引。

(tail + 1) & (elements.length - 1) 的计算

(tail + 1) & (elements.length - 1) 的计算结果赋值给了 tail，显然它表示 当前 tail 后的索引位置。

假设有这样一段代码：

@Test
public void testAddLast() {
    Deque<String> deque = new ArrayDeque<>();
    deque.addFirst("默烦");
    deque.addLast("Mofan");
    deque.forEach(System.out::println);
}

执行 addLast() 方法时，将添加的元素存放在索引为 tail 的位置：

之后计算 (tail + 1) & (elements.length - 1) 的值，赋值给 tail。当前 tail 的值为 0，加一后为 1，因此计算 1 & 15 的值：

    0000 0001
  & 0000 1111
----------------
    0000 0001

1 & 15 = 1，最新的 tail 指向的索引位置是 1：

显然 tail 不等于 head，也就不会扩容。

那当 tail 等于 head 时，扩容是怎么实现的呢？

3.6 扩容逻辑

假设现有一 ArrayDeque，其内部数组结构如下图所示：

使用 addLast() 方法向末位添加元素：

此时 head 等于 tail，表示首尾缠绕，形成了一个环，需要进行进行扩容。doubleCapacity() 的源码如下：

/**
 * Doubles the capacity of this deque.  Call only when full, i.e.,
 * when head and tail have wrapped around to become equal.
 */
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    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 = a;
    head = 0;
    tail = n;
}

首先是一个断言，判断 head 与 tail 是否相等。

紧接着将 head 的值赋值给 p，将数组长度值赋值给 n，并计算 n - p 的值赋值给 r。根据注释可知 r 表示 p（即 head）右边的元素数，验证一下：p = 9，n = 16，16 - 9 = 7，由给出的图可知，head 右边的元素数有 6 个，加上 head 自己指向的元素就有 7 个。

使 n 左移 1 位，相当于乘以 2，然后赋值给 newCapacity，这将作为新数组的长度，接下来还判断了 newCapacity 是否小于 0，防止 n 为 2³⁰ 的情况下导致左移结果为负数（int 类型的最大值为 2³¹ - 1）。

构造一个长度为 newCapacity 的数组，使用 System.arraycopy() 进行数据元素的拷贝：

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

System.arraycopy() 是一个本地方法，其参数含义如下：

• src：来源数组
• srcPos：从来源数组的哪个索引开始拷贝
• dest：目标数组
• destPos：拷贝到目标数组的哪个索引
• length：拷贝元素的个数

回到 doubleCapacity() 方法的实现，其中使用 System.arraycopy() 先将 head 左边的元素（包括 head 指向的元素）拷贝到新数组，然后再将 head 右边的元素拷贝到新数组，这样的拷贝不会破坏原 ArrayDeque 中的元素的先后关系。

最后将新数组赋值给 elements，head 值设置为 0，tail 的值设置为原数组长度。

3.7 移除首位元素

addLast() 方法后的是 offerFirst() 和 offerLast()，这两个方法内部调用了 addFirst() 和 addLast()，就不再赘述。

接下里是 removeFirst() 方法，表示删除首位元素：

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

内部调用了 pollFirst() 方法：

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

实现也很简单，先将 head 的值赋值给 h，然后获取首元素，首元素为 null 时表示 ArrayDeque 为空，直接返回 null；否则将索引为 h 的元素设置为 null，使其能被 GC 释放，之后重新设置 head 的值，最后返回首元素。

以添加了两个元素的 ArrayDeque 为例：

移除首元素后：

还需要计算 (h + 1) & (elements.length - 1) 的值，作为 head 的新值。

此时 h 为 15，15 + 1 = 16，elements.length - 1 = 15，两者进行按位与运算有：

    0001 0000
  & 0000 1111
----------------
    0000 0000

计算出的结果为 0，因此新 head 的值为 0：

3.8 移除末位元素

removeFirst() 方法后是 removeLast() 方法：

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

它调用了 pollLast() 方法：

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

由于 tail 表示下一个将添加到 Deque 尾部的元素的索引，因此真正的尾元素索引需要计算一下，那是怎么计算的呢？

还是以添加了两个元素的 ArrayDeque 为例：

真正的尾元素的索引为 (tail - 1) & (elements.length - 1)，当前 tail 指向的索引是 1，tail - 1 = 0，0 & 15 的值即为真正的尾元素的索引，显然，这个值就是 0：

3.9 确定元素位置

通过 addFirst()、addLast()、removeFirst() 和 removeLast() 方法的讲解，不难得出在 ArrayDeque 中确定元素位置的方式。

针对 head 来说：

• 前一个元素的索引是：(head - 1) & (elements.length - 1)
• 下一个元素的索引是：(head + 1) & (elements.length - 1)

针对 tail 来说：

• 前一个元素的索引是：(tail - 1) & (elements.length - 1)
• 下一个元素的索引是：(tail + 1) & (elements.length - 1)

简单来说，前一个就是 - 1，后一个就是 + 1，这也很符合人们的直觉。

如此简单地就能够确定元素的位置，正是 ArrayDeque 总是保证其内部数组的长度总是 2 的幂所带来的好处。如果没有保证其内部数组长度总是 2 的幂，就得使用模运算来计算元素的位置了，效率低下不说，也不容易理解。不信？你可以尝试实现一下。

3.10 移除指定元素

ArrayDeque 还支持删除指定元素，比如删除第一个指定的元素，又比如删除最后一个指定的元素，在 head 和 tail 的存在下，这样的需求很容易实现。

public boolean removeFirstOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            delete(i);
            return true;
        }
        // 从 head 开始向后遍历
        i = (i + 1) & mask;
    }
    return false;
}

public boolean removeLastOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = (tail - 1) & mask;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            delete(i);
            return true;
        }
        // 从 tail 开始向前遍历
        i = (i - 1) & mask;
    }
    return false;
}

要么是从 head 开始向后遍历，要么是从 tail 开始向前遍历，根据前文对确定元素位置的总结，这些很好理解。

这两个方法内部都调用了 delete() 方法，看看它的实现：

private boolean delete(int i) {
    checkInvariants();
    final Object[] elements = this.elements;
    final int mask = elements.length - 1;
    final int h = head;
    final int t = tail;
    final int front = (i - h) & mask;
    final int back  = (t - i) & mask;

    // Invariant: head <= i < tail mod circularity
    if (front >= ((t - h) & mask))
        throw new ConcurrentModificationException();

    // Optimize for least element motion
    if (front < back) {
        if (h <= i) {
            System.arraycopy(elements, h, elements, h + 1, front);
        } else { // Wrap around
            System.arraycopy(elements, 0, elements, 1, i);
            elements[0] = elements[mask];
            System.arraycopy(elements, h, elements, h + 1, mask - h);
        }
        elements[h] = null;
        head = (h + 1) & mask;
        return false;
    } else {
        if (i < t) { // Copy the null tail as well
            System.arraycopy(elements, i + 1, elements, i, back);
            tail = t - 1;
        } else { // Wrap around
            System.arraycopy(elements, i + 1, elements, i, mask - i);
            elements[mask] = elements[0];
            System.arraycopy(elements, 1, elements, 0, t);
            tail = (t - 1) & mask;
        }
        return true;
    }
}

在 detele() 方法的第一行又调用了 checkInvariants() 方法：

private void checkInvariants() {
    // tail 位置没有元素
    assert elements[tail] == null;
    /*
     * head 与 tail 相等时，首元素为 null，即队列为空
     * head 与 tail 不相等时，首、尾元素不为 null
     */
    assert head == tail ? elements[head] == null :
    (elements[head] != null &&
     elements[(tail - 1) & (elements.length - 1)] != null);
    // 首元素的前一个元素为 null
    assert elements[(head - 1) & (elements.length - 1)] == null;
}

checkInvariants() 方法主要做了一些检查，重点回到 delete() 来。

delete() 方法中也使用了一些位运算，为了能更直观地介绍，以前文使用过了一个队列为例：

假设传入 delete() 方法的 i 为 12，直接看这两行：

final int front = (i - h) & mask;
final int back  = (t - i) & mask;

其中 mask 为数组的长度。

(i - h) & mask = (12 - 9) & 15 = 3 & 15 = 3，front 的值为 3。

(t - i) & mask = (8 - 12) & 15 = -4 & 15，-4 用二进制表示为 1000 0100，其补码为 1111 1100，因此有：

    1111 1100
  & 0000 1111
----------------
    0000 1100

-4 & 15 = 12，即 back 的值为 12。

那这两个值是什么意思？根据其英文与求出的值可知：

• front 表示 i 距首元素之间的元素个数；
• back 表示 i 距尾元素之间的元素个数。

求出 front 和 back 后，又是一个判断：

// Invariant: head <= i < tail mod circularity
    if (front >= ((t - h) & mask))
        throw new ConcurrentModificationException();

这在判断 i 是否在 head 和 tail 之间，如果不在，就抛出异常。

然后又判断 front 与 back 的大小关系，看 i 是更靠近 head 还是更靠近 tail，以确定是移动首位元素还是移动末位元素来 减少元素的移动次数， 之后通过元素的移动覆盖索引为 i 的元素完成此元素的删除。

源码中分为了四种情况，本想利用 gif 文件来显示元素移动的过程，奈何个人技术力有限，只能退而求其次，在此给出四种情况下数组结构的初始状态，如何通过元素的移动完成指定索引位置元素的删除，可以通过源码与图示的结合进行理解，相信对你来说并不难。😜

移动元素的四种情况

下列图示中红色背景标记的格子即为 i 的位置。

• front < back && h <= i

• front < back && h > i

• front >= back && i < t

• front >= back && i >= t

3.11 剩下的疑问

ArrayDeque 中的其他方法大多是前文介绍的方法实现的衍生，就不再赘述了。

那在开始时提出的疑问都解决了吗？

似乎还剩下一个：tail 为什么不是尾元素的索引，而是下一个尾元素的索引？

tail 为什么不是尾元素的索引，而是下一个尾元素的索引？

这个很好回答，就是为了更好地计算。

试想当 tail 表示尾元素的索引时，应该怎么作空队列的判断？还是用 tail == head？显然是不行的，因为只添加一个元素时，这个元素既是首元素，也是尾元素，这时依旧满足 tail == head。

那怎么表示？

似乎没有办法，只能移除 tail，引入另一个变量 size，表示队列中的元素个数。

为什么不能在 ArrayDeque 中添加 null？

参考链接：java - Why null values are not allowed in ArrayDeque? - Stack Overflow

当添加的元素是 null 时，会抛出 NullPointerException 异常，为什么要这么设计呢？

在 Deque 的类注释中有这样一段话：

While Deque implementations are not strictly required to prohibit the insertion
of null elements, they are strongly encouraged to do so. Users of any Deque
implementations that do allow null elements are strongly encouraged not to take
advantage of the ability to insert nulls. This is so because null is used as a
special return value by various methods to indicated that the deque is empty.

简单来说：Deque 并没有严格要求不能插入 null，但建议不要插入 null。因为 null 被作为各种方法的 特殊返回值 来表示当前 Deque 为空。

因此 ArrayDeque 中不允许插入 null 的背后原因更多是约定，或者说遵守 Deque 接口的建议。

但并不是说所有 Deque 的实现都不能插入 null，比如 LinkedList 就可以，这也是 LinkedList 的一个适用场景（再次鞭尸 LinkedList 🤣）。

4. 总结与结语

总结

在 Java 中队列和栈的实现一般都选用 ArrayDeque，LinkedList 的适用场景很有限，基本都用不到它。

ArrayDeque 中在保证其内部数组的长度总是 2 的幂的情况下，不仅使元素位置的确定变得容易，还提高了执行效率。

如果想要在 ArrayDeque 中求某个元素前一个位置的索引，可以使用 (i - 1) & (elements.length - 1)；如果想要求某个元素后一个位置的索引，可以使用 (i - 1) & (elements.length - 1)。

结语

这篇文章是在 10 月的倒数第二个星期末开始构思，在 11 月的第一个星期末完成，甚至大部分内容的编写也是在完成的那一天，前后历经半个多月。不是我偷懒迟迟不完成，确实是没有什么时间，临近双十一，购物车空空如也，逛淘宝的时间都抽不出来。

罪魁祸首还是加班，加班到家后临近 10 点，哪里还有什么时间能够提笔构思语言，可恶的是周六还要加班，更是把所剩无几的休息时间压榨得一干二净，或许周日还有一天？可惜周日也被科目三的学习完全填满。

或许，我是说或许，这年头像贵司此般加班的情况已经不多，而且还是 996 且没有加班工资的情况。

THE Fucking Job 🤮