简介

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

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

它既可以作为队列也可以作为栈。

继承体系

ArrayDeque实现了 Deque接口，Deque接口继承自 Queue接口，它是对 Queue的一种增强。

同时实现了 Serializable和 Cloneable接口，可以进行序列化和克隆。

源码解读

主要属性

// 存储元素的数组

transient Object[] elements; // non-private to simplify nested class access

// 队列头位置

transient int head;

// 队列尾位置

transient int tail;

// 最小初始容量

private static final int MIN_INITIAL_CAPACITY = 8;

// 序列号

private static final long serialVersionUID = 2340985798034038923L;

head指向头元素

tail指向尾元素的下一个位置

这里注意到，head，tail，elements属性都被 transient修饰，不会参与序列化。

可能会有疑问，**elements**要是不参与序列化，集合内的数据不就无法持久化吗。

这个问题先放在这里，讲完 ArrayList扩容原理之后再进行回答。

构造方法

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

这里比较有意思的是 calculateSize容量计算方法，本质是为了获取大于当前数值的最小的2的幂，比如 3 算出来是 8，9 算出来是 16，33 算出来是 64。

由于 2 的幂用二进制表示的特点就是只有一个二进位位是 1 ，其余数位都是 0，所以从二进制的角度，分为两步操作

第一步：将该数二进制的最高位 1 之后的所有数位设置为 1（如果 numElements < 8 则直接返回 8）

// 第一步

0000 0001 0101 1110 1000 1111 0001 1010  // 原数

0000 0001 1111 1111 1111 1111 1111 1111  // 第一步完成

第二步：原数加一（如果小于 0，说明超过最大容量，整体右移一位）

// 第二步

0000 0001 1111 1111 1111 1111 1111 1111  // 第一步完成

0000 0010 0000 0000 0000 0000 0000 0000  // 第二部完成，成为 2 的幂

对于calculateSize 一种直接的想法是使用循环加位运算，找到最高位的二进制 1（形成独立的一个 2 的幂），然后将该数位左移一位返回，时间复杂度 O(n)，最坏情况下需要进行 31 次。

int tmp = 1 << 31;

int count = 31;

while ((numElements & tmp) == 0 && count > 0) {

    tmp >>>= 1;

    count--;

}

tmp <<= 1;

return tmp;

源码利用的是二分的思想，总共 32 位也就是 2 的 5 次方，只需要 5 次位运算即可，时间复杂度 O(logn)

0000 0001 0000 0000 0000 0000 0000 0000

0000 0000 1000 0000 0000 0000 0000 0000  >>> 1

0000 0001 1000 0000 0000 0000 0000 0000  |=

0000 0000 0110 0000 0000 0000 0000 0000  >>> 2

0000 0001 1110 0000 0000 0000 0000 0000  |=

0000 0000 0001 1110 0000 0000 0000 0000  >>> 4

0000 0001 1111 1110 0000 0000 0000 0000  |=

0000 0000 0000 0001 1111 1110 0000 0000  >>> 8

0000 0001 1111 1111 1111 1111 0000 0000  |=

0000 0000 0000 0000 0000 0001 1111 1111  >>> 16

0000 0001 1111 1111 1111 1111 1111 1111  |=

扩容

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;

}

扩容原理：集合满了之后，创建一个原数组容量 2 倍的集数组，然后把元素拷贝到新数组中。

数组拷贝使用的是 System.arraycopy函数

public static native void arraycopy(Object src,  int  srcPos,

                                    Object dest, int destPos,

                                    int length);

// src – the source array.

// srcPos – starting position in the source array.

// dest – the destination array.

// destPos – starting position in the destination data.

// length – the number of array elements to be copied.

ok，讲完扩容之后补一下坑，elements不参与序列化是从空间的角度考虑的，ArrayDeque的容量始终为 2 的幂，始终不是满的，有位置没有存放元素，如果是刚刚扩容完，可能有接近一半的空间未使用，如果参与序列化，会造成大量空间的浪费，消耗网络传输或者数据库传输，降低吞吐量。

解决方案是把集合拆分成几部分进行传输，而不是作为一个整体，来节约空间和减少序列化的时间

// 将 ArrayDeque 实例的状态保存到流（即序列化它）

private void writeObject(java.io.ObjectOutputStream s)

    throws java.io.IOException {

    // 写出当前类的所有非静态字段(non-static)和非瞬态字段(non-transient)到ObjectOutputStream

    s.defaultWriteObject();  

    // Write out size

    // 将size写出到ObjectOutputStream

    s.writeInt(size());

    // Write out elements in order.

    int mask = elements.length - 1;

    // i = (i + 1) & mask 表示循环数组下标的移动

    for (int i = head; i != tail; i = (i + 1) & mask)

        s.writeObject(elements[i]);  // 有序的将elementData中已使用的元素读出到流中

}

// 从流中重构 ArrayDeque 实例（即，对其进行反序列化）

