ArrayDeque深度解析

概述

ArrayDeque这个容器不知道大家在平时的工作中使用的多吗？它是一个非常强大的容器，既可以作为队列实现FIFO先进先出的功能，也具备栈的功能实现FILO先进后出的功能，那么它究竟是怎么样的呢？性能又如何？

ArrayDeque介绍

ArrayDeque主要是基于数组实现的Deque(Double Ended Queue)双端队列，即双端队列，它既可以当作栈使用，也可以当作队列使用。

• ArrayDeque是一个没有容量限制的双端队列，底层是基于数组实现，会自动扩容。
• ArrayDeque不是线程安全的。
• ArrayDeque不可以存取null元素。
• 当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

以上是ArrayDeque的类结构图：

• 实现了Queue接口，它实际上是一个单端队列，只能操作队列的一端。
• 实现了Deque接口，Deque集成了Queue接口，有api可以同时操作队列的双端。
• 实现了Cloneable接口，说明该队列支持clone。
• 实现了Serializable接口，标记该接口支持序列化操作。

构造方法

方法	说明
ArrayDeque()	构造一个初始容量为16的数组双端队列
ArrayDeque(int numElements)	构造一个初始容量为numElements的数组双端队列
ArrayDeque(Collection<? extends E> c)	构造一个初始内容未c的数组双端队列

关键方法

添加相关方法

方 法	等价方法	说明
add(e)	addLast(e)	向队列尾部添加元素
offer(e)	offerLast(e)	向队列尾部添加元素
addFirst(e)	offerFirst(e)	向队列头部添加元素

• add前缀的方法，如果超过容量限制，添加失败，会抛出运行时异常
• offer前缀的方法，比较特殊，如果超过容量限制，会返回指定值true false

队列获取元素相关方法

方 法	等价方法	说明
remove()	removeFirst()	获取并且删除队列头部元素
poll()	pollFirst()	获取并且删除队列头部元素
removeLast()	pollLast()	获取并且删除队列尾部

• remove前缀的方法，如果容量为空，会抛出运行时异常
• offer前缀的方法，如果容量为空，会返回指定值null

查看相关方法

方 法	等价方法	说明
element()	getFirst()	查看队列头部元素
peek()	peekFirst()	查看队列头部元素
getLast()	peekLast()	查看队列尾部元素

• peek前缀的方法，如果容量为空，会返回指定true，false，其他方法失败会抛出异常。

栈相关方法

方 法	等价方法	说明
push(e)	addFirst(e)	向栈中添加元素
pop()	removeFirst()	获取栈顶元素
peek()	peekFirst()	查看栈顶元素

其他方法

方法	说明
removeFirstOccurrence(Object o)	删除队列中第一次相等的元素
removeLastOccurrence(Object o)	删除队列中最后一个相等的元素

tips：具体操作是返回指定值还是抛出异常，建议看源码的javadoc，写的非常清楚了。

使用案例

1. 测试队列功能

  @Test
    public void test1() {
        Deque<String> deque = new ArrayDeque<>();
        deque.add("1");
        deque.offer("2");
        deque.offerLast("3");
        System.out.println(deque);
        String poll = deque.poll();
        System.out.println(poll);
        System.out.println(deque);
    }

运行结果：

1. 测试栈的功能

@Test
    public void test2() {
        Deque<String> deque = new ArrayDeque<>();
        deque.push("1");
        deque.push("2");
        deque.push("3");
        String pop = deque.pop();
        System.out.println(pop);
    }

运行结果：

1. 测试存储null数据

@Test
    public void test3() {
        Deque<String> deque = new ArrayDeque<>();
        boolean offerResult = deque.offer(null);
        System.out.println(offerResult);
        System.out.println(deque);
    }

运行结果：

1. 测试poll和remove的区别

@Test
    public void test4() {
        Deque<String> deque = new ArrayDeque<>();
        String poll = deque.poll();
        //取出为null
        System.out.println(poll);

        // 因为容量为空了，会抛出异常
        String remove = deque.remove();
        System.out.println(remove);
        System.out.println(deque);
    }

运行结果:

核心机制

