转载

JDK源码—双端队列ArrayDeque

又是一个无聊的周一晚上，闲来无事的我，开始了翻翻代码玩玩，看看了看JDK源码，咦，眼前一亮，这个以前好像一直在忽略他嘛
看标题也知道了我看了看ArrayDeque的源码
好了为了防止有不知道的（大佬请忽略），让我们先了解一下预备知识（妙啊）

0.1 队列

首先我们需要知道啥是队列（Queue）？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

0.2 栈

然后我们需要知道什么是栈（Stack）？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

1. 源码结构

既然是讲Java源码，那么肯定是缺少不了继承实现结构图

1.1 Queue

Queue接口总得来说就是对Collection接口进行了拓展，增加了队列相关的特性操作方法的声明
boolean add(E e); 在不违反容量限制的情况将指定元素插入此队列，成功返回true，如果当前没有可用空间，则抛出 IllegalStateException。
boolean offer(E e); 在不违反容量限制的情况下将指定元素插入此队列。使用容量受限队列时此方法通常比add更可取，后者只能通过引发异常才能插入元素。
E remove();
E poll(); remove呵poll也同add和offer一样remove如果队列为空则或抛出异常，而poll则返回null
E element();
E peek(); element和peek也同add和offer一样，如果队列为空则抛出异常，而peek则没有抛出异常直接放回null。

1.2 Deque

Deque是支持在两端插入和删除元素的线性集合。直译就是“双端队列”他是"double ended queue"的缩写，通常发音为“deck”。大多数实现对它们可能包含的元素数量没有固定的限制，但是这个接口支持容量受限的容器以及没有固定大小限制的容器。
void addFirst(E e); 队列头部插入，容量不够会报错
void addLast(E e); 队列尾部插入，容量不够也会报错
boolean offerFirst(E e); 队列头部插入，成功返回true 容量不够返回false
boolean offerLast(E e); 队列尾部插入，成功返回true 容量不够返回false
E removeFirst/Last (E e)
E pollFirst/Last (E e) 分别从头尾移除元素并返回，同上也是一个没有袁术会报错一个会返回null
E getFirst/Last (E e);
E peekFirst/Last (E e)
除以上外还有peek push pop等常用方法、

1.3 ArrayDeque

类方法示意图

不难看出，主要是关于队列和栈的操作。下面我就讲详细讲一下关于这个类的实现

2. ArrayDeque 的数据结构

ArrayDeque的本质，就是一个可扩容的数组设计，里面包含了head和tail（我习惯叫头尾指针）他可以用于做双端队列，也可以用来做栈，而且他的实现方法里面做了二倍扩容机制（同HashMap用移位运算做的）保证了它的可拓展性。
此外需要注意，它并不是线程安全的，源码没有对它做任何同步操作。
双端队列主要是以数组为载体，增加与删除元素过后的变化则通过头尾指针的移动来记录如图

2.1 构造方法

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;
    }
复制代码

如上可看到，默认的无参构造赋默认容量大小为16
如果自己制定了多少元素则会计算大于这个值最近的的2的指数次
传直接传集合也同样计算容量大小
创建一个对象过后相当于int的值默认为0则，头尾指正front 和 tail(rear)如图所示

在双端队列中，front始终指向当前队首元素的位置
tail(rear)始终指向队尾元素的下一个位置也就是入队的位置

2.2 添加元素的方法

由于双端队列可以用作队列也可用作栈所以添加元素的方法有好几个，不过其本质都是差不多的
addFirst 队头增加元素

public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
复制代码

从这里可看出双端队列是没办法放null值的。且 offerFirst和addFirst是一个方法
因为这个方法是从队头增加元素 (head - 1) & (elements.length - 1) 这里解释一下，这个地方是length的值为2的多少次方，如果减了1 二进制表示的时候为全1 相当于 head减了1过后就算出现负数他也会自动到数组的length-1的地方。这个地方也就实现了队列的循环
addLast 队尾增加元素

public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
复制代码

同addFirst类似对应的offerFirst也是调用的addLast方法
这里说一下这个扩容 doubleCapacity 出发条件是当队列增加了一个元素，tail的值已经等于了front则空间不足出发扩容，扩容的方法如下

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;
    }
复制代码

它就是用System.arraycopy 把head到length-1的复制到新数组的前面，0到tail的紧接复制到后面。

2.3 移出元素的方法

pollFisrt 和 pollLast 移出元素也是对数组的操作基本类似

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;
    }
复制代码