private void readObject(java.io.ObjectInputStream s)

    throws java.io.IOException, ClassNotFoundException {

    // 读入size和非transient非static属性

    s.defaultReadObject();

    // Read in size and allocate array

    // 读入容量

    int size = s.readInt();

    // 重新分配容量

    int capacity = calculateSize(size);

    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);

    allocateElements(size);

    head = 0;

    tail = size;

    // Read in all elements in the proper order.

    // // 按正确的顺序读入所有元素。

    for (int i = 0; i < size; i++)

        elements[i] = s.readObject();

}

入队

// 从队列头入队

public void addFirst(E e) {

    // 不允许null元素

    if (e == null)

        throw new NullPointerException();

    // 将head指针减1并与数组长度减1取模

    // 这是为了防止数组到头了边界溢出

    // 如果到头了就从尾再向前

    // 相当于循环利用数组

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

}

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

public boolean add(E e) {

    addLast(e);

    return true;

}

public boolean offer(E e) {

    return offerLast(e);

}

public boolean offerFirst(E e) {

    addFirst(e);

    return true;

}

public boolean offerLast(E e) {

    addLast(e);

    return true;

}

剩下几种入队操作本质都是 addFirst 和 addLast ，不过是多了返回值。

出队

// 从队列头出队

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() {

    // 尾指针左移一位

    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;

}

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

// 移除队头元素

public E removeFirst() {

    E x = pollFirst();

    if (x == null)

        throw new NoSuchElementException();

    return x;

}

// 移除队尾元素

public E removeLast() {

    E x = pollLast();

    if (x == null)

        throw new NoSuchElementException();

    return x;

}

// 移除队头元素

public E remove() {

    return removeFirst();

}

// 移除队头元素

public E poll() {

    return pollFirst();

}

剩下几种出队操作本质是 pollFirst 和 pollLast，区别就是 remove*操作可能抛出 NoSuchElementException异常。

入栈

public void push(E e) {

    addFirst(e);

}

出栈

public E pop() {

    return removeFirst();

}

入栈和出栈操作本质都是操作队列头。

容量

public int size() {

    return (tail - head) & (elements.length - 1);

}

用与运算取代取模运算，速度更快。

查看两端元素

public E peekFirst() {

    // elements[head] is null if deque empty

    return (E) elements[head];

}

@SuppressWarnings("unchecked")

public E peekLast() {

    return (E) elements[(tail - 1) & (elements.length - 1)];

}

如果元素不存在，返回 null

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;

}

如果元素不存在，抛出 NoSuchElementException异常

是否为空

public boolean isEmpty() {

    return head == tail;

}

head和 tail相同时表示为空

清空

public void clear() {

    int h = head;

    int t = tail;

    // 如果 head == tail 则为空，直接返回，指向哪里无所谓，是循环数组

    if (h != t) { // clear all cells

        // 如果 head != tail 表示有元素，head 和 tail 都指向 0

        head = tail = 0;

        int i = h;

        int mask = elements.length - 1;

        // 从头元素开始循环清空数组

        do {

            elements[i] = null;

            i = (i + 1) & mask;

        } while (i != t);

    }

}

性能测试

ArrayDeque 与 LinkedList

ArrayDeque 跟同样实现了 Deque 接口的 LinkedList 对比。

二者都添加 200000 个数据。

long start = 0, end = 0;

start = System.currentTimeMillis();

LinkedList linkedList = new LinkedList();

for (int i=0; i<2000000; i++) {

    linkedList.addFirst(i);

}

end = System.currentTimeMillis();

System.out.println("LinkedList addFirst 2000000 cost time = " + (end-start) + "ms");

LinkedList addFirst 2000000 cost time = 351ms

long start = 0, end = 0;

ArrayDeque arrayDeque = new ArrayDeque();

start = System.currentTimeMillis();

for (int i=0; i < 2000000; i++){

    arrayDeque.addFirst(i);

}

end = System.currentTimeMillis();

System.out.println("ArrayDeque addFirst 2000000 cost time = " + (end-start) + "ms");

ArrayDeque addFirst 2000000 cost time = 20ms

可以看到，ArrayDeque是 LinkedList速度的 15 倍

二者都移除 200000 个数据。

start = System.currentTimeMillis();

while (linkedList.size() != 0) {

    linkedList.removeFirst();

}

end = System.currentTimeMillis();

System.out.println("LinkedList removeFirst cost time = " + (end-start) + "ms");

LinkedList removeFirst cost time = 21ms

start = System.currentTimeMillis();

while (arrayDeque.size() != 0) {

    arrayDeque.removeFirst();

}

end = System.currentTimeMillis();

System.out.println("ArrayDeque removeFirst cost time = " + (end-start) + "ms");

ArrayDeque removeFirst cost time = 10ms

可以看到，ArrayDeque是 LinkedList速度的 2 倍

巴特西

【Java集合】ArrayDeque源码解读

简介