前言
今天我們來(lái)看看 ArrayDeque，可以說(shuō)，之前使用的隊(duì)列的場(chǎng)景不多，所以也沒(méi)有深入研究隊(duì)列，但最近在做 LeetCode 的時(shí)候，很多時(shí)候使用隊(duì)列會(huì)有想不到的功效，比如我們?cè)趯?xiě) BFS 廣度優(yōu)先遍歷的時(shí)候，或者在寫(xiě) 二叉樹(shù)的層次遍歷，非遞歸前序，中序，后序遍歷，都會(huì)用到這個(gè)結(jié)構(gòu)，如果還不會(huì)的同學(xué)，趕緊去復(fù)習(xí)一波吧，非?？傄材転槟愕墓P面試加不少分，很多時(shí)候當(dāng)面試官問(wèn)道我分析過(guò)的源碼時(shí)，心里那個(gè)叫酸爽啊，令面試官刮目相看。閑話不多說(shuō)了，讓我們深入了解一下我們的主角
前世今生
實(shí)現(xiàn)了 Deque 接口，Deque 繼承了 Queue
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {}
public interface Deque<E> extends Queue<E> {}
Queue
在了解 ArrayDeque 之前，我們先來(lái)看看 Queue 有些什么東西，談到隊(duì)列，我們會(huì)想到先進(jìn)先出等特性，我把接口貼出來(lái)給大家看一下，如果你還不熟悉這幾個(gè)方法的區(qū)別，是該反省一下了！??！一定要熟記，這是基本功
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
Deque
由于是雙端隊(duì)列，多了很多接口，一張圖真相，你可能會(huì)說(shuō)，記住這些所有的太難了，太多了，但總結(jié)起來(lái)，也并不多，在之前的Queue的接口的基礎(chǔ)上，加了 First，Last 的接口，是不是一下子變少了
ArrayDeque
終于到了我們的主角了，然而你可能會(huì)想，是不是也有LinkedDeque，當(dāng)初我也這樣想過(guò)，然而我并沒(méi)有在 jdk 里找到這個(gè)數(shù)據(jù)結(jié)構(gòu)，但是 LinkedList 卻實(shí)現(xiàn)了 Deque 也就是說(shuō)它取代了自己LinkedDeque，也就沒(méi)有必要多此一舉了
屬性
既然是 Array，那么里面勢(shì)必用數(shù)組存儲(chǔ)，記住，使用 Object[] elements,而不是T[] elements,聰明的你能否想到這樣做的目的呢？哈哈。然后是一個(gè)head，tail 的指針。
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
構(gòu)造函數(shù)
默認(rèn)開(kāi)辟了 16 的數(shù)組，一般都是這樣，預(yù)先開(kāi)辟空間，不夠了再擴(kuò)容。如果自己指定了大小，那么將調(diào)用 allocateElements函數(shù)，獲取一個(gè) 2 的冪次方的大小的容量，如果你知道 Hashmap的初始化，那么這個(gè)初始化你一定不陌生！至于怎么做到，你可以自己實(shí)踐一下，這樣會(huì)理解的更加透徹！
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(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
}
return initialCapacity;
}
普通的方法
add 使用 addLast 在末尾追加元素
public boolean add(E e) {
addLast(e);
return true;
}
addLast，直接給數(shù)組的末尾元素賦值，之后便是移動(dòng)tail 指針，這里的擴(kuò)容實(shí)現(xiàn)的很有意思，這也對(duì)應(yīng)了為什么容量要為 2的冪次方，當(dāng)數(shù)組大小剛好為 2 的冪次方時(shí)，(tail = (tail + 1) & (elements.length - 1) 為零，也就是說(shuō)如果head也為0，那么就需要擴(kuò)容了
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
doubleCapacity 函數(shù)，新數(shù)組的大小為兩倍，使用 System.arraycopy 函數(shù)復(fù)制，效率極高。因?yàn)?head 不一定為零，所以在擴(kuò)容的時(shí)候，需要恢復(fù)head = 0；這里我們應(yīng)該推測(cè)出整個(gè)數(shù)組都是存儲(chǔ)數(shù)據(jù)，為了方便刪除數(shù)組而不移動(dòng)元素，便使用了指針記錄狀態(tài)，這一實(shí)現(xiàn)必須要好好琢磨，下次面試別人的時(shí)候可以問(wèn)一下別人，哈哈，有點(diǎ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;
}
pollFirst 獲取元素，當(dāng)然是從 head 位置獲取元素，這里需要注意的是，head 如果到了數(shù)組末尾，那么又會(huì)通過(guò) (h + 1) & (elements.length - 1) 變?yōu)?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;
}
pollLast 獲取隊(duì)尾元素，如果隊(duì)尾元素此時(shí)為 0，那么將回到了 數(shù)組末尾，別問(wèn)我怎么知道，老師叫你好好學(xué)二進(jìn)制！
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;
}
其他的不涉及到刪除，添加到操作就顯得尤為簡(jiǎn)單了，直接獲取，就不必多說(shuō)了
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
pop 根據(jù)先進(jìn)先出，pop 應(yīng)該移除隊(duì)首的元素，注意，這里會(huì)拋出異常，如果隊(duì)首為空的話
* @throws NoSuchElementException {@inheritDoc}
*/
public E pop() {
return removeFirst();
}
小結(jié)
ArrayDeque 看起來(lái)不大，但也有不少東西，知道大概容易，弄懂每一個(gè)細(xì)節(jié)很難，如果你做到了，成功便是你的~
