ArrayDeque 源码解析

1、Stack 和 Queue 和 Deque

在讲解ArrayDeque之前，我们先对Stack（栈）、Queue（队列）和Deque（双向队列）进行解析一下。

1.1、Stack

栈（Stack）是一种遵循先入后出的逻辑的线性数据结构。

栈的先入后出规则

Java中有个Stack类，它是Vector的子类。但是Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque。

1.2、Queue

队列（Queue）是一种遵循先入先出规则的线性数据结构。

队列的先入先出规则

Java中的Queue接口继承了Collection接口。除了Collection的方法外，Queue还提供了一些额外方法，分别对应插入、删除和检查操作。

方法	说明
add(E e)	添加元素到队列的末尾，如果队列已满，则抛出IllegalStateException异常。
offer(E e)	添加元素到队列的末尾，如果队列已满，则返回false。
remove()	移除并返回队列头部的元素，如果队列为空，则抛出NoSuchElementException异常。
poll()	移除并返回队列头部的元素，如果队列为空，则返回null。
element()	返回队列头部的元素，但不移除它，如果队列为空，则抛出NoSuchElementException异常。
peek()	返回队列头部的元素，但不移除它，如果队列为空，则返回null。

1.3、Deque

双向队列(Deque：double-ended queue) 提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

双向队列入队出对

Java中的Deque接口继承了Queue接口。除了Queue的方法外，Deque还提供了一些额外方法。

方法	说明
addFirst(E e)	在双端队列的头部添加元素，如果队列已满，则抛出IllegalStateException异常。
addLast(E e)	在双端队列的尾部添加元素，如果队列已满，则抛出IllegalStateException异常。
offerFirst(E e)	在双端队列的头部添加元素，如果队列已满，则返回false。
offerLast(E e)	在双端队列的尾部添加元素，如果队列已满，则返回false。
removeFirst()	移除并返回双端队列的头部元素，如果队列为空，则抛出NoSuchElementException异常。
removeLast()	移除并返回双端队列的尾部元素，如果队列为空，则抛出NoSuchElementException异常。
pollFirst()	移除并返回双端队列的头部元素，如果队列为空，则返回null。
pollLast()	移除并返回双端队列的尾部元素，如果队列为空，则返回null。
getFirst()	返回双端队列的头部元素，但不移除它，如果队列为空，则抛出NoSuchElementException异常。
getLast()	返回双端队列的尾部元素，但不移除它，如果队列为空，则抛出NoSuchElementException异常。
peekFirst()	返回双端队列的头部元素，但不移除它，如果队列为空，则返回null。
peekLast()	返回双端队列的尾部元素，但不移除它，如果队列为空，则返回null。

Deque的接口虽然有很多，但无非都是对两端的增删改查。Deque作为双向队列的首选实现类是ArrayDeque，其次选择LinkedList。

2、ArrayDeque 源码解析

ArrayDeque特性

• ArrayDeque的底层实现是数组，相比于LinkedList，ArrayDeque通常会提供更快的插入和移除元素的性能。
• ArrayDeque会进行动态扩容，当队列容量满时，扩容大小为原大小的2倍。因此，当预期数量大时，使用初始容量创建ArrayDeque会更有效率，避免频繁扩容带来的性能损耗。
• ArrayDeque在内部实现上使用了循环数组（Circular Array）的机制。
• ArrayDeque是非线程安全的(not thread-safe)
• ArrayDeque不支持null元素。

循环数组

循环数组是一个数组和一个指针，指针的移动是在这个数组的开始和结束之间进行的，如同指针在数组的末尾和数组的开始之间形成了一个循环。

• 在ArrayDeque中，有两个指针：head和tail。head指针总是指向队列的头部元素，tail指针总是指向队列的下一个空位。
• 当我们向ArrayDeque添加元素时，如果tail已经移动到数组的末尾并且数组没有满，那么tail会回到数组的开头；当我们从ArrayDeque中移除元素时，如果head已经移动到数组的末尾，那么head会回到数组的开头。这就是ArrayDeque的数据结构的精妙之处，它的实现相当于一个环形队列。
• 如果插入元素时发现数组已满，那么ArrayDeque会将内部数组的容量扩大一倍，然后将原有元素迁移到新的数组中。但在转移过程中，新数组中元素的布局依然保持原来的循环数组规则，这也是为什么称之为动态扩容的循环数组。
• 通过这种方式，ArrayDeque可以提供在队列两端插入和删除的复杂度为O(1)，同时避免了频繁的内存分配和数组复制。

