简介
双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。
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要是不参与序列化，集合内的数据不就无法持久化吗。
这个问题先放在这里，讲完 ArrayDeque扩容原理之后再进行回答。
构造方法
// 默认构造方法，初始容量为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 倍
