開篇
?Deque 接口繼承自 Queue接口鼻种，但 Deque 支持同時從兩端添加或移除元素反番，因此又被成為雙端隊列。鑒于此叉钥，Deque 接口的實現(xiàn)可以被當作 FIFO隊列使用罢缸，也可以當作LIFO隊列（棧）來使用。官方也是推薦使用 Deque 的實現(xiàn)來替代 Stack投队。
?ArrayDeque 是 Deque 接口的一種具體實現(xiàn)枫疆，是依賴于可變數(shù)組來實現(xiàn)的。ArrayDeque 沒有容量限制敷鸦，可根據(jù)需求自動進行擴容息楔。ArrayDeque不支持值為 null 的元素。
ArrayDeque類圖
ArrayDeque類圖
ArrayDeque的類變量和構(gòu)造函數(shù)
?ArrayDeque的類變量當中數(shù)組elements用來保存隊列元素轧膘，head指針指向第一個存儲元素钞螟，tail指向最后一個元素的下一個位置。
?ArrayDeque的calculateSize的邏輯非常巧妙谎碍，用于計算大于numElements的最小的2*n次方的值鳞滨。
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
// ArrayDeque采用數(shù)組來保存元素，通過頭尾指針實現(xiàn)循環(huán)數(shù)組
transient Object[] elements; // non-private to simplify nested class access
// 第一個元素和最后一個元素的位置
transient int head;
transient int tail;
private static final int MIN_INITIAL_CAPACITY = 8;
// 計算數(shù)組大小的方式蟆淀，實現(xiàn)大于numElements的最小的2*n次方的數(shù)字
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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
}
return initialCapacity;
}
// 分配數(shù)組的大小拯啦，calculateSize計算大小
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
ArrayDeque的add相關(guān)操作
?ArrayDeque的add操作支持head端插入和tail端插入澡匪，head端插入是先計算位置后插入元素，tail端的插入是先保存元素后計算位置褒链，所以會造成head的指針指向第一個元素的位置唁情，tail指向最后一個元素的下一個位置。
?ArrayDeque的擴容時機是在head和tail相等的時候甫匹，根據(jù)上面分析我們可以得出ArrayDeque的容量達到（舊容量-1）的時候進行擴容甸鸟。
?ArrayDeque的頭部插入過程是回退head指針后添加元素。
?ArrayDeque的尾部插入過程是添加元素后前進tail指針兵迅。
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//head往后移動一個位置放置新插入的元素
//head指向第一個元素的下標
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
//tail往前移動一個位置放置新插入的元素
//tail指向末尾元素的下一個位置抢韭，注意是末尾元素的下一個位置
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
//tail循環(huán)以后和head保持一個空余位置，也就是說head=tail+1的時候進行擴容
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
ArrayDeque的remove相關(guān)操作
?ArrayDeque的remove操作包括從head開始刪除和從tail開始刪除恍箭。
- 頭部刪除pollFirst()方法返回head指針指向的元素同時向后移動一個位置
- 尾部刪除pollLast()方法返回tail指針指向位置的前一個位置的元素后tail指針往前移動一個位置
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;
}
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;
}
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
@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)];
}
ArrayDeque的擴容過程
?ArrayDeque的擴容過程如下：
- 以2倍速率進行擴容（int newCapacity = n << 1）
- 拷貝下標head到數(shù)組末尾的元素到新數(shù)組
- 拷貝下標0到tail指針的元素到新數(shù)組
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;
}
ArrayDeque的操作圖解過程
ArrayDeque添加過程
ArrayDeque擴容過程
