目录

目录.png

---

简介

• AbstractQueue中add中满了会抛异常，offer不会。但ArrayDeque offer和add是一样的。
• Deque double ended queue双端队列的意思ArrayQueue, LinkedList都实现了Deque
• removeFirst, removeLast如果元素为null会抛异常， pollFirst, pollList元素为null不会跑异常
• add offer不允许添加null
• ArrayDeque实现是循环数组

继承体系

• Deque说明是双端队列， Cloneable可克隆实现的是深复制，Serializable表示可序列化。ArrayDeque是使用数组实现的双端队列

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

数据结构

// 存储元素的数组
transient Object[] elements; // non-private to simplify nested class access
// 队列头位置
transient int head;
// 队列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

构造方法

// 默认构造方法，初始容量为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;
    }
    return initialCapacity;
}

入队

• head指向头元素，从队尾开始往前加，tail指向尾元素后一个空的元素从队头开始往后加
• head开始是0， head - 1负1补码 & length -1就是数组最后个元素

• 参考文章2的图

  
  图示.png

// 从队列头入队
public void addFirst(E e) {
    // 不允许null元素
    if (e == null)
        throw new NullPointerException();
    // 将head指针减1并与数组长度减1取模
    // 这是为了防止数组到头了边界溢出, x & y - 1相当于 x % y
    // 如果到头了就从尾再向前
    // 相当于循环利用数组
    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();
}

扩容

• 参考文章3图示从上往下看的顺序看图

  
  图示.png

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];
    // 将旧数组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;
}

栈实现

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

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

---

参考文章

1. 死磕 java集合之ArrayDeque源码分析
2. Java进阶--ArrayDeque双端队列完全解析
3. 【源码解析】你真的了解ArrayDeque嘛？