1. ArrayDeque简介
ArrayDeque是基于数组实现的一种双端队列，既可以当成普通的队列用（先进先出），也可以当成栈来用（后进先出），故ArrayDeque完全可以代替Stack，ArrayDeque是非线程安全的，Stack是线程安全的。
ArrayDeque虽然是基于数组实现的，但很容易被数组这种数据结构所迷惑。因为数组是从0开始到length-1位置结束的，但ArrayDeque的实现实际上是一种循环结构的队列，首尾位置完全靠head和tail两个首尾指针来决定的，正常理解的情况下head的值应该比tail小，但是这里会出现head比tail大的情况。所以这里我们不能以正常数组的角度去看待，我可以把这个数组看成一个环形结构的首尾相连的结构，即数组最后一位的下一位就是第一位（不要习惯性把0当成头部，length-1当成尾部），数据都存储在head右边及tail的左边，不知道有没有说清楚~~
除此之外，ArrayDeque对队列的容量有特殊的要求，必须是2^n（这里和HashMap类似），由于2^31超出int的最大值，故ArrayDeque的最大容量为2^30。ArrayDeque不允许存储null值，原因是需要通过取出的元素是否为null来判断队列是否为空。
关于更多关于ArrayDeque的讲解，这篇文章讲的很好：
2. ArrayDeque继承关系
ArrayDeque继承自AbstractCollection，实现了Deque、Cloneable、java.io.Serializable接口。
继承自AbstractCollection表明ArrayDeque是一个集合，并且拥有AbstractCollection的全部API。
实现了Deque接口，表明ArrayDeque是一个双端队列，实现了双端队列相关操作。
实现了Cloneable接口：可以调用Object.clone方法返回该对象的浅拷贝。
实现了 java.io.Serializable 接口：可以启用其序列化功能，能通过序列化去传输。
3. ArrayDeque实现
1. 核心参数
//存储数据，同包类可访问，不可被序列化 transient Object[] elements; //头部指针，不可被序列化 transient int head; //尾部指针，不可被序列化 transient int tail; //最小初始容量 private static final int MIN_INITIAL_CAPACITY = 8;
ArrayDeque底层通过数组进行数据存储，通过head和tail两个指针实现了双端队列，并且定义了最小的初始容量为8。
2. 构造方法
//无参构造，默认创建一个容量为16的数组 public ArrayDeque() { elements = new Object[16]; } //传入一个数值，根据这个数值计算出适合的初始容量 public ArrayDeque(int numElements) { allocateElements(numElements); } //传入一个集合，根据集合的大小计算出合适的初始容量，并将集合中的所有元素添加进来 public ArrayDeque(Collection c) { allocateElements(c.size()); addAll(c); } 3. 核心方法
//这里为什么用private static修饰？ //通过一系列位运算得到大于numElements的最小2的次幂 private static int calculateSize(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; //如果numElements >= initialCapacity则计算合适的初始容量，否则直接返回默认初始容量 if (numElements >= initialCapacity) { initialCapacity = numElements; //与'+='符号类似，a |= b 等效于 a = a | b, 这里进行的是二进制的或运算 //假设initialCapacity = 24, 二进制数值为 00011000; //initialCapacity >>> 1 二进制数值为 00001100; // 00011000 | 00001100 = 00011100; 28 initialCapacity |= (initialCapacity >>> 1); // 00011100 >>> 2 = 00000111; // 00011100 | 00000111 = 00011111; 31 initialCapacity |= (initialCapacity >>> 2); //00011111 >>> 4 = 00000001; //00011111 | 00000001 = 00011111; 31 initialCapacity |= (initialCapacity >>> 4); //... initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); //int为32位 通过这连续几次左移操作总共左移了31位（1+2+4+8+16 = 31） //将二进制数从第一个不为0的位开始后面每一位都变成1 //最后再加1取得比numElements大的最小2的次幂 initialCapacity++; //initialCapacity超出int最大值时，左移一位（除以2），最大容量为2 ^ 30 if (initialCapacity < 0) initialCapacity >>>= 1; } return initialCapacity; } //新建一个数组来保证容量足够容纳numElements个元素 private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; } //将底层数组扩容1倍 private void doubleCapacity() { //断言，当head == tail为true时才会向下执行，否则抛出AssertionError并终止执行 //当head == tail时表明底层数组已经满了 assert head == tail; int p = head; // 记录数组的长度 int n = elements.length; //这里取head右边数据的个数，由于是双端队列，数据从数组两端都可以添加数据（这里的数组可以看成首尾相连的循环数组，即element.length + 1 = 0） //既可以在下标为0的位置开始向后添加元素，也可以从n-1位置依次向前添加元素 //如addFirst方法是从数组最后一位开始添加数据的，head初始值为0，第一次调用时会变成n，之后每添加一次head-1 //addLast方法则从第一位开始添加数据，tail初始值为0，每次添加元素tail+1 int r = n - p; // number of elements to the right of p // 将数组长度扩大2倍 int newCapacity = n << 1; //如果扩容后超出int最大值则抛出异常 if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); //新建一个数组，容量为当前前的2倍 Object[] a = new Object[newCapacity]; //将head后面的元素拷贝到新数组的开始位置 System.arraycopy(elements, p, a, 0, r); //将head前面的元素拷贝到新数组的开始位置 System.arraycopy(elements, 0, a, r, p); //将底层数组替换成扩容后的数组 elements = a; //head重置为0 head = 0; //tail重置为最后一个位置索引+1 tail = n; } //内部拷贝元素 private T[] copyElements(T[] a) { //双端循环队列，元素存在head右边和tail的左边 //当head tail) { int headPortionLen = elements.length - head; System.arraycopy(elements, head, a, 0, headPortionLen); System.arraycopy(elements, 0, a, headPortionLen, tail); } return a; } //从队列头部添加元素e，插入null元素会报空指针异常 public void addFirst(E e) { if (e == null) throw new NullPointerException(); //如果elements.length = 16，则 element.length - 1 = 15,转为二进制 00000000 00000000 00000000 00001111 //第一次添加时head=0 head - 1 = -1 （1的反码再取补码）转为二进制 11111111 11111111 11111111 11111111 // 00000000 00000000 00000000 00001111 // & 11111111 11111111 11111111 11111111 // = 00000000 00000000 00000000 00001111 （15） //第二次添加时head=15 head - 1 = 14 转为二进制 00000000 00000000 00000000 00001110 // 00000000 00000000 00000000 00001110 // & 11111111 11111111 11111111 11111111 // = 00000000 00000000 00000000 00001110 （14） //从上面可以看出，head = (head - 1) & (elements.length - 1)实际上就是从数据最后一位开始依次向前添加元素 elements[head = (head - 1) & (elements.length - 1)] = e; //当head==tail时说明数组已经装满了，需要进行扩容 if (head == tail) doubleCapacity(); } //从队列尾部添加元素e，插入null元素会报空指针异常 public void addLast(E e) { if (e == null) throw new NullPointerException(); //第一次添加时tail=0，从数组第一次依次添加元素 elements[tail] = e; //是不是想这里为什么要这样做，tail + 1不是就够了吗？ //这里是考虑head值为0的情况，设elements.length = 16，当head为0，tail当前值为15时 //实际上数组这时已经满了，但是怎么判断数组满了呢? //tail + 1 = 16, elements.length - 1 = 15， head = 0 // 00010000 & 00001111 = 00000000 == head //这里是一处非常巧妙的做法，简单一行做了很多事 将tail+1的同时还能判断数组有没有满 //与运算又能提高程序效率，真是一举多得!!! //需要注意的是，这里是把元素放在tail位置之后再把tail+1的，也就是说tail下标位置是没有值的，也就是含头不含尾 if ( (tail = (tail + 1) & (elements.length - 1)) == head) //扩容1倍 doubleCapacity(); } //从队列头部添加元素e，插入null元素会报空指针异常，跟addFirst不同的是返回布尔值 public boolean offerFirst(E e) { addFirst(e); return true; } //从队列尾部添加元素e，插入null元素会报空指针异常，跟addLast不同的是返回布尔值 public boolean offerLast(E e) { addLast(e); return true; } //将队列首部的元素取出并移除 public E removeFirst() { E x = pollFirst(); //x==null，说明队列为空 if (x == null) throw new NoSuchElementException(); return x; } //将队列首部的元素取出并移除 public E pollFirst() { int h = head; @SuppressWarnings("unchecked") //将队列头部的元素赋值给result E result = (E) elements[h]; //result为null说明队列为空 if (result == null) return null; //将头部元素置空 elements[h] = null; //将头部指针向右移一位 head = (h + 1) & (elements.length - 1); return result; } //将队列尾部元素取出并移除 public E pollLast() { //当tail>0时，直接取tail - 1位置元素，tail位置为null //当tail=0时，取elements.length - 1处元素 int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; //result为null说明队列为空 if (result == null) return null; //将头部元素置空 elements[t] = null; //将取出到的元素位置索引赋给tail，tail处值为null，含头不含尾 tail = t; return result; } //获取队列头部元素，不删除，没有则抛出异常 public E getFirst() { @SuppressWarnings("unchecked") E result = (E) elements[head]; if (result == null) throw new NoSuchElementException(); return result; } //获取队列尾部元素，不删除，没有则抛出异常 public E getLast() { @SuppressWarnings("unchecked") E result = (E) elements[(tail - 1) & (elements.length - 1)]; if (result == null) throw new NoSuchElementException(); return result; } //获取队列头部元素，不删除 public E peekFirst() { // elements[head] is null if deque empty return (E) elements[head]; } //获取队列尾部元素，不删除 public E peekLast() { return (E) elements[(tail - 1) & (elements.length - 1)]; } //移除队列中从头部开始第一次出现的元素o，equals比较 public boolean removeFirstOccurrence(Object o) { //队列中不存在null元素 if (o == null) return false; //取底层数组的最后一位 int mask = elements.length - 1; //取队列首部的位置 int i = head; //声明一个x变量，用来存储遍历的元素，避免在循环中多次声明 Object x; //遍历队列，为空说明没有元素，结束遍历 while ( (x = elements[i]) != null) { //找到第一个相同的元素，直接删除并返回true if (o.equals(x)) { delete(i); return true; } //没找到，继续遍历，当遍历到最后一个元素时，下个元素下标为0 //如果elements.length=16,当 i = mask 时，i + 1 = 16, mask = 15 // 00010000 & 00001111 = 00000000 i = (i + 1) & mask; } return false; } //移除队列中从尾部开始第一次出现的元素o，equals比较 public boolean removeLastOccurrence(Object o) { //队列中不存在null元素 if (o == null) return false; //取底层数组的最后一位 int mask = elements.length - 1; //从tail-1位置开始遍历，当tail=0时，从最后一位开始 int i = (tail - 1) & mask; //声明一个x变量，用来存储遍历的元素，避免在循环中多次声明 Object x; //遍历队列，为空说明没有元素，结束遍历 while ( (x = elements[i]) != null) { //找到第一个相同的元素，直接删除并返回true if (o.equals(x)) { delete(i); return true; } //没找到，继续遍历，当遍历到下标为0时，下个元素为最后一个元素 i = (i - 1) & mask; } return false; } //从队列尾部添加元素e，插入null元素会报空指针异常，跟addLast不同的是返回布尔值 public boolean add(E e) { addLast(e); return true; } //从队列尾部添加元素e，插入null元素会报空指针异常，跟addLast不同的是返回布尔值 public boolean offer(E e) { return offerLast(e); } //移除队列首部元素并返回 public E remove() { return removeFirst(); } //将队列首部的元素取出并移除 public E poll() { return pollFirst(); } //获取队列头部元素，不删除 public E element() { return getFirst(); } //获取队列尾部元素，不删除 public E peek() { return peekFirst(); } //从队列头部添加元素e，插入null元素会报空指针异常 public void push(E e) { addFirst(e); } //移除队列首部元素并返回 public E pop() { return removeFirst(); } //检查队列中的元素是否正常 private void checkInvariants() { assert elements[tail] == null; assert head == tail ? elements[head] == null : (elements[head] != null && elements[(tail - 1) & (elements.length - 1)] != null); assert elements[(head - 1) & (elements.length - 1)] == null; } //根据下标删除一个元素 private boolean delete(int i) { //检查队列中的元素是否正常 checkInvariants(); //用一堆final变量来存储当前队列内部数据 //数组 final Object[] elements = this.elements; //数组最后一位 final int mask = elements.length - 1; //队列头部 final int h = head; //队列尾部 final int t = tail; //设elements.length=16, h=11,t=9,i=13，mask主要是通过与运算将其中的负数转为正数 //i-h=2 //故这里的front其实就是指的要删除的位置前面有几个元素 final int front = (i - h) & mask; //t-i=-4, 二进制0100 取反-> 1011 加1-> 1100 即12 //故这里的back其实就是指的要删除的位置后面有几个元素 final int back = (t - i) & mask; // t-h=-2 二进制0010 取反-> 1101 加1-> 1110 即14 //(t - h) & mask)主要是为了计算队列中元素个数 //所以这里要删除的元素前面的元素肯定要小于总元素个数 if (front >= ((t - h) & mask)) throw new ConcurrentModificationException(); // 要删除的元素位置右边的元素个数小于左边的情况 if (front < back) { //如果要删除的元素在head-mask之间，把head位置和要删除的元素之间的元素右移一位即可 if (h <= i) { System.arraycopy(elements, h, elements, h + 1, front); } else { //把要删除的元素到0位置的i个元素先右移一位 System.arraycopy(elements, 0, elements, 1, i); //再把最后一位元素移到第一位 elements[0] = elements[mask]; //最后把head后面的元素右移一位 System.arraycopy(elements, h, elements, h + 1, mask - h); } //把head位置元素置空null elements[h] = null; //重新计算head的位置 head = (h + 1) & mask; return false; // 要删除的元素位置右边的元素个数大于左边的情况 } else { //要删除的元素在0-tail之间,把i+1位置到tail之间的元素都右移一位 if (i < t) { System.arraycopy(elements, i + 1, elements, i, back); tail = t - 1; } else { //要删除的元素在head-mask之间，把i+1到mask之间的元素都左移一位 System.arraycopy(elements, i + 1, elements, i, mask - i); //再把第一位的元素放到最后一位 elements[mask] = elements[0]; //最后把1到tail之间的元素全部左移一位 System.arraycopy(elements, 1, elements, 0, t); //重新计算tail的位置 tail = (t - 1) & mask; } return true; } } //获取队列大小 public int size() { return (tail - head) & (elements.length - 1); } //判断队列是否为空，默认head=0，tail=0，即head=tail，添加元素后head=tail时会自动扩容 public boolean isEmpty() { return head == tail; } //返回一个迭代器 public Iterator iterator() { return new DeqIterator(); } //判断队列中是否包含元素o，equals比较 public boolean contains(Object o) { //队列中不存在null元素 if (o == null) return false; //取数组最后一个位置 int mask = elements.length - 1; //取队列头部 int i = head; //声明一个x变量，用来存储遍历的元素，避免在循环中多次声明 Object x; //从头部开始遍历，遇到null元素则停止遍历 while ( (x = elements[i]) != null) { //含有元素o，返回true if (o.equals(x)) return true; //否则取下一位元素 i = (i + 1) & mask; } return false; } //移除队列中从头部开始第一次出现的元素o，equals比较 public boolean remove(Object o) { return removeFirstOccurrence(o); } //清空队列 public void clear() { int h = head; int t = tail; if (h != t) { // clear all cells //重置head与tail到初始状态 head = tail = 0; int i = h; int mask = elements.length - 1; //从头部开始遍历，直到尾部停止 do { //将元素依次置为空 elements[i] = null; //获取下个元素位置 i = (i + 1) & mask; } while (i != t); } } //将队列转为Object数组并返回 public Object[] toArray() { return copyElements(new Object[size()]); } //将队列转为指定类型数组并返回 public T[] toArray(T[] a) { int size = size(); if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); copyElements(a); if (a.length > size) a[size] = null; return a; } //克隆一份队列，浅克隆 public ArrayDeque clone() { try { @SuppressWarnings("unchecked") ArrayDeque result = (ArrayDeque ) super.clone(); result.elements = Arrays.copyOf(elements, elements.length); return result; } catch (CloneNotSupportedException e) { throw new AssertionError(); } } //序列化队列 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); // Write out size s.writeInt(size()); // Write out elements in order. int mask = elements.length - 1; for (int i = head; i != tail; i = (i + 1) & mask) s.writeObject(elements[i]); } //反序列化队列 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { 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(); }