目录
1. ArrayDeque
Deque
是双端队列，既可以从队列头部增删元素，也可以从队列尾部增删元素。
ArrayDeque
是用数组实现的双端队列。
因为数组元素的位置是固定的，所以进行
头插
时，一般情况下常人思维就是把队列内已有的元素统一向后移动，给队首腾出地方。
但是这种操作耗时严重，所以本文的主角
ArrayDeque
就体现出了它的设计精妙之处。
public class ArrayDeque {
Object[] elements; // 默认长度16，后续扩容总是2的整数次幂（重要）
int head; // 指向队首元素索引，初始值0
int tail; // 指向队尾元素索引，初始值0
}
2. 新增
ArrayDeque
初始状态如下
2.1 只有头插
ArrayDeque
的头插不是直接插到头上，它做了这个操作
elements[head = (head - 1) & (elements.length - 1)] = e
分解一下
int index = (head - 1) & (elements.length - 1); // -1 & 15 = 15
head = index; //head = 15，tail = 0
elements[index] = e;
头插头插嘛，就得在当前队首前面插一个元素，但是直接
head - 1
会出问题，索引会变成负数，所以经过跟
elements.length
取余数后，得到的值就变成了正数，而且还是数组最后一个索引。
这么搞的好处是，避免了每次头插都将已有元素向后移动，时间花销变成常数级！
连续头插13次，会发现每次头插完毕
head
的值的变化是这样的
head = 15, 14, 13, ……, 3
直到
head
撞上
tail
，然后就该扩容了，后面说如何扩容。
2.2 只有尾插
elements[tail] = e;
tail = (tail + 1) & (elements.length - 1); //防止索引越界
连续尾插3次，会发现每次尾插完毕
tail
的值的变化是这样的
tail = 0, 1, 2, 3
直到
tail
撞上
head
，然后扩容。
2.3 头尾交插
根据上面两种插入元素的方式，即使是头尾交替插入元素也不会碰撞。
下图中
绿色
的表示头插元素，
黄色
的表示尾插元素
头 = 1
尾 = 2
头 = 3
尾 = 4
头 = 5
尾 = 6
头 = 7
尾 = 8
最后双端队列的
正向
遍历顺序是
7 5 3 1 2 4 6 8
3. 扩容
ArrayDeque
每次双倍扩容。
ArrayDeque
内部数组默认容量是16，为了方便演示，下面将默认容量修改为8，当数组被塞满后，扩容到16。
4. 删除
理解了
头插
和
尾插
原理后，删除操作只需
+ 变 -
- 变 +
4.1 删头
头插
是先对
head
做运算，然后再添加；添加完毕后
head
就指向首元素
删头
是先删
head
指向元素，然后把
head
指针向后移
// 头插
elements[head = (head - 1) & (elements.length - 1)] = e;
// 删头
E e = elements[head]; // 取出做备份
if (e == null) return null; // 证明队列已空 head == tail == null
elements[head] = null; // 释放槽位，避免内存泄漏
head = (head + 1) & (elements.length - 1); // 向后移动 head 指针
return e;
4.2 删尾
尾插
是先添加，后对
tail
做运算；添加完毕后
tail
指向下一个空闲位置
删尾
是先把
tail
指针向前移，然后删除
tail
指向元素
// 尾插
elements[tail] = e;
tail = (tail + 1) & (elements.length - 1);
// 删尾
int t = (tail - 1) & (elements.length - 1); // 向前移动 tail 指针
E e = elements[t]; // 取出做备份
if (e == null) return null; // 证明队列已空 tail == head == null
elements[t] = null; // 释放槽位，避免内存泄漏
tail = t;
return e;
5. 遍历
既然是双端队列，那必然有两种遍历方式：正向遍历（head > tail）和逆向遍历（tail > head）
ArrayDeque
没有实现
java.util.List
接口，所以不能按索引遍历，只能通过迭代器遍历
5.1 正向遍历
ArrayDeque
为了屏蔽内部实现细节，提供了
java.util.Iterator
的内部实现类
DeqIterator
，供外部正向遍历（head > tail）
正如你所想的一样，额外定义一个变量
cursor
最初指向
head
hasNext()
判断
cursor != tail
时才能
next()
next()
把
cursor
指向的元素返回给你，然后
cursor = (cursor + 1) & (elements.length - 1)
5.2 逆向遍历
ArrayDeque
提供了另一个内部类
DescendingIterator
，它同样实现了
java.util.Iterator
，用于逆向遍历（tail > head）
额外定义一个变量
cursor
最初指向
tail
hasNext()
判断
cursor != head
时才能
next()
next()
先
cursor = (cursor - 1) & (elements.length - 1)
，然后把
cursor
指向的元素返回给你
5.3 遍历删除
最后再补充一点。
迭代器遍历很简单，那如果想在迭代过程中删除元素怎么办呢？
废话，当然是使用 iterator.remove() 了
数组毕竟是数组，如果想删除中间部分的元素，而非头、尾元素，依然避免不了移动元素的操作
ArrayDeque
为了尽量减少移动元素的个数，在
delete()
方法内写了点
人类友好型
代码，不过我并不想分享出来，
一是因为它虽然简短，但是没有完全实现任何情况下都能达到它这么做的初衷；
二是因为我相信有一部分人看过这个方法之后，也会有像我写这篇博客时的心情。
如果让我设计，我也会考虑到移动元素过多影响效率的问题，虽然我写不出官方代码，但是思路都是差不多的~~。
5.3.1 一边倒
只进行
头插 / 尾插
，使
head = 0 / tail = 0
例如下面这种情况，想删除
4
，正常人想的肯定都是把
3 2 1
往前挪，然后
elements[tail = elements.length - 1] = null
如果你也是这么想的，那纯属雷同。
如果想删除
10
，就把
13 12 11
往后挪，然后
elements[head] = null; head++;
5.3.2 两边散
最麻烦的就是这样的，想删除
5
，就得判断
min(index - head, elements.length - index + tail)
说白了就是判断
index
离哪个指针更近，就移动哪边的元素
如果不幸的离
tail
更近，最多需要复制两次数组 —— 先把
[index ~ elements.length-1]
补齐，再折腾
[0 ~ tail-1]
画图不易，还请自行脑部，感谢浏览本文！
Over