引言
隊列楞抡、棧是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)中的兩種伟众，非常簡單，但也很重要召廷。隊列的規(guī)則是：先進先出（First In First Out, FIFO）凳厢；棧的規(guī)則是：先進后出(First In Last Out, FILO)。而在其它方面幾乎沒有差別竞慢，所以java中就有一個類同時實現(xiàn)了它們的功能先紫，即：ArrayDeque，直譯一下應(yīng)該可以叫基于數(shù)組的雙端隊列筹煮。
成員變量:
transient Object[] elements; // 數(shù)據(jù)載體遮精，長度始終為2的冪
transient int head;//頭指針
transient int tail;//尾指針
這里要注意的是：
- 這個隊列不允許元素為空；
- 數(shù)組至少有一個位置是空的败潦；
- head跟tail之間沒有絕對的大小關(guān)系本冲；
從它的設(shè)計上來看，我們可以把它看成一個循環(huán)數(shù)組劫扒，數(shù)組里存放的元素下標(biāo)區(qū)間因head與tail的關(guān)系而異檬洞，具體如下：
- head < tail:
[head : tail-1] - head > tail:
[head : elements.length()-1] + [0, tail-1] - head == tail:
隊列為空，也就是沒有存放任何元素
兩個構(gòu)造方法：
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
第一個很簡單沟饥，就是預(yù)申請長度為16的數(shù)組添怔；
再看第二個，numElements是指用戶指定的隊列長度贤旷，它調(diào)用了allocateElements(int 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];
}
前面幾句很好理解广料，如果numElements太小，那么隊列長度就取默認(rèn)初始化長度遮晚；
后面一坨代碼的意思：如果numElements大于默認(rèn)初始化長度性昭，就取最小的n使得：n = 2^k(k為整數(shù)), 且n > numElements拦止。
求n的方法有很多：從小到大枚舉k县遣、二分k等等糜颠；可能作者覺得這些方法都太low了，又熟練掌握二進制運算技巧萧求，于是才有了這幾行代碼其兴。
下面簡單分析一下代碼的運算過程，注：">>>"代表按位右移：
假設(shè)a=1xxxxxxxxxxxx...(base 2, x代表該位任意為0或1)
首先a |= (a >>> 1)之后夸政，a => 11xxxxxxxx...(最高兩位是1)
然后a |= (a>>> 2): a => 1111xxxxxxxxx...（最高四位是1）
再a |= (a>>> 4): a => 11111111xxxxxxx...（最高八位是1）
........
最終元旬，a的所有低位也都變成了1，即11111111...111(全是1)
再a++ 就變成了10000000000...000(加一之后進位守问，比原來的二進制串多了一位匀归，且第一位是1，其它位都是0)耗帕，這個算法不僅時間效率高穆端，而且只用到了一個變量，真可謂是短小精悍仿便，在HashMap里也可以看到這個算法的身影体啰。
兩個添加方法：
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();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
前面代碼很簡潔，剛開始做元素非空檢測嗽仪；加到頭部時荒勇，head自減并對數(shù)組長度取余，然后將元素存在head位置闻坚；加到尾部時沽翔，將元素存放在tail，再執(zhí)行tail自增并對數(shù)組長度取余鲤氢。最后再檢查隊列空間是否已滿搀擂，若已滿調(diào)用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;
}
這里主要做了這么幾件事：
- 先做各種合法性校驗；
- 申請新數(shù)組（長度擴大一倍）卷玉；
- 根據(jù)head和tail推算出元素的邏輯順序哨颂；
- 保持元素原來順序拷貝到新數(shù)組里；
- 重置頭尾指針相种。
這里稍微解釋一下代碼里的取余邏輯：
記mod = elements.length = 2^k, a為[-1,mod]之間的一個整數(shù)威恼，那么有：
- a == -1:
a & (mod-1) == mod - 1; - 0 <= a < mod:
a & (mod - 1) == a; - a == mod:
a & (mod - 1) == 0
兩個取首/尾元素并刪除的方法：
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;
}
它們分別就是從數(shù)組中取指定下標(biāo)的元素，并修改首/尾指針寝并，最后返回箫措。
再看兩個比較低效并且不怎么用的方法：
- removeFirst/LastOccurrence(Object o)方法：
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;
}
public boolean removeLastOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = (tail - 1) & mask;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i - 1) & mask;
}
return false;
}
從首/尾部開始遍歷，一直到找到相同的元素為止衬潦，再調(diào)用delete(int i)將其刪除斤蔓。delete方法里沒有太多技術(shù)含量的代碼，就不贅述了镀岛。
ArrayDeque里還有一些比如Iterator（比較簡單）弦牡，Spliterator（沒用過）的代碼友驮，這邊就不分析了。
總結(jié)
總體上來說驾锰，ArrayDeque的效率還是非常高的卸留，大部分操作如從首尾插入或者讀取都是O(1)的；但是隊列的容量必須為2的冪這一點可能會構(gòu)成很大的浪費椭豫。
比如耻瑟，假設(shè)我要用的隊列里元素最多的時候數(shù)量為2k，無論我們怎么努力赏酥，它會申請2(k+1)的長度喳整，足足浪費了一半。這與ArrayList大不相同裸扶。個人認(rèn)為算柳，數(shù)組長度必須為2的冪，它所帶來唯一的好處可能就是在取余的時候可以直接用位運算(&)來替代原本的取余操作(%)姓言，提高一點運算效率瞬项，不知道今后的jdk會不會對其進行優(yōu)化。