源码

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    /**
     * 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;

    // ...
}

• elements：用于存储队列中的元素。
• head：表示在队列中头部元素的索引，也就是会被remove()或pop()方法删除的元素的索引；如果队列为空，则head与tail的值相同。
• tail：表示下一个元素会被添加到队列尾部的位置的索引，通过addLast(E)，add(E)，或push(E)方法添加的元素都会被添加的这个位置。
• MIN_INITIAL_CAPACITY：表示新创建的队列的最小初始容量，也确保了队列容量始终为2的幂。

2.1、构造函数

ArrayDeque提供了多个构造函数。用法和ArrayList差不多，这里不再赘述。

源码

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

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    //做移位与运算最后加一得到比给定长度大的最小的2的幂数。
    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];
}

allocateElements解析

对于一个给定长度，先判断是否小于定义的最小长度，如果小于，则使用定义的最小长度作为数组的长度。否则，找到比给定长度大的最小的2的幂数

2.2、addFirst()

addFirst()在队列的首端插入元素，数组没有越界就比较简单了，直接elements[--head] = e就可以了。

首端插入过程中会遇到两个问题：

• 首端(head)的索引下标为0，需要将插入的位置改为数组的最后一个位置。
• 空间不够，需要扩容。

接下来先看源码再解析

源码

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


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

将元素插入到head前一位，同时修改head值。判断内存是否足够，若不够，扩容为原数组的两倍。然后通过System.arraycopy()，将原来数组的元素复制到新数组中。

解析过程：

head插入时，判断是否为null，Deque不允许有null的元素。elements[head = (head - 1) & (elements.length - 1)] = e;，这段代码就解决了下标越界问题。

• 当head ≠ 0时

因为element数组的内存大小为2的n次幂，因此(elements.length-1)的二进制为全1，(head - 1) & (elements.length - 1)值始终为head-1的值。即在element[head-1]插入元素。

• 当head = 0时

head - 1 = -1时，其中-1用二进制表示为全1，与elements.length - 1相与，结果为elements.length - 1的值，即在数组的末尾插入元素。

• 扩容

doubleCapacity()将新建一个数组，大小为原来的两倍，并分两次来复制，第一次复制head右边的元素，第二次复制head左边的元素。

2.3、addLast()

addLast()是在Deque的尾部(tail)直接插入元素，因为tail的位置总是为空的，所以直接elements[tail] = e插入就行。

源码

public void addLast(E e) {
    if (e == null) // 不允许放入null
        throw new NullPointerException();
    elements[tail] = e; // 赋值
    if ((tail = (tail + 1) & (elements.length - 1)) == head)// 下标越界处理
        doubleCapacity();// 扩容
}

解析过程

• 判断元素是否为空，不为空直接赋值给tail位置即可
• 判断插入之后，下标是否越界，处理方式跟addFirst()一样
• 扩容，也跟addFirst()一样

2.4、pollFirst()

pollFirst()的作用是删除并返回Deque首端元素，也即是head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。

源码

public E pollFirst() {
    int h = head;
    E result = elements[head];
    if (result == null)//null值意味着deque为空
        return null;
    elements[h] = null;//let GC work
    head = (head + 1) & (elements.length - 1);//下标越界处理
    return result;
}

2.5、pollLast()

pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。

源码

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null)//null值意味着deque为空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}

2.6、peekFirst()

peekFirst()的作用是返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。

源码

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

2.7、peekLast()

peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。

源码

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

3、ArrayDeque常用方法

方法	说明
add(E e)	向队列尾部添加元素。不推荐使用该方法，因为它与Queue的add方法在功能上有重复，建议 使用offer代替。
addFirst(E e)	在队列的头部添加元素。
addLast(E e)	在队列的尾部添加元素。
offer(E e)	向队列尾部添加元素，如果因为容量限制添加失败会返回false，而不是抛出异常。
offerFirst(E e)	在队头添加元素，如果因为容量限制添加失败会返回false，而不是抛出异常。
offerLast(E e)	在队尾添加元素，如果因为容量限制添加失败会返回false，而不是抛出异常。
remove()	移除并返回队头元素，如果队列为空，则抛出NoSuchElementException异常。
removeFirst()	移除并返回头部元素，如果队列为空，则抛出NoSuchElementException异常。
removeLast()	移除并返回尾部元素，如果队列为空，则抛出NoSuchElementException异常。
poll()	移除并返回队头元素，如果队列为空，则返回null。
pollFirst()	移除并返回头部元素，如果队列为空，则返回null。
pollLast()	移除并返回尾部元素，如果队列为空，则返回null。
getFirst()	获取，但是不移除头部元素。如果队列为空会抛出NoSuchElementException异常。
getLast()	获取，但是不移除尾部元素。如果队列为空会抛出NoSuchElementException异常。
peek()	获取，但是不移除头部元素。如果队列为空会返回null。
peekFirst()	获取，但是不移除头部元素。如果队列为空会返回null。
peekLast()	获取，但是不移除尾部元素。如果队列为空会返回null。
size()	返回队列中元素的个数。
clear()	清空队列中的所有元素。
isEmpty()	检查队列是否为空。如果为空返回true，否则返回false。
contains(Object o)	检查队列是否包含指定元素。如果包含返回true，否则返回false。