1 ArrayDeque简介
通过名称我们可以知道ArrayDeque是Java中使用数组实现的双端队列。是用作队列、双端队列、栈的绝佳选择。
1.1 如何理解“栈”
关于“栈”，一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
1.2 如何“理解队列“
队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。
相对于栈只支持两个基本操作：入栈 push()和出栈 pop()，对于也只支持两个操作入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素，因此队列跟栈一样，也是一种操作受限的线性表数据结构
1.3 如何理解“双端队列”
Deque 全称为double ended queue，即双向队列，相对于队列它提供了更强大的功能.它允许在队列两侧插入或删除元素。因此deque实现不仅仅能能作为队列【先进先出FIFO(first in first out)】使用，还能作为栈【后入先出LIFO(last in first out)使用】。
1.4 Java中双端队列“接口”
2 数组实现队列
队列的数组实现需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。结合下面这幅图来理解。当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。
当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。
你肯定已经发现了，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，
也无法继续往队列中添加数据了。这个问题该如何解决呢？
2.1 循环队列
循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。
我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：
通过这样的方法，我们成功避免了数据搬移操作。但是循环队列最关键的是，确定好队空和队满的判定条件。
在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？
方式一
就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时满足以下公式 ：(tail+1)%n=head。
当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
3 数组实现双端队列
还是循环队列队列为例，双端队列相对于普通队列，支持头部插入队，尾部出队
3.1 入队操作
队首入队
图中这个队列的大小为 8，当前 head=0，tail=0。将一个元素a从队列头部入队，首先移动head指向下标为7的位置，之后将a放入head新指向位置7 （先移动后赋值）
队尾入队
和普通队列一样，将元素b 队尾入队时,首先将b值放入tail指向的位置0，移动head指向下标为1的位置 (先赋值后移动)
3.2 出队操作
队首出队
图中这个队列的大小为 8，当前 head=6，tail=2。队首出队时，首先将head指向的数据清空，之后移动head指向下标为7的位置。（先清理后移动）
队尾出队
和普通队列一样，队尾出队时，移动tail指向下标为1的位置，将tail指向的数据清空 (先赋值后移动)
3.3 扩容
新建一个原始数组2倍大小的数组，移动head,tail指向位置0，并将原始数组中数据按顺序插入新队列尾部。
3 ArrayDeque源码解析
3.1 内部成员变量
//容器capacity最小值，也是2的次幂（数组初始容量保证都时2的次幂，方便使用位运算）
private static final int MIN_INITIAL_CAPACITY = 8;
//存放数据数组，长度和capacity一致，并且总是2的次幂
transient Object[] elements;
//标记队首元素所在的位置
transient int head;
//标记队尾元素所在的位置
transient int tail;
3.2 构造函数
/**
* 构造一个初始容量为16的空队列
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 构造一个能容纳指定大小的空队列
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* 构造一个包含指定集合所有元素的队列
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
allocateElements方法主要用于给内部的数组分配合适大小的空间，大于等于最接近toSize的2的冪数
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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];
}
3.3 容量设置成2^n的幂好处？
任何一个数和2^n-1做&运算可以用在循环队列的数组中快速指针的位置。
一个负数x和2^n-1做&运算相当于 2^n-1-|x|
案例
System.out.println(Integer.toBinaryString(8 - 1));
System.out.println(Integer.toBinaryString((0 - 1) & (8 - 1)));
System.out.println((0 - 1) & (8 - 1));
System.out.println(Integer.toBinaryString((0 - 2) & (8 - 1)));
System.out.println((0 - 2) & (8 - 1));
//结果
00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000110
7
6
一个正数x和2^n-1做&运算相当于取余。
案例
System.out.println(Integer.toBinaryString((1) & (8 - 1)));
System.out.println(Integer.toBinaryString(( 2) & (8 - 1)));
System.out.println(( 1) & (8 - 1));
System.out.println(( 2) & (8 - 1));
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000010
1
2
3.4 入队
/** 在队首添加元素 **/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/** 在队首添加元素 **/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
/** 在队尾添加元素 **/
public boolean offerLast(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();
}
3.5 出队
/** 队首出队 **/
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];
if (result == null)
return null;
elements[h] = null;
head = (h + 1) & (elements.length - 1);
return result;
}
/** 队尾出队 **/
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
/** 队尾出队 **/
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
3.6 扩容
private void doubleCapacity() {
//只有head==tail时才可以扩容
assert head == tail;
int p = head;
int n = elements.length;
//在head之后，还有多少元素
int r = n - p; // number of elements to the right of p
//直接翻倍，因为capacity初始化时就已经是2的倍数了，这里无需再考虑
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 = a;
head = 0;
tail = n;
}
3.7 获取
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
@SuppressWarnings("unchecked")
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
@SuppressWarnings("unchecked")
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
}
3.8 其他
removeFirstOccurrence和removeLastOccurrence分别用于找到元素在队首或队尾第一次出现的位置并删除。其实现原理是一致的
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
这里就是遍历所有元素，然后通过delete方法删除，我们看看delete实现：
private boolean delete(int i) {
//检查
checkInvariants();
final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
//待删除元素前面的元素个数
final int front = (i - h) & mask;
//待删除元素后面的元素个数
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
//确认 i 在head和tail之间
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
//尽量最少操作数据
//前面数据比较少
if (front < back) {
if (h <= i) {
//这时 h 和 i 之间最近距离没有跨过位置0
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);
elements[0] = elements[mask];
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
if (i < t) { // Copy the null tail as well
//这时 t 和 i 之间最近距离没有跨过位置0
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
}
