Collections(五)Deque

[Sayi]

Deque是一个双向队列，它继承了Queue接口，除了作为双向队列使用外，既可以作为 FIFO队列和栈LIFO使用，即同时实现了堆栈和队列。

通用实现有LinkedList和ArrayDeque，前面已经讨论过LinkedList作为队列来使用，下面看一段如何作为栈来使用的代码：

LinkedList<String> linkedListDeque = new LinkedList<>();
linkedListDeque.push("hello");
linkedListDeque.push("i");
linkedListDeque.push("am");
linkedListDeque.push("stack");
org.junit.Assert.assertEquals("stack", linkedListDeque.pop());

本文将会对ArrayDeque详细阐述。

Deque接口

我们先来看看Deque接口。

public interface Deque<E> extends Queue<E> {

    // *** deque methods ***
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();

    // *** Stack methods ***
    void push(E e);
    E pop();

    // *** Collection methods ***
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

从方法名上大体上就能知道作用了，关于add和offer、remove和poll的区别参见《Java Collections Framework(三)Queue》。

ArrayDeque实现原理

ArrayDeque是基于双向可变数组实现的，内部维护一个数组Object[] elements以及两个变量：int head和int tail，其中head是队列头部的下标，tail是队列尾部下一个位置的下标，即head始终指向第一个元素，tail指向空元素，它是最后一个元素的下一个插入位置。

之所以称为双向数组，是因为它的元素可以从数组的两头插入，并且它还是一个循环数组，即如果head值为0，在头部插入新元素时，head位置会变为capacity-1，即这个内部数组的最后一个元素下标。

初始容量

在介绍容量的时候，我们先讨论一个明确的要求：ArrayDeque的容量必须是2的幂次方，那么这是为什么呢？它是为了高效的计算下标。 我们来考虑一个长度为8的数组，如果tail是7，那么增加一位后的下标应该是0，计算方式是：

new_tail = (tail + 1) % length = (7 + 1) % 8 = 0；

如果当前位置head是0，那么往前一位是7，计算方式是：

new_head = (head - 1 + length) % length = (0 - 1 + 8) % 8 = 7

由于取余运算在计算机指令中比较慢，但是如果 length是2的幂次方，我们可以用较快的位运算来代替取余运算。

(tail + 1) & (length - 1) = (7 + 1) & (8 - 1) = 0
(head - 1) & (length - 1) = (0 - 1) & (8 - 1) = 7

因此，为了迅速定位到数组的下标，要求容量是2的N次方，在HashMap的key的Hash映射到哈希表某个下标的时候，也采用了位运算，这也是为什么HashMap的容量也必须是2的幂次方的原因。

接下来我们分析下ArrayDeque的容量，默认初始容量是16，最小容量是8，由一个常量定义，并且也提供了一个定义初始容量的构造器，确切的说，这个参数numElements并不是初始容量的值，而是初始容量的下界，因为没有限制使用者这个参数的传值，可以传任何非2的幂次方的值，源码如下：

private static final int MIN_INITIAL_CAPACITY = 8;

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

那么又是如何保证内部数组的容量是2的幂次方呢? numElements是一个下界，向上取2的幂次方值为初始容量。

private void allocateElements(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
    }
    elements = new Object[initialCapacity];
}

增加元素和增长容量策略分析

我们直接看增加元素的代码，可以得出结论，ArrayQueue是不允许NULL值存在的，这和PriorityQueue是一致的，和LinkedList允许NULL值是不一致的。

循环数组的下标计算在源码中也可以理解的更清楚，计算head和tail值都运用了位运算。

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

方法doubleCapacity()是为了容量增长策略设计的，当下一个要插入的元素，让head和tail相遇相等时就会成倍增长容量，我们看下这个方法：

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

其中newCapacity = n << 1;就是扩容成双倍空间。

基础源码分析

获取元素

public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}

可以看到，由于tail是指向尾部的下一个位置，所以取最后一个元素，需要位运算。peek是队列的操作，没有元素时会返回null，当使用get方式获取元素时，如果没有元素，则会抛出异常：

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

出队

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

