【Java源码】集合类-ArrayDeque (2)

通过位与计算找到下一个元素的位置。

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

add()函数实际上调用了addLast()函数，顾名思义这是将元素添加到队列尾。前提是不能添加空元素。

elements[tail] = e; 首先将元素添加到tail位置，第一次tail和head都为0.

tail = (tail + 1) & (elements.length - 1) 给tail赋值，这里先将tail指向下一个位置，也就是加一。再和elements.length - 1做位与计算。由于elements.length始终是2的幂，所以elements.length - 1的二进制始终是111...111(每一位二进制都是1)，当(tail + 1)比(elements.length - 1)大1时得到tail为0

(tail = (tail + 1) & (elements.length - 1)) == head 判断tail和head相等，通过doubleCapacity()进行扩容。
例如：初始化7个容量的队列，默认容量为8，当容量达到8时。

8 & 7 = 0 (1000 & 111) 为什么elements.length的实际长度必须是2的幂呢？

这就是为了上面说的位与计算elements.length - 1 以此得到下一个元素的位置tail。

addFirst()

和addLast相反，添加的元素都在队列最前面

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

判空

head = (head - 1) & (elements.length - 1) 通过位与计算，计算head的值。head最开始为0,所以计算式为：

-1 & （lements.length - 1）= lements.length - 1

所以第一次添加一个元素后head就变为lements.length - 1

最终head == tail = 0 达到扩容的条件。

例如：

ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(7); arrayDeque.addFirst(1); arrayDeque.addFirst(2); arrayDeque.addFirst(3);

执行时，ArrayDeque内部数组结构变化为：

0 1 2 3 4 5 6 7
          3   2   1  

第一次添加前head为0，添加时计算：head = -1 & 7 ， 计算head得到7。

remove()/removeFirst()/pollFirst() 删除第一个元素 public E remove() { return removeFirst(); } public E removeFirst() { E x = pollFirst(); if (x == null) throw new NoSuchElementException(); return x; } 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; }

删除元素实际上是调用pollFirst()函数。

E result = (E) elements[h]; 获取第一个元素

elements[h] = null; 将第一个元素置为null

head = (h + 1) & (elements.length - 1); 位与计算head移动到下一个位置

size() 查看长度

public int size() { return (tail - head) & (elements.length - 1); } 七、ArrayDeque应用场景以及总结

正如jdk源码中说的“ArrayDeque当作为栈使用时比Stack快，当作为队列使用时比LinkedList快。” 所以，当我们需要使用栈这种数据结构时，优先选择ArrayDeque，不要选择Stack。如果作为队列操作首位两端我们应该优先选用ArrayDeque。如果需要根据索引进行操作那我们就选择LinkedList.

ArrayDeque是一个双端队列，也是一个栈。

内部数据结构是一个动态的循环数组，head为头指针，tail为尾指针

内部elements数组的长度总是2的幂（目的是为了支持位与计算，以此得到下一个元素的位置）

由于tail始终指向下一个将被添加元素的位置，所以容量大小至少比已插入元素多一个长度。

内部是一个动态的循环数组，长度是动态扩展的，所以会有额外的内存分配，以及数组复制开销。