前言
今天我们来看看 ArrayDeque，可以说，之前使用的队列的场景不多，所以也没有深入研究队列，但最近在做 LeetCode 的时候，很多时候使用队列会有想不到的功效，比如我们在写 BFS 广度优先遍历的时候，或者在写 二叉树的层次遍历，非递归前序，中序，后序遍历，都会用到这个结构，如果还不会的同学，赶紧去复习一波吧，非常总要，也能为你的笔面试加不少分，很多时候当面试官问道我分析过的源码时，心里那个叫酸爽啊，令面试官刮目相看。闲话不多说了，让我们深入了解一下我们的主角
前世今生
实现了 Deque 接口，Deque 继承了 Queue
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {}
public interface Deque<E> extends Queue<E> {}
Queue
在了解 ArrayDeque 之前，我们先来看看 Queue 有些什么东西，谈到队列，我们会想到先进先出等特性，我把接口贴出来给大家看一下，如果你还不熟悉这几个方法的区别，是该反省一下了！！！一定要熟记，这是基本功
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
Deque
由于是双端队列，多了很多接口，一张图真相，你可能会说，记住这些所有的太难了，太多了，但总结起来，也并不多，在之前的Queue的接口的基础上，加了 First，Last 的接口，是不是一下子变少了
Screen Shot 2018-09-12 at 11.00.50 PM.png
ArrayDeque
终于到了我们的主角了，然而你可能会想，是不是也有LinkedDeque，当初我也这样想过，然而我并没有在 jdk 里找到这个数据结构，但是 LinkedList 却实现了 Deque 也就是说它取代了自己LinkedDeque，也就没有必要多此一举了
属性
既然是 Array，那么里面势必用数组存储，记住，使用 Object[] elements,而不是T[] elements,聪明的你能否想到这样做的目的呢？哈哈。然后是一个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;
构造函数
默认开辟了 16 的数组，一般都是这样，预先开辟空间，不够了再扩容。如果自己指定了大小，那么将调用 allocateElements函数，获取一个 2 的幂次方的大小的容量，如果你知道 Hashmap的初始化，那么这个初始化你一定不陌生！至于怎么做到，你可以自己实践一下，这样会理解的更加透彻！
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，直接给数组的末尾元素赋值，之后便是移动tail 指针，这里的扩容实现的很有意思，这也对应了为什么容量要为 2的幂次方，当数组大小刚好为 2 的幂次方时，(tail = (tail + 1) & (elements.length - 1) 为零，也就是说如果head也为0，那么就需要扩容了
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
doubleCapacity 函数，新数组的大小为两倍，使用 System.arraycopy 函数复制，效率极高。因为 head 不一定为零，所以在扩容的时候，需要恢复head = 0；这里我们应该推测出整个数组都是存储数据，为了方便删除数组而不移动元素，便使用了指针记录状态，这一实现必须要好好琢磨，下次面试别人的时候可以问一下别人，哈哈，有点小坏
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 获取元素，当然是从 head 位置获取元素，这里需要注意的是，head 如果到了数组末尾，那么又会通过 (h + 1) & (elements.length - 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;
}
pollLast 获取队尾元素，如果队尾元素此时为 0，那么将回到了 数组末尾，别问我怎么知道，老师叫你好好学二进制！
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;
}
/**
* @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 根据先进先出，pop 应该移除队首的元素，注意，这里会抛出异常，如果队首为空的话
* @throws NoSuchElementException {@inheritDoc}
*/
public E pop() {
return removeFirst();
}
小结
ArrayDeque 看起来不大，但也有不少东西，知道大概容易，弄懂每一个细节很难，如果你做到了，成功便是你的~
网友评论