【JDK源码】ArrayDeque源码分析

ArrayDeque源码分析

1.简介

双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。

ArrayDeque是一种以数组方式实现的双端队列，它是非线程安全的。

• 通过继承体系可以看，ArrayDeque实现了Deque接口，Deque接口继承自Queue接口，它是对Queue的一种增强。
• 从继承体系可以看出，ArrayDeque实现了Cloneable和Serializable接口，说明其可以被克隆，也可以被序列化。

2.主要属性

//存储元素的数组
transient Object[] elements; // non-private to simplify nested class access

//队列头位置
transient int head;

//队列尾位置
transient int tail;

//最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

从属性我们可以看到，ArrayDeque使用数组存储元素，并使用头尾指针标识队列的头和尾，其最小容量是8。

3.主要构造方法

//默认无参构造方法，初始容量为16
public ArrayDeque() {
    elements = new Object[16];
}

//指定元素个数初始化
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

//传入集合c，将其中的元素初始化到数组
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
//传入指定大小，初始化数组
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 计算容量，这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8
// 比如，3算出来是8，9算出来是16，33算出来是64
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，最小容量是8。

4.入队

入队有很多方法，我们这里主要分析两个，addFirst(e)和addLast(e)。

队头入队

//从队列头入队
public void addFirst(E e) {
    //如果为null，直接抛异常
    if (e == null)
        throw new NullPointerException();
    //将head指针减1并与数组长度减1取模
    //目的是防止数组到头了边界溢出
    //如果到头了就从尾部再向前
    //相当于循环利用数组
    //栗子：head为0，数组长度为8.(-1&7)=(-1%8)=7
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        //如果头尾在一起了，就触发扩容
        doubleCapacity();
}

队尾入队

//从队列尾入队
public void addLast(E e) {
    //不允许null元素，否则抛出异常
    if (e == null)
        throw new NullPointerException();
    //在尾指针的位置放入元素
    //可以看到tail指针指向的是队列的最后一个元素的下一个位置
    elements[tail] = e;
    //tail指针+1,如果到数组尾了就从头开始
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

整个流程：

1. 入队有两种方式，从队列头或者从队列尾
2. 如果容量不够了，直接扩大为两倍
3. 通过取模的方式让头尾指针在数组范围内循环
4. x & (len - 1) = x % len，使用&的方式更快

5.扩容

//两倍扩容
private void doubleCapacity() {
    assert head == tail;
    //头指针的位置
    int p = head;
    //旧数组的长度
    int n = elements.length;
    // head右边元素的个数
    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];
    //将旧数组head之后的元素拷贝到新数组中
    System.arraycopy(elements, p, a, 0, r);
    //将就数组小标0到head之间的元素拷贝到新数组中
    System.arraycopy(elements, 0, a, r, p);
    //赋值给新数组
    elements = a;
    //head指向0，tail指向旧数组长度表示的位置
    head = 0;
    tail = n;
}

下图为一个栗子，可做参考：

6.出队

出队同样有很多方法，我们主要看两个，pollFirst()和pollLast()。

队头出队

//从队列头出队
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    //取队列头元素
    E result = (E) elements[h];
    // 如果队列为空，就返回null
    if (result == null)
        return null;
    //将队列头置为空
    elements[h] = null;     // Must null out slot
    //队列头指针想右移动一位
    head = (h + 1) & (elements.length - 1);
    //返回取到的元素
    return result;
}

队尾出队

//从队列尾出队
public E pollLast() {
    //tail的上一个位置是最后一个元素
    //尾指针左移一位
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    //取当前尾指针处元素
    E result = (E) elements[t];
    //如果队列为空返回null
    if (result == null)
        return null;
    //将当前尾指针处置为空
    elements[t] = null;
    //tail指向新的尾指针处
    tail = t;
    //返回取得的元素
    return result;
}

总结

1. 出队有两种方式，从队列头或者从队列尾
2. 通过取模的方式让头尾指针在数组范围内循环
3. 出队之后没有缩容

7.作为栈

Deque可以直接作为栈来使用，ArrayDeque的实现。

进栈

public void push(E e) {
    addFirst(e);
}

出栈

public E pop() {
    return removeFirst();
}

8.总结

1. ArrayDeque是采用数组方式实现的双端队列
2. ArrayDeque的出队入队是通过头尾指针循环利用数组实现的
3. ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍
4. ArrayDeque可以直接作为栈使用