ArrayDeque
原文見Java 容器源碼分析之 Deque 與 ArrayDeque氢卡。
概述
ArrayDeque是Deque接口的一個實現(xiàn)，使用了可變數(shù)組镇饺，所以沒有容量上的限制愿卸。同時抄瓦，ArrayDeque是線程不安全的，在沒有外部同步的情況下蚕泽，不能再多線程環(huán)境下使用蛇更。ArrayDeque是Deque的實現(xiàn)類，可以作為棧來使用赛糟，效率高于Stack派任；也可以作為隊列來使用，效率高于LinkedList璧南。需要注意的是掌逛，ArrayDeque不支持null值。
結構
//用數(shù)組存儲元素
transient Object[] elements; // non-private to simplify nested class access
//頭部元素的索引
transient int head;
//尾部下一個將要被加入的元素的索引
transient int tail;
//最小容量司倚，必須為2的冪次方
private static final int MIN_INITIAL_CAPACITY = 8;
在ArrayDeque底層使用了數(shù)組來存儲數(shù)據(jù)豆混，同時用兩個int值head和tail來表示頭部和尾部。不過需要注意的是tail并不是尾部元素的索引动知，而是尾部元素的下一位皿伺，即下一個將要被加入的元素的索引。
初始化
ArrayDeque有三個構造函數(shù)來初始化盒粮，除了無參的構造函數(shù)使用了默認容量鸵鸥，其它兩個構造函數(shù)會通過allocateElements來計算初始容量。
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
ArrayDeque 對數(shù)組的大小(即隊列的容量)有特殊的要求丹皱，必須是 2^n妒穴。我們來看一下allocateElements方法。
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];
}
這里的實現(xiàn)很有意思摊崭，對于一個小于2^30的值讼油，經(jīng)過五次右移和位或操作后，可以得到一個2^k - 1的值呢簸。最后再將這個值+1矮台，得到2^k。通過這個方法根时，可以將一個任意的初始值轉化為2^n的值瘦赫，不過有一點不足在于，如果本身傳進來的值就是2^n的值啸箫，那么經(jīng)過轉化會變成2^(n+1)耸彪，所以我們在不用刻意去傳入2^n的值。還有一點在于忘苛，如果傳入的值大于等于2^30蝉娜，那么經(jīng)過轉化會變成負值唱较，即< 0，此時會把初始值設置為2^30召川，即最大的容量只有2^30南缓。
添加元素
向末尾添加元素
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//tail 中保存的是即將加入末尾的元素的索引
elements[tail] = e;
//tail 向后移動一位
//把數(shù)組當作環(huán)形的，越界后到0索引
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
//tail 和 head相遇荧呐，空間用盡汉形，需要擴容
doubleCapacity();
}
在ArrayDeque中，數(shù)組是作為環(huán)形來使用的倍阐，正常情況下在末尾添加元素后概疆，tail=tail+1是要判斷是否越界，如果越界峰搪，會變?yōu)閺乃饕?code>0開始岔冀。參考如下圖片，當H添加到索引7后概耻，tail值會+1,此時tail=8使套，但是越界了，所以應該將tail設置為0鞠柄。
但是為什么這里并沒有判斷越界呢侦高？關鍵在于(tail = (tail + 1) & (elements.length - 1)) == head這段代碼。這段代碼可以拆分為tail = (tail + 1) & (elements.length - 1)和tail == head厌杜，這樣會比較清晰奉呛，前一段代碼是為了獲取正確的tail索引值，后一段代碼是為了判斷數(shù)組是否滿了期奔。之前要求數(shù)組的大小必須為2^n值侧馅，就是為了能夠不通過條件判斷危尿，直接使用位操作在環(huán)形數(shù)組中獲取下一個正確的索引值呐萌。
我們驗證一下tail = (tail + 1) & (elements.length - 1)的正確性：
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
所以當tail+1 <= length - 1茫叭，此時數(shù)組并沒有越界，(tail + 1) & (elements.length - 1)后得到的還是tail+1半等。如果tail + 1 = length揍愁，此時數(shù)組越界了呐萨，(tail + 1) & (elements.length - 1)后得到0。
所以通過(tail + 1) & (elements.length - 1)可以跳過條件判斷在環(huán)形數(shù)組中獲取正確的索引值莽囤，然后再判斷新的tail是否等于head谬擦，如果結果為true，那么數(shù)組已經(jīng)滿了朽缎，需要擴容惨远，即doubleCapacity()。
向頭部添加元素
public void addFirst(E e) {
if (e == null) //不支持值為null的元素
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
其實向頭部添加元素和向尾部添加元素原理是相同的话肖，都是通過位操作高效獲取新的索引值北秽。
擴容
無論是從頭部還是從尾部添加元素，都會判斷tail==head最筒，如果兩個索引相遇羡儿，說明數(shù)組空間已滿，需要擴容操作是钥。見下圖：
private void doubleCapacity() {
assert head == tail; //擴容時頭部索引和尾部索引肯定相等
int p = head;
int n = elements.length;
//頭部索引到數(shù)組末端(length-1處)共有多少元素
int r = n - p; // number of elements to the right of p
//容量翻倍掠归，相當于 2 * n
int newCapacity = n << 1;
//容量過大，溢出了
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
//分配新空間
Object[] a = new Object[newCapacity];
//復制頭部索引到數(shù)組末端的元素到新數(shù)組的頭部
System.arraycopy(elements, p, a, 0, r);
//復制其余元素
System.arraycopy(elements, 0, a, r, p);
elements = a;
//重置頭尾索引
head = 0;
tail = n;
}
移除元素
ArrayDeque支持從頭尾兩端移除元素悄泥，remove方法是通過poll來實現(xiàn)的虏冻。因為是基于數(shù)組的，在了解了環(huán)的原理后這段代碼就比較容易理解了弹囚。
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;
}