实现机制

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组，也就是说数组的任何一点都可能被看作起点或者终点。

上图中我们看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。

总的来说，ArrayDeque内部它是一个动态扩展的循环数组，通过head和tail变量维护数组的开始和结尾，数组长度为2的幂次方，使用高效的位操作进行各种判断，以及对head和tail的维护。

源码解析

• 构造放方法ArrayDeque(int numElements)

public ArrayDeque(int numElements) {
        // 初始化数组
        allocateElements(numElements);
    }

private void allocateElements(int numElements) {
        // 初始化数组，通过calculateSize方法计算数组长度
        elements = new Object[calculateSize(numElements)];
    }

private static int calculateSize(int numElements) {
        // 设置初始容量等于8
        int initialCapacity = MIN_INITIAL_CAPACITY;
        //  如果numElement大于等于初始容量        	
        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;
    }

是无符号右移操作，|是位或操作, 举个例子：

ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);

1. 程序运行到第五行时，numElements >= initialCapacity成立，10>=8，则会进入到if语句内部。
2. 程序运行到第六行时， initialCapacity = numElements，initialCapacity 设置为10，10的二进制表示方式是1010。
3. 程序运行到第七行时， initialCapacity无符号向右移动一位，1010无符号向右移动一位是0101，1010|0101=1111，十进制表示方式是15。
4. 程序运行到第八行时， initialCapacity无符号向右移动2位，1111无符号向右移动一位是0011，1111|0011=1111，十进制表示方式是15，一直持续下去都是15，当程序运行到第12行时，15进行加1操作，则变成16。这个时候16就是2的幂次方返回。

整体思路是每次移动将位数最高的值变成1，从而将二进制所有位数都变成1，变成1之后得到的十进制加上1之后得到值就是2的幂次方的值。最终，数组长度永远都是是2的幂次方。

• addFirst方法

 public void addFirst(E e) {
        // 如果元素为空则抛出空指针异常
        if (e == null)
            throw new NullPointerException();
        // 计算头指针的索引，并设置值
        elements[head = (head - 1) & (elements.length - 1)] = e;
        //如果头指针和尾指针相等，则进行扩容
        if (head == tail)
            // 扩容操作
            doubleCapacity();
    }

这里head = (head - 1) & (elements.length - 1)使用的很巧妙，我们举个例子来讲解：

  ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(10);
    arrayDeque.addFirst(5);

此时初始化时数组长度为16，头指针head和尾指针head默认是0，此时数组的内容如下所示：

现在来找执行addFirst操作后的head位置：

• 初始head = 0, head -1 = -1, 对应的补码是11111111
• elements.length 是16，elements.length - 1 是15，对应补码是00001111
• 将上面两个数字&操作后得到结果00001111，正好是15

小结： 这段代码相当于取余，因为数组容量是2的幂次方，减去1的二进制位都是1，与1相与相当于它本身，同时也处理为为-1的这种情况，非常的巧妙。

扩容操作：

在每次添加元素后，如果头索引和尾部索引相遇，则说明数组空间已满，需要进行扩容操作。 ArrayDeque 每次扩容都会在原有的容量上翻倍，这也是对容量必须是2的幂次方的保证。

private void doubleCapacity() {
        assert head == tail; //扩容时头部索引和尾部索引肯定相等
        int p = head;
        int n = elements.length;
        //头部索引到数组末端(length-1处)共有多少元素
        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;
    }

• pollLast()取元素

 public E pollLast() {
        //计算要取的元素索引
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        // 获取t位置的元素
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        // 重新设置t
        tail = t;
        return result;
    }

tail是指向下一个为空的位置，所以(tail - 1) & (elements.length - 1)相当于计算出上一个索引位置，获取其中的值，然后将元素设置为空。

总结

ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack；ArrayDeque和LinkedList也都实现了Deque接口，应该用哪一个呢？如果只需要Deque接口，从两端进行操作，一般而言，ArrayDeque效率更高一些，应该被优先使用，不过，如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除，则应该选LinkedList。

参考

blog.jrwang.me/2016/java-c…

www.cnblogs.com/carpenterle…

www.cnblogs.com/swiftma/p/6…