Java深海拾遗系列（3）---JDK8中的ArrayDeque源码分析
ArrayDeque类视图
简介
从类视图可以看出，ArrayDeque实现了Deque接口，Deque接口继承了Queue接口，Queue接口继承自*接口集合类Collection。
Queue 也是 Java 集合框架中定义的一种接口，直接继承自 Collection 接口。除了基本的 Collection 接口规定测操作外，Queue 接口还定义一组针对队列的特殊操作。通常来说，Queue 是按照先进先出(FIFO)的方式来管理其中的元素的，但是优先队列是一个例外。
Deque 接口继承自 Queue接口，但 Deque 支持同时从两端添加或移除元素，因此又被成为双端队列。鉴于此，Deque 接口的实现可以被当作 FIFO队列使用，也可以当作LIFO队列（栈）来使用。官方也是推荐使用 Deque 的实现来替代 Stack。
ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque不支持值为 null 的元素。
Queue接口
- Queue是具有队列特性的接口
- Queue具有先进先出的特点
- Queue所有新元素都插入队列的末尾，移除元素都移除队列的头部
public interface Queue<E> extends Collection<E> {
//Inserts the specified element into this queue,throwing an IllegalStateException if no space is currently available.
boolean add(E e);
//Inserts the specified element into this queue,return false if no space is currently available.
boolean offer(E e);
//removes the head of this queue,return the head of this queue, or NoSuchElementException if this queue is empty
E remove();
//removes the head of this queue,return the head of this queue, or null if this queue is empty
E poll();
//not remove,return the head of this queue,throws NoSuchElementException if this queue is empty
E element();
//not remove,return the head of this queue, or null if this queue is empty
E peek();
}画成以下表格
| 操作 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入 | add() | offer() |
| 删除 | remove() | poll() |
| 查询 | element() | peek() |
Deque
- Deque是一个双端队列
- Deque继承自Queue
- Deque具有先进先出或后进先出的特点
- Deque支持所有元素在头部和尾部进行插入、删除、获取
public interface Deque<E> extends Queue<E> {
void addFirst(E e);//插入头部，异常会报错
boolean offerFirst(E e);//插入头部，异常返回false
E getFirst();//获取头部，异常会报错
E peekFirst();//获取头部，异常不报错
E removeFirst();//移除头部，异常会报错
E pollFirst();//移除头部，异常不报错
void addLast(E e);//插入尾部，异常会报错
boolean offerLast(E e);//插入尾部，异常返回false
E getLast();//获取尾部，异常会报错
E peekLast();//获取尾部，异常不报错
E removeLast();//移除尾部，异常会报错
E pollLast();//移除尾部，异常不报错
}画成以下表格，只不过Deque是有头部和尾部的
| 操作 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入 | add() | offer() |
| 删除 | remove() | poll() |
| 查询 | element() | peek() |
ArrayDeque
- 实现于Deque，拥有队列或者栈特性的接口
- 实现于Cloneable，拥有克隆对象的特性
- 实现于Serializable，拥有序列化的能力
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable{}ArrayDeque底层结构
/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* 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 equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
*/
private static final int MIN_INITIAL_CAPACITY = 8;ArrayDeque底层使用数组存储元素，同时还使用head和tail来表示索引，但注意tail不是尾部元素的索引，而是尾部元素的下一位，即下一个将要被加入的元素的索引
ArrayDeque的初始化
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = 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);
}
/**
* Constructs a deque containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator. (The first element returned by the collection's
* iterator becomes the first element, or <i>front</i> of the
* deque.)
*
* @param c the collection whose elements are to be placed into the deque
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(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
}
return initialCapacity;
}
在初始化中，数组要求的大小必须为2^n，所以有这么一个算法，如果当前的大小大于默认规定的大小时，就会去计算出新的大小，那么这个计算过程是怎么样的呢？>>>是无符号右移操作，|是位或操作，经过五次右移和位或操作可以保证得到大小为2^k-1的数。举例子进行分析
如果initialCapacity为10的时候，那么二进制为 1010
经过initialCapacity |= (initialCapacity >>> 1)时，那么二进制为 1010 | 0101 = 1111
经过initialCapacity |= (initialCapacity >>> 2)时，那么二进制为 1111 | 0011 = 1111
后面计算的结果都是1111，可以理解为将二进制的低位数都补上1，这样出来的结果都是2^n-1
最后initialCapacity++，2^n-1+1出来的结果就是2^n
这里又有人会有疑问了，为什么initialCapacity>>>16，右移到5位就可以结束呢？那是因为用的是|=符号，从右移1位到5位累加，其实就是整体右移了15位，刚好int值是16位的数，这就刚好满足16位二进制的低位都被补上了1。在进行5次位移操作和位或操作后就可以得到2^k-1，最后加1即可。这个实现还是很巧妙的。
ArrayDeque的插入
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//tail中保存的是即将加入末尾的元素的索引
elements[tail] = e;
//tail向后移动一位
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
//tail和head相遇，空间用尽，需要扩容
doubleCapacity();
}
在存储的过程中，这里有个有趣的算法，就是tail的计算公式(tail = (tail + 1) & (elements.length - 1))，注意这里的存储采用的是环形队列的形式，也就是当tail到达容量最后一个的时候，tail就为等于0，否则tail的值tail+1
(tail = (tail + 1) & (elements.length - 1))
证明：(elements.length - 1) = 2^n-1 即二进制的所有低位都为1，假设为 11111111
假设：tail为最后一个元素，则(tail + 1)为 (11111111 + 1) = 100000000
结果：(tail + 1) & (elements.length - 1) = 000000000，tail下一个要添加的索引为0
其插入过程中，如果刚好是最后一个元素时，示例如下图
那么为什么(tail + 1) & (elements.length - 1)就能保证按照环形取得正确的下一个索引值呢？这就和前面说到的 ArrayDeque 对容量的特殊要求有关了。下面对其正确性加以验证：
1 2 3 4 5 |
length = 2^n，二进制表示为: 第 n 位为1，低位 (n-1位) 全为0 length - 1 = 2^n-1，二进制表示为：低位(n-1位)全为1 如果 tail + 1 <= length - 1，则位与后低 (n-1) 位保持不变，高位全为0 如果 tail + 1 = length，则位与后低 n 全为0，高位也全为0，结果为 0 |
可见，在容量保证为 2^n 的情况下，仅仅通过位与操作就可以完成环形索引的计算，而不需要进行边界的判断，在实现上更为高效。
ArrayDeque的扩容
private void doubleCapacity() {
assert head == tail; //扩容时头部索引和尾部索引肯定相等
int p = head;
int n = elements.length;
//头部索引到数组末端(length-1处)共有多少元素
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 = a;
//重置头尾索引
head = 0;
tail = n;
}其扩容的过程如下图
ArrayDeque的删除
ArrayDeque支持从头尾两端移除元素，remove方法是通过poll来实现的。因为是基于数组的，在了解了环的原理后这段代码就比较容易理解了
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;
}
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;
}ArrayDeque的查询
@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)];
}总结
ArrayDeque是Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于Stack；ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的LinkedList也要更好一些
参考：
1，https://blog.csdn.net/qq_30379689/article/details/80558771