这段代码再一次说明了，队列操作如果result为空，则会返回null，如果是pop操作遇到null值，则会抛出NoSuchElementException异常，这里就不附上代码了。

删除首次出现的指定元素

public boolean removeFirstOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            delete(i);
            return true;
        }
        i = (i + 1) & mask;
    }
    return false;
}
private boolean delete(int i) {
    checkInvariants();
    final Object[] elements = this.elements;
    final int mask = elements.length - 1;
    final int h = head;
    final int t = tail;
    final int front = (i - h) & mask;
    final int back  = (t - i) & mask;

    // Invariant: head <= i < tail mod circularity
    if (front >= ((t - h) & mask))
        throw new ConcurrentModificationException();

    // Optimize for least element motion
    if (front < back) {
        if (h <= i) {
            System.arraycopy(elements, h, elements, h + 1, front);
        } else { // Wrap around
            System.arraycopy(elements, 0, elements, 1, i);
            elements[0] = elements[mask];
            System.arraycopy(elements, h, elements, h + 1, mask - h);
        }
        elements[h] = null;
        head = (h + 1) & mask;
        return false;
    } else {
        if (i < t) { // Copy the null tail as well
            System.arraycopy(elements, i + 1, elements, i, back);
            tail = t - 1;
        } else { // Wrap around
            System.arraycopy(elements, i + 1, elements, i, mask - i);
            elements[mask] = elements[0];
            System.arraycopy(elements, 1, elements, 0, t);
            tail = (t - 1) & mask;
        }
        return true;
    }
}

从源码中可见，当删除中间元素时，会出现数组拷贝复制操作，这里会有性能问题，而LinkedList的代价较低。

iterator源码实现和fail-fast设计

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;

  /**
   * Index of element returned by most recent call to next.
   * Reset to -1 if element is deleted by a call to remove.
   */
  private int lastRet = -1;

  public boolean hasNext() {
    return cursor != fence;
  }

  public E next() {
    if (cursor == fence)
      throw new NoSuchElementException();
    @SuppressWarnings("unchecked")
    E result = (E) elements[cursor];
    // This check doesn't catch all possible comodifications,
    // but does catch the ones that corrupt traversal
    if (tail != fence || result == null)
      throw new ConcurrentModificationException();
    lastRet = cursor;
    cursor = (cursor + 1) & (elements.length - 1);
    return result;
  }

  public void remove() {
    if (lastRet < 0)
      throw new IllegalStateException();
    if (delete(lastRet)) { // if left-shifted, undo increment in next()
      cursor = (cursor - 1) & (elements.length - 1);
      fence = tail;
    }
    lastRet = -1;
  }

  public void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    Object[] a = elements;
    int m = a.length - 1, f = fence, i = cursor;
    cursor = f;
    while (i != f) {
      @SuppressWarnings("unchecked") E e = (E)a[i];
      i = (i + 1) & m;
      if (e == null)
        throw new ConcurrentModificationException();
      action.accept(e);
    }
  }
}

当获取迭代器时，会保存当前的head和tail变量，分别为cursor和fence，当cursor不等于fence时，则认为有下一元素。

我们注意到的是，ArrayDeque实现fail-fast设计没有采用modCount机制，而是通过一个 不完全的判断来实现，这个判断只判断了当尾部下标变化时，才会抛出异常，这是值得注意的地方：

(tail != fence || result == null)

性能

ArrayDeque采用了双向可变数组，通过两个下标来标识收尾，它的访问和删除性能，都不会导致数组拷贝，当插入元素并且容量不足时，才会扩容，因为Deque大多数操作只允许在首部或者尾部进行，ArrayDeque和LinkedList之间并没有多少性能差异。

它们之间的性能差异主要体现在 迭代过程中删除元素，因为这样会导致ArrayDeque执行数组复制，正如上文中removeFirstOccurrence方法的源码所示。

最后，ArrayDeque的容量也是性能优化的一个点。

总结

ArrayDeque和LinkedList都不是线程安全的，LinkedBlockingDeque(如果双端队列为空，则方法如takeFirst并takeLast一直等待)是并发环境下一个双向队列的选择。