雙端隊(duì)列是一個(gè)很有意思的話題装黑。在講并發(fā)雙端隊(duì)列之前限番，我們需要介紹一個(gè)非并發(fā)的ArrayDequeue扼褪， 讓大家理解雙端隊(duì)列的一些原理想幻。
- ArrayDeque不是線程安全的。
- ArrayDeque不可以存取null元素话浇，因?yàn)橄到y(tǒng)根據(jù)某個(gè)位置是否為null來(lái)判斷元素的存在脏毯。
- 當(dāng)作為棧使用時(shí)，性能比Stack好幔崖；當(dāng)作為隊(duì)列使用時(shí)食店，性能比LinkedList好。
從 ArrayDeque 命名就能看出他的實(shí)現(xiàn)基于數(shù)組（LinkedList 是基于鏈表實(shí)現(xiàn)的雙端隊(duì)列）赏寇，但是 ArrayDeque 的數(shù)組是一個(gè)可擴(kuò)容動(dòng)態(tài)數(shù)組吉嫩，每次隊(duì)列滿了就會(huì)進(jìn)行擴(kuò)容，除非擴(kuò)容至 int 邊界才會(huì)拋出異常蹋订，ArrayDeque 不允許元素為 null率挣。ArrayDeque 的主要成員是一個(gè) elements 數(shù)組和 int 的 head 與 tail 索引，head 是隊(duì)列的頭部元素索引露戒，而 tail 是隊(duì)列下一個(gè)要添加的元素的索引椒功，elements 的默認(rèn)容量是 16 且默認(rèn)容量必須是 2 的冪次，不足 2 的冪次會(huì)自動(dòng)向上調(diào)整為 2 的冪次智什。
- ArrayDeque 獲取隊(duì)列頭部元素的 element()\getFirst()\peek()\peekFirst() 操作动漾，其都是調(diào)用 getFirst() 實(shí)現(xiàn)的，訪問(wèn)隊(duì)列頭部元素但不刪除荠锭，即如下
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
- ArrayDeque 刪除隊(duì)列頭部元素的 remove()\removeFirst()\poll()\pollFirst() 操作旱眯，其都是調(diào)用 pollFirst() 實(shí)現(xiàn)的，移除隊(duì)列頭部元素且返回被移除的元素证九，即如下
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;
}
- ArrayDeque 添加元素到隊(duì)列尾部的操作可以發(fā)現(xiàn) add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是調(diào)用 addLast(E e) 實(shí)現(xiàn)的删豺，即如下：
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
addLast 的實(shí)現(xiàn)原理，也就是那句 if 操作與雙倍擴(kuò)容到底是做了什么我們先看下不擴(kuò)容情況下 ArrayDeque 相關(guān)操作的圖解愧怜，如下：
正如上圖中最后的多次操作結(jié)果所示呀页，如果此時(shí)我們?cè)?add 操作一個(gè)元素到 tail 索引處則 tail+1 會(huì)變成 8 導(dǎo)致數(shù)組越界，理論上來(lái)說(shuō)這時(shí)候應(yīng)該進(jìn)行擴(kuò)容操作了拥坛，但是由于下標(biāo)為 0蓬蝶、1尘分、2、3 處沒(méi)有存儲(chǔ)元素丸氛，直接擴(kuò)容有些浪費(fèi)（ArrayList 為了避免浪費(fèi)是通過(guò)拷貝將刪除之后的元素整體前挪一位）培愁，所以為了高效利用數(shù)組中現(xiàn)有的剩余空間就有了 addLast(E e) 中的代碼 (tail = (tail + 1) & (elements.length - 1)); 實(shí)質(zhì)類似上面 pollFirst() 里面 head 操作，即假設(shè) elements 默認(rèn)初始化長(zhǎng)度是 8缓窜，則當(dāng)前 tail + 1（8=1000）按位與上數(shù)組長(zhǎng)度減一（7=0111）的結(jié)果為十進(jìn)制的 0定续，所以下一個(gè)被 addLast(E e) 的元素實(shí)際會(huì)放在索引為 0 的位置，再下一個(gè)會(huì)放在索引為 1 的位置雹洗，如下圖：
問(wèn)題： (tail = (tail + 1) & (elements.length - 1)) 這個(gè)哪里見(jiàn)過(guò)香罐，是不是在LongAdder里線程probe找cell 那個(gè)邏輯？ 這句話實(shí)際上就是對(duì)element.length 取余
可以看到时肿，隨著出隊(duì)入隊(duì)不斷操作庇茫，如果 tail 移動(dòng)到 length-1 之后數(shù)組的第一個(gè)位置 0 處沒(méi)有元素則需要將 tail 指向 0，依次循環(huán)螃成，當(dāng) tail 如果等于 head 時(shí)說(shuō)明數(shù)組要滿了旦签，接下來(lái)需要進(jìn)行數(shù)組擴(kuò)容，所以就有了上面 addLast(E e) 里面那個(gè) if 判斷的邏輯去觸發(fā) doubleCapacity()寸宏。因此這也就解釋了為什么 ArrayDeque 的初始容量必須是 2 的冪次（擴(kuò)容每次都是成倍的宁炫，所以自然也滿足 2 的冪次），因?yàn)橹挥腥萘繛?2 的冪次時(shí) ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二進(jìn)制最高位永遠(yuǎn)為 0氮凝，當(dāng) (tail + 1) 與其按位與操作時(shí)才能保證循環(huán)歸零置位羔巢。ArrayDeque 的 doubleCapacity() 擴(kuò)容操作的實(shí)現(xiàn)，如下：
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;
}
