Java8 ArrayDeque 源码解析

前言

今天我们来看看 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 看起来不大，但也有不少东西，知道大概容易，弄懂每一个细节很难，如果你做到了，成功便是你的~