背景

前几篇主要介绍的都是java的普通集合，包括list,set,map等 本篇要介绍和ArrayList对应的ArrayDeque

上一篇和Deque相关的实现时LinkedList。之前提到过LinkedList既是List也是Queue

源码

类图

构造函数

/**  * Constructs an empty array deque with an initial capacity  * sufficient to hold 16 elements.  */ public ArrayDeque() {     elements = (E[]) new Object[16]; }   /**  * Constructs an empty array deque with an initial capacity  * sufficient to hold the specified number of elements.  *  * @param numElements  lower bound on initial capacity of the deque  */ public ArrayDeque(int numElements) {     allocateElements(numElements); }

ArrayDeque顾名思义是一个用数组实现的双向队列。

其默认大小为16【当调用无参构造函数时】

而会通过AllocateElements来进行确保size为2的倍数

private void allocateElements(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     }     elements = (E[]) new Object[initialCapacity]; }

其实就是保证为2的倍数

这段代码就是将左边最高位循环传递给右边  先传1 此时至少最高位和次高位为11 再次循环右传递 此时至少最高4位为1 一次反复直到32位【最高位到末尾】全部为1

这个时候执行+1的操作自然需要进位此时 就完成了2的pow操作 如果溢出需要向右右移

相比较下还是

// Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity)     capacity <<= 1;

容易理解【但是效率可能没有上面的算法高~大数的情况下】

那我们已知就是正常情况下使用ArrayDeque时16的size

由于是双向队列，通常来说需要使用环形来解决 

如何判断队列是否是满呢？

【通常思路是两个指针分别指向头和尾 当向头部插入元素是头指针后移 当向尾部插入元素是尾指针前移，如果头指针和尾指针相遇表示队列已满】===》并不存在严格意义上的满，ArrayDeque会自动扩容 因此属于无界非阻塞队列

addFirst

/**  * Inserts the specified element at the front of this deque.  *  * @param e the element to add  * @throws NullPointerException if the specified element is null  */ public void addFirst(E e) {     if (e == null)         throw new NullPointerException();     elements[head = (head - 1) & (elements.length - 1)] = e;     if (head == tail)         doubleCapacity(); } /**  * Double 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 = (E[])a;     head = 0;     tail = n; }

当插入元素时必然要先检查是够为空为空则直接抛出异常【如果允许插入了空元素当移除的时候碰到null无法区分是否是一个真实的元素，当然也可以同EnumMap的方式使用Object来做mask】

正如上文所说当head == tail表示插入已满 那么需要做扩容【扩容都是两倍】===》为何要求数组的长度为2的倍数？需要通过

(elements.length - 1)进行与操作来保证 由于element.length为2的pow 因此减一自然可以获得全是除首位之后全是1 那么可以轻而易举的获得在size之类的数组下标

扩容的时候每次也是两倍大小的扩容，在做数组元素copy是直接从头指针指向地方开始拷贝 这样不需要重新计算头尾指针 直接将头指针设置为0尾指针设置为之前数组的长度

pollFirst

public E pollFirst() {     int h = head;     E result = 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; }

当移除first时直接将对应头指针的返回即可，同时标记头指针指向的数组元素为空 同时移动头指针