源码|jdk源码之栈、队列及ArrayDeque分析

2018-09-09

栈、队列、双端队列都是非常经典的数据结构。和链表、数组不同，这三种数据结构的抽象层次更高。它只描述了数据结构有哪些行为，而并不关心数据结构内部用何种思路、方式去组织。
本篇博文重点关注这三种数据结构在java中的对应设计，并且对ArrayDeque的源码进行分析。

1. 概念

先来简单回顾下大学时的数据结构知识。

什么是栈？数据排成一个有序的序列，只能从一个口弹出数据或加入数据。即后进先出（LIFO）。
什么是队列？数据同样排成一个有序的序列，数据只能在队尾加入，在队头弹出。即先进先出（FIFO）。
什么是双端队列？数据同样排成一个有序的序列，只能从前后两个口插入或删除数据。结合了栈和队列的特点。

这三样东西都可以通过数组或链表来实现。从这种表述就能发现，似乎链表和数组比这三个更“偏底层”。
仔细思考不难发现，栈、队列、双端队列仅仅是描述了接口行为，是一种抽象数据类型；而数组、链表则描述的是数据的具体在内存中的组织方式。

2. java中栈、队列、双端队列

2.1. java中的栈

public
class Stack<E> extends Vector<E> {
    /* */
}

java的确有一个叫做Stack的类，它继承自Vector。
个人以为，jdk的这种设计不是很妥当。前面分析过，Stack从概念上是一种抽象数据类型，可以有多种实现方式。因此，将其设计为接口更为合适。
jdk的这种设计导致：

Stack只有数组这一种实现方式，没有办法改用其它的实现方式。
Stack继承自Vector，耦合太紧，同时拥有Vector的大量不属于Stack模型的方法，破坏隐藏。

此外，Vector本身现在已经不建议使用了。

而且，jdk自己也说了，Stack这个类，设计的不好，不推荐使用：

* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class.  For example:
*   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>

好在Deque像是栈和队列的组合，也能当栈使用。因此，在java中，有栈的使用需求时，使用Deque代替。

而且，偶然间在jdk中看到这样一个工具函数Collections.asLifoQueue：

1
2
3

public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
    return new AsLIFOQueue<>(deque);
}

它将Deque包装成一个Lifo的队列。LIFO？那不就是栈么！也就是说，得到的虽然是Queue接口，但是行为是LIFO。

2.2. java中的队列

1
2
3

public interface Queue<E> extends Collection<E> {
    /* ... */
}

jdk中队列的设计没有什么问题，是一个接口。
虽然名字叫Queue，但是这个jdk中Queue接口指代的范围更广。从它的子接口及实现类来看，有这样几种含义：

FIFO队列。也就是数据结构中的先进先出队列。
优先队列。也就是数据结构中的大顶堆或小顶堆。
阻塞队列。也是队列，只不过某些方法在没有元素时或队满时会阻塞，并发中使用的一种结构。

再来看它的几种实现：

FIFO队列。FIFO队列的实现其实是按照Deque实现的了，有LinkedList和ArrayDeque。
优先队列。PriorityQueue。
阻塞队列。这个和并发关系更大，这里先不谈。

2.3. java中的双端队列

双端队列的定义也是接口：

1
2
3

public interface Deque<E> extends Queue<E> {
    /* ... */
}

Deque也是Queue，Deque也能当Queue用，没有太多额外开销。所以jdk没有单独实现Queue。

Deque有两种实现类：

LinkedList。也就是链表，java的链表同时实现了Deque。
ArrayDeque。Deque的数组实现。为什么不在ArrayList中一把实现Deque接口？
也很简单，实现方式不同。

Deque也有阻塞队列版本的实现，这里也先不谈。

3. ArrayDeque源码分析

3.1. 实现思路

我先来总结下ArrayDeque的实现思路。

首先，ArrayDeque内部是拥有一个内部数组用于存储数据。
其次，假设采用简单的方案，即队列数组按顺序在数组里排开，那么：

由于ArrayDeque的两端都能增删数据，那么把数据插入到队列头部也就是数组头部，会造成O(N)的时间复杂度。
假设只再队尾加入而只从队头删除，队头就会空出越来越多的空间。

那么该怎么实现？也很简单。将物理上的连续数组回绕，形成逻辑上的一个 环形结构。即a[size - 1]的下一个位置是a[0].
之后，使用头尾指针标识队列头尾，在队列头尾增删元素，反映在头尾指针上就是这两个指针绕着环赛跑。

这个是大体思路，具体的还有一些细节，后面代码里分析：

head和tail的具体概念是如何界定？
如果判断队满和队空？
数组满了怎么办？

3.2. 属性

先来看内部属性。elements域就是存储数据的原生数组。
head和tail分别分别为头尾指针。

transient Object[] elements; // non-private to simplify nested class access
transient int head;
transient int tail;

3.3. 构造函数

public ArrayDeque() {
    elements = new Object[16];
}
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

如果没有指定内部数组的初始大小，默认为16.
如果指定了内部数组的初始大小，则通过calculateSize函数二次计算出大小。

来看calculateSize函数：

private static final int MIN_INITIAL_CAPACITY = 8;
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;
}

如果小于8，那么大小就为8.
如果大于等于8，则按照2的幂对齐。

3.4. 入队

看两个入队方法：

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

addFirst是从队头插入，addLast是从队尾插入。

从该代码能够分析出head和tail指针的含义：

head指针指向的是队头元素的位置，除非队列为空。
tail指针指向的是队尾元素后一格的位置，即尾后指针。

因此：

如果队列没有满，tail指向的是空位置，head指向的是队头元素，永远不可能一样。
但是当队列满时，tail回绕会追上head，当tail等于head时，表示队列满了。

理清楚了这一点，上面的代码也就十分容易理解了：

对应位置插入位置，移动指针。
当tail和head相等时，扩容。

最后，这句：

1	(head - 1) & (elements.length - 1)

曾经在《源码|jdk源码之HashMap分析(二)》中分析过，假如被余数是2的幂次方，那么模运算就能够优化成按位与运算。
也即相当于：

1	(head - 1) % elements.length

3.5. 出队

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;
}

出队的代码很显然，不多解释。

3.6. 扩容

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;
    // 扩容后的大小小于0（溢出），也即队列最大应该是2的30次方
    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;
}

扩容的实现为按两倍扩容原数组，将原数倍拷贝过去。
其中值得注意的是对数组大小溢出的处理。

3.7. 迭代器

之前《源码|jdk源码之LinkedList与modCount字段》中分析过，
容器的实现中，所有修改过容器结构的操作都需要修改modCount字段。
这样迭代器迭代过程中，通过前后比对该字段来判断容器是否被动过，及时抛出异常终止迭代以免造成不可预测的问题。

不过，在ArrayDeque的插入方法中并没有修改modeCount字段。从ArrayDeque的迭代器的实现中可以看出来：

private class DeqIterator implements Iterator<E> {
    /**
     * Index of element to be returned by subsequent call to next.
     */
    private int cursor = head;
    /**
     * Tail recorded at construction (also in remove), to stop
     * iterator and also to check for comodification.
     */
    private int fence = tail;
}

原来，ArrayDeque直接使用了head和tail头尾指针，就能判断出迭代过程中是否发生了变化。