Java 容器 - 双端循环队列 ArrayDeque 分析

ArrayDeque

循环双端队列，底层基于数组实现。继承于AbstractCollection抽象类，并实现了Deque接口。

思路

引入两个游标，head 和 tail，如果向队列里，插入一个元素，就把tail向后移动。如果从队列中删除一个元素，就把head向后移动。

源码

isEmpty()

head 与 tail指向同一个元素，表示队列空

size()

获取队列元素个数。使用位与操作替代求余%操作，效率更高，要注意的是只有长度为2的幂次方情况下才可以使用位与操作替代求余,后面可以看到初始化队列长度时总是使用2的幂次方作为队列长度。

构造方法

提供了3个构造方法，无参构造方法设置初始化长度为16（2的幂次方），其他的构造方法调用allocateElements()方法初始化

allocateElements()

allocateElements() 负责初始化底层数组。源码中对initialCapacity不断的按位右移并位与操作，目的是为了获得一个大于等于numElements的且二进制位全是1的数字， initialCapacity++将数值+1得到一个2的幂次方的值。所以不管传入的初始化容量是多少，队列的初始化长度将是大于等于传入数值的最小的2的幂次方的值。（2的幂次方值在求余操作中可用位&替代，效率更高）
>>> 表示无符号右移(逻辑右移)，int在java中表示4个字节，32位，其中最高位表示符号，其余31位表示数值，可以看到代码中右移次数加起来正好是31位。几次右移后，可以将initialCapacity的最高位为1的位置以及其右侧地位全置成1.

clear()

清空队列。若队列不空，将head和tail都指向第一个元素位置。并遍历从head到tail之间的元素，将这些元素置空（以在下次gc时回收）。

doubleCapacity()

扩容位原来的2倍，并将元素复制到新数组中。n << 1 通过移位实现扩大1倍，移动后可能最高位符号位会被置成1，这时newCapacity就是负数（超出Integer的最大值）。