今天來介紹一個不太常見也不太常用的類——ArrayDeque，這是一個很不錯的容器類，如果對它還不了解的話，那麼就好好看看這篇文章吧。
看完本篇，你将會了解到：
1、ArrayDeque是什麼？
2、ArrayDeque如何使用？
3、ArrayDeque的内部結構是怎樣的？
4、ArrayDeque的各個方法是如何實作的？
5、ArrayDeque是如何擴容的？
6、ArrayDeque的容量有什麼限制？
7、ArrayDeque和LinkedList相比有什麼優勢？
8、ArrayDeque的應用場景是什麼？
一、ArrayDeque簡介
ArrayDeque是JDK容器中的一個雙端隊列實作，内部使用數組進行元素存儲，不允許存儲null值，可以高效的進行元素查找和尾部插入取出，是用作隊列、雙端隊列、棧的絕佳選擇，性能比LinkedList還要好。聽到這裡，不熟悉ArrayDeque的你是不是有點尴尬？JDK中竟然還有這麼好的一個容器類？
别慌，現在了解還來得及，趁響指還沒有彈下去，快上車吧，沒時間解釋了。
來看一個ArrayDeque的使用小栗子：
public class DequeTest {
public static void main(String[] args){
// 初始化容量為4
ArrayDeque<String> arrayDeque = new ArrayDeque<>(4);
//添加元素
arrayDeque.add("A");
arrayDeque.add("B");
arrayDeque.add("C");
arrayDeque.add("D");
arrayDeque.add("E");
arrayDeque.add("F");
arrayDeque.add("G");
arrayDeque.add("H");
arrayDeque.add("I");
System.out.println(arrayDeque);
// 擷取元素
String a = arrayDeque.getFirst();
String a1 = arrayDeque.pop();
String b = arrayDeque.element();
String b1 = arrayDeque.removeFirst();
String c = arrayDeque.peek();
String c1 = arrayDeque.poll();
String d = arrayDeque.pollFirst();
String i = arrayDeque.pollLast();
String e = arrayDeque.peekFirst();
String h = arrayDeque.peekLast();
String h1 = arrayDeque.removeLast();
System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1);
System.out.println();
// 添加元素
arrayDeque.push(e);
arrayDeque.add(h);
arrayDeque.offer(d);
arrayDeque.offerFirst(i);
arrayDeque.offerLast(c);
arrayDeque.offerLast(h);
arrayDeque.offerLast(c);
arrayDeque.offerLast(h);
arrayDeque.offerLast(i);
arrayDeque.offerLast(c);
System.out.println(arrayDeque);
// 移除第一次出現的C
arrayDeque.removeFirstOccurrence(c);
System.out.println(arrayDeque);
// 移除最後一次出現的C
arrayDeque.removeLastOccurrence(c);
System.out.println(arrayDeque);
}
} 輸出如下：
[A, B, C, D, E, F, G, H, I]
a = A, a1 = A, b = B, b1 = B, c = C, c1 = C, d = D, i = I, e = E, h = H, h1 = H
[I, E, E, F, G, H, D, C, H, C, H, I, C]
[I, E, E, F, G, H, D, H, C, H, I, C]
[I, E, E, F, G, H, D, H, C, H, I] 可以看到，從ArrayDeque中取出元素的姿勢可謂是五花八門，不過别慌，稍後會對這些方法進行一一講解，現在隻需要知道，get、peek、element方法都是擷取元素，但是不會将它移除，而pop、poll、remove都會将元素移除并傳回，add和push、offer都是插入元素，它們的不同點在于插入元素的位置以及插入失敗後的結果。
二、ArrayDeque的内部結構
ArrayDeque的整體繼承結構如下：
ArrayDeque是繼承自Deque接口，Deque繼承自Queue接口，Queue是隊列，而Deque是雙端隊列，也就是可以從前或者從後插入或者取出元素，也就是比隊列存取更加友善一點，單向隊列隻能從一頭插入，從另一頭取出。
再來看看ArrayDeque的内部結構，其實從名字就可以看出來，ArrayDeque自然是基于Array的雙端隊列，内部結構自然是數組：
//存儲元素的數組
transient Object[] elements; // 非private通路限制，以便内部類通路
/**
* 頭部節點序号
*/
transient int head;
/**
* 尾部節點序号，（指向最後一點節點的後一個位置）
*/
transient int tail;
/**
* 雙端隊列的最小容量，必須是2的幂
*/
private static final int MIN_INITIAL_CAPACITY = 8; 這裡可以看到，元素都存儲在Object數組中，head記錄首節點的序号，tail記錄尾節點後一個位置的序号，隊列的容量最小為8，而且必須為2的幂。看到這裡，有沒有想到HashMap的元素個數限制也必須為2的幂，嗯，這裡同HashMap一樣，自有妙用，後面會有分析。
三、ArrayDeque的常用方法
| 從隊列首部插入/取出 | 從隊列尾部插入/取出 | |||
|---|---|---|---|---|
| 失敗抛出異常 | 失敗傳回特殊值 | |||
| 插入 | addFirst(e) push() | offerFirst(e) | addLast(e) | offerLast(e) |
| 移除 | removeFirst() pop() | pollFirst() | removeLast() | pollLast() |
| 擷取 | getFirst() | peekFirst() | getLast() | peekLast() |
嗯，幾乎絕大多數常用方法都在這裡了，基本上可以分成兩類，一類是以add，remove，get開頭的方法，這類方法失敗後會抛出異常，一類是以offer，poll，peek開頭的方法，這類方法失敗之後會傳回特殊值，如null。大部分方法基本上都是可以根據命名來推斷其作用，如addFirst，當然就是從隊列頭部插入，removeLast，便是從隊列尾部移除，get和peek隻擷取元素而不移除，getFirst方法調用時，如果隊列為空，會抛出NoSuchElementException異常，而peekFirst在隊列為空時調用則傳回null。
一下擺出這麼多方法有些難以接受？别慌别慌，接下來讓我們從源碼的角度一起來看看這些方法，用圖說話，來解釋我們最開始那個栗子中到底發生了哪些事情。
四、ArrayDeque源碼分析
先來看看構造函數：
/**
* 構造一個初始容量為16的空隊列
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 構造一個能容納指定大小的空隊列
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* 構造一個包含指定集合所有元素的隊列
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
} 是以之前栗子中，
ArrayDeque<String> arrayDeque = new ArrayDeque<>(4); 調用的是第二個構造函數，裡面有這麼一個函數allocateElements，讓我們來看看它的實作：
1 private void allocateElements(int numElements) {
2 elements = new Object[calculateSize(numElements)];
3 }
4
5 private static int calculateSize(int numElements) {
6 int initialCapacity = MIN_INITIAL_CAPACITY;
7 if (numElements >= initialCapacity) {
8 initialCapacity = numElements;
9 initialCapacity |= (initialCapacity >>> 1);
10 initialCapacity |= (initialCapacity >>> 2);
11 initialCapacity |= (initialCapacity >>> 4);
12 initialCapacity |= (initialCapacity >>> 8);
13 initialCapacity |= (initialCapacity >>> 16);
14 initialCapacity++;
15
16 if (initialCapacity < 0)
17 initialCapacity >>>= 1;
18 }
19 return initialCapacity;
20 } allocateElements方法主要用于給内部的數組配置設定合适大小的空間，calculateSize方法用于計算比numElements大的最小2的幂次方，如果指定的容量大小小于MIN_INITIAL_CAPACITY（值為8），那麼将容量設定為8，否則通過多次無符号右移進行最小2次幂計算。先将initialCapacity指派為numElements，接下來，進行5次無符号右移，下面将以一個小栗子介紹這樣運算的妙處。
在Java中，int類型是占4位元組，也就是32位。簡單起見，這裡以一個8位二進制數來示範前三次操作。假設這個二進制數對應的十進制為89，整個過程如下：
可以看到最後，除了第一位，其他位全部變成了1，然後這個結果再加一，即得到大于89的最小的2次幂，怎麼樣，很巧妙吧，也許你會想，為什麼右移的數值要分别是1，2，4，8，16呢？嗯，好問題。其實仔細觀察就會發現，先右移在進行或操作，其實我們隻需要關注第一個不為0的位即可，下面以64為例再示範一次：
是以，事實上，在這系列操作中，其他位隻是配角，我們隻需要關注第一個不為0的位即可，假設其為第n位，先右移一位然後進行或操作，得到的結果，第n位和第n-1位肯定為1，這樣就有兩個位為1了，然後進行右移兩位，再進行或操作，那麼第n位到第n-3位一定都為1，然後右移4位，依次類推。int為32位，是以，最後隻需要移動16位即可。1+2+4+8+16 = 31，是以經過這一波操作，原數字對應的二進制，操作得到的結果将是從其第一個不為0的位開始，往後的位均為1。然後：
initialCapacity++; 再自增一下，目标完成。觀察到還有下面這一小節代碼：
if (initialCapacity < 0)
initialCapacity >>>= 1; 其實它是為了防止進行這一波操作之後，得到了負數，即原來第31位為1，得到的結果第32位将為1，第32位為符号位，1代表負數，這樣的話就必須回退一步，将得到的數右移一位（即2 ^ 30）。 嗯，那麼這一部分就先告一段落了。
來看看之前的那些函數。
public boolean add(E e) {
addLast(e);
return true;
}
/**
* 在隊列頭部插入元素，如果元素為null，則抛出異常
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
/**
* 在隊列尾部插入元素，如果元素為null，則抛出異常
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
} add的幾個函數比較簡單，在頭部或者尾部插入元素，如果直接調用add方法，則是在尾部插入，這時直接在對應位置塞入該元素即可。
elements[tail] = e; 然後把tail記錄其後一個位置，如果tail記錄的位置已經是數組的最後一個位置了怎麼辦？嗯，這裡又有一個巧妙的操作，跟HashMap中的取模是一樣的：
tail = (tail + 1) & (elements.length - 1) 因為elements.length是2的幂次方，是以減一後就變成了掩碼，tail如果記錄的是最後一個位置，即 elements.length - 1，tail + 1 則等于elements.length，與 elements.length - 1 做與操作後，就變成了0，嗯，沒錯，這樣就變成了一個循環數組，如果tail與head相等，則表示沒有剩餘空間可以存放更多元素了，則調用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;
} 擴容其實也是很簡單粗暴的，先記錄一下原來head的位置，然後把容量變為原來的兩倍，然後把head之後的元素複制到新數組的開頭，把剩餘的元素複制到新數組之後。以之前的栗子為例，建立的ArrayDeque執行個體容量為8，然後我們調用add插入元素，插入H之後，tail指向第一個位置，與head重合，就會觸發擴容。
arrayDeque.add("A");
arrayDeque.add("B");
arrayDeque.add("C");
arrayDeque.add("D");
arrayDeque.add("E");
arrayDeque.add("F");
arrayDeque.add("G");
arrayDeque.add("H");
arrayDeque.add("I"); 看圖應該就比較清楚了，然後來看看擷取元素的幾個方法：
// 擷取元素
String a = arrayDeque.getFirst();
String a1 = arrayDeque.pop();
String b = arrayDeque.element();
String b1 = arrayDeque.removeFirst();
String c = arrayDeque.peek();
String c1 = arrayDeque.poll();
String d = arrayDeque.pollFirst();
String i = arrayDeque.pollLast();
String e = arrayDeque.peekFirst();
String h = arrayDeque.peekLast();
String h1 = arrayDeque.removeLast();
System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1);
System.out.println(); getFirst方法直接取head位置的元素，如果為null則抛出異常。
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
} getLast也是類似，取出tail所在位置的前一個位置，這裡也做了掩碼操作。
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
} element方法直接調用的是getFirst方法：
public E element() {
return getFirst();
} remove方法有三個：
public E remove() {
return removeFirst();
}
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
} remove方法其實是調用的對應的poll方法，poll方法也有三個：
public E poll() {
return pollFirst();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// 如果結果為null則傳回null
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;
} 其實也很簡單，都是先取出對應的元素，如果為null則傳回null，否則取出對應的元素并對head或tail進行調整。
pop方法調用的是removeFirst方法，removeFIrst方法調用的是pollFirst方法，是以方法看起來這麼多，實際上最後真正調用的就那麼幾個。
public E pop() {
return removeFirst();
} peek方法是取出元素但是不移除，也有三個方法：
public E peek() {
return peekFirst();
}
@SuppressWarnings("unchecked")
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
@SuppressWarnings("unchecked")
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
} 這裡沒有做任何校驗，是以如果如果取到的元素是null，傳回的也是null。
再來看看插入元素的其它幾個方法：
public boolean offer(E e) {
return offerLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public void push(E e) {
addFirst(e);
} offer方法直接調用的是add方法。
emmm，都是互相調用，為啥要設定那麼多方法呢？其實主要是為了模拟不同的資料結構，如棧操作：pop，push，peek，隊列操作：add，offer，remove，poll，peek，element，雙端隊列操作：addFirst，addLast，getFirst，getLast，peekFirst，peekLast，removeFirst，removeLast，pollFirst，pollLast。不過确實稍微多了一點。
之前的栗子裡還有用到兩個方法，removeFirstOccurrence和removeLastOccurrence，前者是移除首次出現的位置，後者是移除最後一次出現的位置。
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;
} 其實都是通過循環周遊的方式進行查找一個是從head開始往後查找，一個是從tail開始往前查找。
最後，我們再來看看它的疊代器類。
public Iterator<E> iterator() {
return new DeqIterator();
}
private class DeqIterator implements Iterator<E> {
private int cursor = head;
private int fence = tail;
private int lastRet = -1;
public boolean hasNext() {
return cursor != fence;
}
public E next() {
if (cursor == fence)
throw new NoSuchElementException();
@SuppressWarnings("unchecked")
E result = (E) elements[cursor];
if (tail != fence || result == null)
throw new ConcurrentModificationException();
lastRet = cursor;
cursor = (cursor + 1) & (elements.length - 1);
return result;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (delete(lastRet)) {
cursor = (cursor - 1) & (elements.length - 1);
fence = tail;
}
lastRet = -1;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
Object[] a = elements;
int m = a.length - 1, f = fence, i = cursor;
cursor = f;
while (i != f) {
@SuppressWarnings("unchecked") E e = (E)a[i];
i = (i + 1) & m;
if (e == null)
throw new ConcurrentModificationException();
action.accept(e);
}
}
} 在疊代器類中，cursor記錄的是head的位置，fence記錄的是tail的位置，lastRet記錄的是調用next傳回的元素的序号，如果調用了remove方法，lastRet會置為-1，這裡沒有像其它容器那樣使用modCount來實作fast-fail機制，而是通過在next方法中進行修改判斷。
// 如果移除了尾部元素，會導緻 tail != fence
// 如果移除了頭部元素，會導緻 result == null
if (tail != fence || result == null)
throw new ConcurrentModificationException(); 當然，這種檢測比較弱，如果先移除一個尾部元素，然後再添加一個尾部元素，那麼tail依舊和fence相等，這種情況就檢測不出來了。
在調用remove方法的時候，調用了一個delete方法，這是ArrayDeque類中的一個私有方法。
private boolean delete(int i) {
// 先做不變性檢測，判斷是否目前結構滿足删除需求
checkInvariants();
final Object[] elements = this.elements;
// mask即掩碼
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
// front代表i到頭部的距離
final int front = (i - h) & mask;
// back代表i到尾部的距離
final int back = (t - i) & mask;
// 再次校驗，如果i到頭部的距離大于等于尾部到頭部的距離，表示目前隊列已經被修改了，通過最開始檢測後，i是不應該滿足該條件的
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// 為移動盡量少的元素做優化，如果離頭部比較近，則将該位置到頭部的元素進行移動，如果離尾部比較近，則将該位置到尾部的元素進行移動
if (front < back) {
if (h <= i) {
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);
elements[0] = elements[mask];
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
if (i < t) { // Copy the null tail as well
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
} 是以這個delete還是花了一點心思的，不僅做了兩次校驗，還對元素移動進行了優化。嗯，到此為止，源碼部分就差不多了。
那麼現在再回到最開始提的問題。
1、ArrayDeque是什麼？ArrayDeque是一個用循環數組實作的雙端隊列。
2、ArrayDeque如何使用？通過add，offer，poll等方法進行操作。
3、ArrayDeque的内部結構是怎樣的？内部結構是一個循環數組。
4、ArrayDeque的各個方法是如何實作的？嗯，見上文。
5、ArrayDeque是如何擴容的？擴容成原來的兩倍，然後将原來的内容複制到新數組中。
6、ArrayDeque的容量有什麼限制？容量必須為2的幂次方，最小為8，預設為16.
7、ArrayDeque和LinkedList相比有什麼優勢？ArrayDeque通常來說比LinkedList更高效，因為可以在常量時間通過序号對元素進行定位，并且省去了對元素進行包裝的空間和時間成本。
8、ArrayDeque的應用場景是什麼？在很多場景下可以用來代替LinkedList，可以用做隊列或者棧。
到此，本篇圓滿結束。如果覺得還不錯的話，記得動動小手點個贊，也歡迎關注部落客，你們的支援是我寫出更好部落格的動力。
有興趣對Java進行更深入學習和交流的小夥伴，歡迎加入QQ群交流：529253292