準備知識
因為ArrayDeque使用了循環(huán)隊列，所以首先要了解循環(huán)隊列數(shù)據(jù)結構的原理。
http://www.reibang.com/p/5fa1d2234045
屬性
// 存儲E類型元素的數(shù)組
private transient E[] elements;
// 循環(huán)隊列的頭元素索引
private transient int head;
// 循環(huán)隊列的尾元素索引
private transient int tail;
// 循環(huán)隊列的初始化最小容量為8
private static final int MIN_INITIAL_CAPACITY = 8;
構造方法
// 構造一個空的數(shù)組循環(huán)隊列冕房，初始化Object數(shù)組長度為16
public ArrayDeque() {
elements = (E[]) new Object[16];
}
// 構造一個指定長度的數(shù)組循環(huán)隊列
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 分配指定元素長度的Object數(shù)組
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];
}
// 構造一個包含指定 collection 的元素的循環(huán)隊列
public ArrayDeque(Collection<? extends E> c) {
// 先分配集合c那么長的空間
allocateElements(c.size());
// 將c中的元素插入到雙端隊列中
addAll(c);
}
/**
* 插入集合c中的所有元素躏啰，設置標記位modified代表是否插入元素。
* 如果插入元素了就返回標記位為true耙册。
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
// 在隊列的尾部插入元素e
public boolean add(E e) {
addLast(e);
return true;
}
public void addLast(E e) {
// 如果插入的元素為空给僵，那么就拋出空指針異常
if (e == null)
throw new NullPointerException();
// 在隊列的尾部插入元素
elements[tail] = e;
/**
* 按照循環(huán)隊列的特點，隊滿時采用(tail+1)%elements.length==head,而在此處使用了與位運算來代替取余運算详拙，由于位運算速度快帝际，所以這種方式效率高。
* 而此處代碼的意思是如果循環(huán)隊列已經達到了隊滿的狀態(tài)饶辙，那么就進行擴容操作蹲诀、并且賦值。
*/
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
// 將隊列擴充原來的2倍弃揽，并且將元素復制到擴充的數(shù)組中脯爪。
private void doubleCapacity() {
assert head == tail;
// 設置暫時變量p，如果直接操作head矿微，那么就會修改head痕慢。而本意是操作head而不修改head。
int p = head;
int n = elements.length;
// head右邊元素的個數(shù)
int r = n - p; // number of elements to the right of p
// 設置新容量涌矢，左移一位就相當于擴充為原來的2倍掖举。
int newCapacity = n << 1;
// 如果新容量的小于0,那么就會拋出非法狀態(tài)異常。
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
// 創(chuàng)建新容量的Object數(shù)組
Object[] a = new Object[newCapacity];
// 將elements元素復制到數(shù)組a中蒿辙，從elements數(shù)組的p開始拇泛，數(shù)組a從0開始，復制的長度為r
System.arraycopy(elements, p, a, 0, r);
// 將elements元素復制到數(shù)組a中思灌，從elements數(shù)組的0開始俺叭，數(shù)組a從r開始，復制的長度為p
System.arraycopy(elements, 0, a, r, p);
// 將新數(shù)組a賦值給elements
elements = (E[])a;
// 然后設置新數(shù)組的頭索引為0.尾索引為n
head = 0;
tail = n;
}
方法
addFirst方法：在隊列的頭部插入元素e泰偿。
public void addFirst(E e) {
// 如果插入元素為空熄守，那么就拋出空指針異常
if (e == null)
throw new NullPointerException();
// 與位運算代替取余運算，計算出新的頭索引的值耗跛，進行插入元素e
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果頭索引和尾索引重合裕照，達到了循環(huán)隊列的隊滿狀態(tài)，就進行擴容賦值操作
if (head == tail)
doubleCapacity();
}
remove方法：獲取并移除此雙端隊列所表示的隊列的頭调塌。
public E remove() {
return removeFirst();
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
public E pollFirst() {
int h = head;
E result = elements[h];
// 如果頭索引下標對應的元素為空晋南，那么就返回空
if (result == null)
return null;
// 將頭索引處的元素設置為空
elements[h] = null;
// 將頭索引對應的空元素，與運算計算出新的索引值
head = (h + 1) & (elements.length - 1);
return result;
}
總結
1. ArrayDeque采用循環(huán)隊列數(shù)據(jù)結構設計的羔砾。（所以增加负间、刪除偶妖、判斷隊空、判斷隊滿都是循環(huán)隊列的套路）
2. ArrayDeque增加元素政溃，如果循環(huán)隊列容量不夠趾访，那么就擴容為原來的2倍。
3. ArrayDeque采用與位運算來代替求余運算董虱，提高了效率扼鞋。（用在判斷隊滿的時候）
