概述
??首先解釋下躺屁，Queue（隊列）肯夏，隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)（First In First Out，F(xiàn)IFO）犀暑，經(jīng)常和棧一起討論驯击，而棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)（FILO）。隊列有頭指針head和尾指針tail耐亏，數(shù)據(jù)從隊尾入隊徊都，從隊頭出隊。費盡心力广辰，畫了一張圖暇矫，真是靈魂畫手。
??而Deque被稱為雙端隊列择吊，隊列的原則是只能一頭入隊李根，一頭出隊，而雙端隊列則是兩端都可以入隊和出隊的隊列几睛。隊列和棧兩者很像房轿，所以像我們今天要學(xué)習(xí)的這個ArrayDeque，就同時實現(xiàn)了它們兩個的功能，可以稱為是一種基于數(shù)組的雙端隊列囱持。
我們可以先看下文檔：
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
通過文檔和我們實際使用夯接，我們大概知道ArrayDeque隊列有以下性質(zhì)：
- 首先該類是JDK1.6才引入的，算引入的比較晚了纷妆，在以前版本的話钻蹬，要使用隊列的功能，一般要用LinkedList凭需，或者自己封裝實現(xiàn)问欠；
- 隊列不是線程安全的，并且不允許元素為空粒蜈；
- 當(dāng)用作堆棧時顺献，這個類的速度可能比堆棧快枯怖，當(dāng)用作隊列時注整，它比LinkedList更快；
- 隊列底層是由數(shù)組來實現(xiàn)的度硝，沒有容量限制肿轨，并且數(shù)組容量可以自動進行擴容。
- 隊列有兩個指針蕊程，頭指針和尾指針椒袍，我們對隊列進行的操作一般都是通過操作這兩個指針進行的。
- 為了滿足可以同時在數(shù)組兩端進行插入和移除操作藻茂，該數(shù)組還必須是一個循環(huán)的數(shù)組驹暑，也就是說數(shù)組的任何一點都可以看作起點和終點。
繼承結(jié)構(gòu)和屬性
public interface Deque<E> extends Queue<E> {
}
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
// 隊列中存放數(shù)據(jù)的數(shù)組
transient Object[] elements;
// 頭指針辨赐，或頭索引
transient int head;
// 尾指針优俘，或尾索引
transient int tail;
// 最小初始化數(shù)組容量
private static final int MIN_INITIAL_CAPACITY = 8;
}
從繼承結(jié)構(gòu)我們可以看出，Deque是繼承自Queue的掀序。
構(gòu)造方法
/**
* 默認構(gòu)造方法帆焕，初始容量為16
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 用戶指定數(shù)組容量
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
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 = new Object[initialCapacity];
}
??其中allocateElements方法是計算實際所需容量的。首先不恭，numElements是用戶指定的隊列大小叶雹，allocateElements中這么多無符號右移運算操作，只是為了計算離numElements最近的且大于numElements的2的次方县袱。比如浑娜，用戶指定隊列是15，那最終計算的結(jié)果就是2的4次方16式散。因為ArrayDeque規(guī)定，數(shù)組容量大小必須是2的冪打颤。
The capacity of the deque is the length of this array, which is always a power of two.
??首先暴拄，我們不妨想一下漓滔，對于用戶指定的大小numElements，那離它最近的且大于numElements的2的次方應(yīng)該是多少呢乖篷。
??仔細想了之后响驴，我們就會發(fā)覺，這個值應(yīng)該是我們就將numElements轉(zhuǎn)為二進制后撕蔼，該二進制所有位都是1豁鲤，然后再加1的值。比如numElements是10001鲸沮，那距離它最近的那個值就將是11111 + 1琳骡。
initialCapacity |= (initialCapacity >>> 1);這里是將高2位設(shè)置為1；initialCapacity |= (initialCapacity >>> 2);這里是將高4位設(shè)置為1讼溺；initialCapacity |= (initialCapacity >>> 4);這里是將高8位設(shè)置為1楣号；initialCapacity |= (initialCapacity >>> 8);這里是將高16位設(shè)置為1；initialCapacity |= (initialCapacity >>> 16);這里是將高32位怒坯，也就是int的全部位設(shè)置為1炫狱。- 這樣，最終所有的位都變?yōu)榱?剔猿，然后再加1就是2的次冪了视译。
addFirst和addLast
分別在頭部和尾部插入元素：
/**
* 在隊列頭部插入元素，也就是在head之前位置插入元素
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果兩者相等归敬，說明數(shù)組已經(jīng)放滿了元素憎亚，需要擴容
if (head == tail)
doubleCapacity();
}
/**
* 在隊列尾部插入元素，也就是在tail位置插入元素
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
??在頭部插入元素弄慰，也就是在head之前第美，head自減之后然后進行位與操作。因為elements.length一直是2的次冪陆爽，所以elements.length-1之后的二進制全是1什往，所以這里就相當(dāng)于進行的是取余操作。而在尾部插入的話慌闭，其實和頭部類似别威，只不過是直接插入到了尾部，然后tail加1驴剔。添加完之后省古，兩個方法都會檢測數(shù)組是否已滿，如果滿了丧失，則進行擴容操作豺妓。這里判斷是否已滿的條件是head == tail。
doubleCapacity方法
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
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;
}
這里，大概分以下幾個步驟：
- 檢測tail是否等于head琳拭；
- 創(chuàng)建一個原數(shù)組容量2倍的新數(shù)組训堆；
3 將原數(shù)組從head位置一分為二，分別拷貝到新數(shù)組中白嘁；比如數(shù)組容量16坑鱼，head位置是7，則先將原數(shù)組下標從7開始絮缅，拷貝16-7個元素到新的下標從0開始鲁沥，元素個數(shù)為16-7的數(shù)組中。然后將原數(shù)組下標從0開始到7的元素拷貝到新數(shù)組下標從（16-7）開始耕魄，元素個數(shù)是7的數(shù)組中画恰。這么做的目的就是為了拷貝到新數(shù)組的時候保持元素原來的順序。- 重新確定頭尾指針的位置屎开。
??與之相關(guān)聯(lián)的兩個方法 offerFirst 和 offerLast 方法阐枣，和addFirst，addLast唯一不同的是提供了是否添加成功的返回值奄抽。當(dāng)然蔼两，都是返回的true。
pollFirst和pollLast
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;
}
??這兩個方法其實沒什么好說的逞度，就是分別移除頭部和尾部的元素并返回該元素额划。另外，removeFirst档泽，removeLast 這兩個方法也是移除并返回元素俊戳，和pollFirst不同的是該接口會判斷返回的值是否為null，如果為null馆匿，就拋出異常抑胎。也就是說，該方法不允許要移除的元素為null渐北。
??還有兩個方法阿逃，peekFirst，peekLast也是返回頭元素或尾元素赃蛛，只是不移除元素恃锉。
remove，removeFirstOccurrence方法
public boolean remove(Object o) {
return removeFirstOccurrence(o);
}
/**
* 遍歷查找數(shù)據(jù)呕臂，然后在隊列中刪除該數(shù)據(jù)
*/
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;
}
- remove方法是刪除隊列中的指定元素破托，內(nèi)部調(diào)用的是removeFirstOccurrence。這個方法是刪除指定元素第一次出現(xiàn)的位置歧蒋，該方法內(nèi)部是通過遍歷查詢該元素土砂，遍歷的方向是從head下標到tail下標州既。
- 同樣，和該方法類似的還有removeLastOccurrence方法瘟芝，該方法是刪除指定元素最后一次出現(xiàn)的位置易桃，計算方式和removeFirstOccurrence恰好相反褥琐。
- 根據(jù)隊列的定義锌俱，隊列中一般不建議刪除既非隊頭也非隊尾的元素，要刪除一般都是使用removeFirst或pollFirst就滿足了敌呈，所以這兩個方法并不經(jīng)常用贸宏，并且這兩個方法的查詢都是線性時間。
size和isEmpty
/**
* 計算隊列的長度
*/
public int size() {
return (tail - head) & (elements.length - 1);
}
/**
* 通過判斷head是否等于tail來判斷隊列是否為空
*/
public boolean isEmpty() {
return head == tail;
}
??至于getFirst磕洪，getLast吭练，peekFirst，peekLast這些就是獲取元素的方法析显，當(dāng)然ArrayDeque還實現(xiàn)了隊列Queue的各個方法鲫咽。比如add，offer谷异，remove等等分尸，這些方法基本上都是調(diào)用以上Deque的方法實現(xiàn)的，沒什么好說的歹嘹。
??ArrayDeque也提供了一些轉(zhuǎn)換為數(shù)組的方法箩绍，底層是通過System.arraycopy實現(xiàn)的，不過這些都挺簡單的尺上，就不一一說了材蛛。
總結(jié)
- 一般情況下，ArrayDeque的效率還是挺高的怎抛，大多數(shù)方法都是在常數(shù)時間內(nèi)運行卑吭，除了一些例如removeFirstOccurrence，removeLastOccurrence和一些批量操作是線性時間马绝。
- 雖然LinkedList也提供了Deque的實現(xiàn)豆赏，不過官方還是建議我們使用ArrayDeque來實現(xiàn)隊列的功能。所以如果我們有類似的功能迹淌，建議使用ArrayDeque來實現(xiàn)河绽。
本文參考自：
ArrayDeque源碼分析
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
