ArrayDeque 源码

问题

1. ArrayDeque 如何实现双端队列的？
2. ArrayDeque 操作队列的头部和尾部指针有什么特别技巧，如何防止移位越界？
3. ArrayDeque 有界吗？

概述

• 双端队列，非线程安全

  ArrayDeque 是一种以数组方式实现的双端队列（两端可以进出），非线程安全。

继承结构

• ArrayDeque 继承 AbstractCollection<E>

可求两个集合的并集、差集、交集等方法

• ArrayDeque 实现了 Deque<E> 接口

实现双队列方法，具有双端队列属性

源码实现

属性

/**
 * The array in which the elements of the deque are stored.
 * The capacity of the deque is the length of this array, which is
 * always a power of two. The array is never allowed to become
 * full, except transiently within an addX method where it is
 * resized (see doubleCapacity) immediately upon becoming full,
 * thus avoiding head and tail wrapping around to equal each
 * other.  We also guarantee that all array cells not holding
 * deque elements are always null.
 */
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;

/**
 * The minimum capacity that we'll use for a newly created deque.
 * Must be a power of 2.
 */
private static final int MIN_INITIAL_CAPACITY = 8;

• ArrayDeque 底层使用数组存储，容量大小总是 2^n

• ArrayDeque 使用头部和尾部指针标识

• ArrayDeque 的最小总量是 8

构造方法

/**
 * Constructs an empty array deque with an initial capacity
 * sufficient to hold 16 elements.
 */
public ArrayDeque() {
    elements = new Object[16];
}

/**
 * Constructs an empty array deque with an initial capacity
 * sufficient to hold the specified number of elements.
 *
 * @param numElements  lower bound on initial capacity of the deque
 */
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

/**
 * Constructs a deque containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.  (The first element returned by the collection's
 * iterator becomes the first element, or <i>front</i> of the
 * deque.)
 *
 * @param c the collection whose elements are to be placed into the deque
 * @throws NullPointerException if the specified collection is null
 */
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

/**
 * Allocates empty array to hold the given number of elements.
 *
 * @param numElements  the number of elements to hold
 */
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^n）
• 最大分配容量的 2^30

知识点

如何找到大于一个正整数N的最小2的次幂数，参考 calculateSize(int numElements) 方法。
详细解读

入队

入队有很多方法，主要是调用以下两个方法。

/**
 * Inserts the specified element at the front of this deque.
 *
 * @param e the element to add
 * @throws NullPointerException if the specified element is null
 */
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

/**
 * Inserts the specified element at the end of this deque.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 * @throws NullPointerException if the specified element is null
 */
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

• 两种入队方式，从队列头或者从队列尾
• 如果容量不够，直接扩大为两倍
• 头部指针和尾部指针在数组范围内循环

知识点

一个容量为 2^n 的数组，增减元素时移动前后指针，如何使用最优的方式解决指针越界的问题？

• 前提：elements.length 是 2^n
• head = (head - 1) & (elements.length - 1) 头部指针前移一位
• tail = (tail + 1) & (elements.length - 1) 尾部指针后移一位

扩容

ArrayDeque 扩容为原来的两倍。

/**
 * Doubles the capacity of this deque.  Call only when full, i.e.,
 * when head and tail have wrapped around to become equal.
 */
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;
}

• 创建新的数组为原来的两倍
• 从旧的数组拷贝到新数组
• 重新设置头部和尾部的指针

出队

出队有多种方法，主要调用以下两个方法。

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

• 两种出队方式，从队列头部或者队列尾
• 与出队一样方式，反向调整指针的位置

栈

ArrayDeque 可以作为栈来使用。

/**
 * Pushes an element onto the stack represented by this deque.  In other
 * words, inserts the element at the front of this deque.
 *
 * <p>This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @throws NullPointerException if the specified element is null
 */
public void push(E e) {
    addFirst(e);
}

/**
 * Retrieves and removes the head of the queue represented by this deque
 * (in other words, the first element of this deque), or returns
 * {@code null} if this deque is empty.
 *
 * <p>This method is equivalent to {@link #pollFirst}.
 *
 * @return the head of the queue represented by this deque, or
 *         {@code null} if this deque is empty
 */
public E poll() {
    return pollFirst();
}

• 栈的特性是先进后出，故只需要操作队列头就可以实现了

总结

• ArrayDeque 通过数组实现的双端队列；
• ArrayDeque 出队入队列是通过操作头部和尾部的指针实现；
• ArrayDeque 容量不足是，进行扩容，新容量为原来的 2 倍；
• ArrayDeque 的容量都是 2^n ，这样方便操作头部和尾部的指针；

head = (head - 1) & (elements.length - 1) 头部指针前移一位
tail = (tail + 1) & (elements.length - 1) 尾部指针后移一位

• ArrayDeque 可作为栈来使用；