我们在学习ArrayList的时候，知道其底层是数组。而在学习LinkedList时候，知道其实现了Deque接口。
那么，这篇讲到的ArrayDeque，就是底层是数组，又实现了Deque接口的一种容器。
为什么需要这样的容器呢？这种容器有什么用呢？
先看看ArrayDeque的接口：
先看构造函数：
public ArrayDeque() {
elements = new Object[16 + 1];
}
public ArrayDeque(int numElements) {
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
原来内部结构果然是elements数组。
无参构造函数原来是分配16+1=17的数组大小。
传参的构造函数分配numElements+1个数组大小。传负数就创建1+1=2个。传入超过MAX_VALUE = 0x7fffffff就只能创建MAX_VALUE = 0x7fffffff个。
再看addFirst(E e)插入头步元素的函数：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
grow(1);
}
`es[head = dec(head, es.length)] = e;拆开来看就是：
head = dec(head, es.length);
es[head] = e;
那么，这个head是多少呢？
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number 0 <= head < elements.length equal to tail if
* the deque is empty.
*/
transient int head;
原来，head是指向数组头部的索引。初始化是0。取值范围是大于等于0，而小于数组长度。如果等于尾部索引head == tail的话，就证明是空的队列。
那dec是啥函数？
/**
* Circularly decrements i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
注释提到：循环减i，与系数取模。 前置条件和后置条件:0 <= i <系数。
什么意思？这里传入i就是head，值是0。--0就是-1，小于0。所以呢，head = es.length - 1。如果加入的是第一个元素，那么head = 17 - 1 = 16 。
计算出head值后，执行es[head] = e;就是把e存放在数组的第16个位置，就是倒数第一个位置。
如果继续调用addFirst加入头部，这时候head = 15，放在倒数第二个位置。
原来，ArrayDeque的addFirst是对数组索引逆序使用，以实现元素插入头部的功能。想象下，就好像一群胆小的人去坐过山车。胆小的人抢着先坐最后一个座位。第二个胆小的只能坐倒数第二个座位。我们可以这样建立这样的联想：
ArrayDeque的
addFirst相当于胆小鬼坐过山车抢后排座位，从后往前坐。
继续看下一句：
if (head == tail)
grow(1);
当插入一个元素后，如果头部与尾巴重叠，证明数组满了。这时候调用grow(1)扩容。
/**
* Increases the capacity of this deque by at least the given amount.
对这个双向队列进行扩容，至少也要达到给定的容量
*
* @param needed the required minimum extra capacity; must be positive
*/
private void grow(int needed) {
// overflow-conscious code
// 保存扩容前的长度
final int oldCapacity = elements.length;
// 扩容后的长度
int newCapacity;
// Double capacity if small; else grow by 50%
// jump 为待扩容长度。如果原长度小于64，就每次扩容原来的长度+2。如果大于64，每次扩容50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
// 1、如果待扩容长度小于用户期望扩容的长度，就调用 newCapacity(needed, jump)
// 2、或者扩容超最大限制了，也调用 newCapacity(needed, jump)
// 3、最终得到期待的长度newCapacity
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
// 创建个新的扩容后长度的数组，把老数组元素拷贝过去
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
// 处理下如果 tail == head 的异常情况
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
// 把原来的元素重新放回扩容后数组末尾
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
// 把原来位置的元素至为空
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
newCapacity(needed, jump)也很简单，如下：
/** Capacity calculation for edge conditions, especially overflow. */
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
// 如果按期待去扩容，容量大于MAX_ARRAY_SIZE，而且没溢出的话，就只返回Integer.MAX_VALUE
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
// 如果期待扩容的容量，大于计算出来的扩容，就用期待的容量
if (needed > jump)
return minCapacity;
// 否则就返回计算出来的保证不溢出的扩容量
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
? oldCapacity + jump
: MAX_ARRAY_SIZE;
}
另外，MAX_ARRAY_SIZE注释上面提到，有一些虚拟机需要存储一些头信息在数组里，如果扩容到Integer.MAX_VALUE会造成内存溢出，所以才有如下定义：
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
再看看addLast，果然跟addFirst差不多。
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
grow(1);
}
而根据我们之前分析，offerFirst、offerLast只是增加了返回值true，所以就不额外分析了。
好，今天我们先给出一些结论：
- ArrayDeque的底层是数组，默认长度是17，会自动扩容
- ArrayDeque的
addFirst相当于胆小鬼坐过山车抢后排座位，从后往前坐。当坐满人的时候，会自动扩容。- 自动扩容的规则是：在数组小于64长度时候，扩容原长度2倍+2；大于64时扩容50%。
- 扩容对溢出做了很多校验，尽量保证总长度不超过MAX_ARRAY_SIZE
- 扩容后，所有元素仍然处于新数组的末尾。
- 通过Head、Tail下标来添加元素，时间复杂度O(1)。
