概述
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，写的非常清楚了。
使用案例
- 测试队列功能
@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); }
运行结果：
- 测试栈的功能
@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); }
运行结果：
- 测试存储null数据
@Test public void test3() { Deque<String> deque = new ArrayDeque<>(); boolean offerResult = deque.offer(null); System.out.println(offerResult); System.out.println(deque); }
运行结果：
- 测试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);
- 程序运行到第五行时，numElements >= initialCapacity成立，10>=8，则会进入到if语句内部。
- 程序运行到第六行时， initialCapacity = numElements，initialCapacity 设置为10，10的二进制表示方式是1010。
- 程序运行到第七行时， initialCapacity无符号向右移动一位，1010无符号向右移动一位是0101，1010|0101=1111，十进制表示方式是15。
- 程序运行到第八行时， 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。
