队列(queue)是一种常用的数据结构，插入在尾部，删除在头部。就像排队打饭一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人。该结构遵循的先进先出原则。

Queue接口（单向队列）

它是集合框架Collection的子接口，基于链表来进行实现的单向队列。LinkedList接口，实现了Deque(双向队列)接口，而Deque继承了Queue接口，所以LinkedList，不管在列表头部或列表尾部或列表中的任意位置执行插入和删除操作，效率会比较高。

  1. public interface Queue<E> extends Collection<E> {
  2.     //往队列插入元素，如果出现异常会抛出异常
  3.     boolean add(E e);
  4.     //往队列插入元素，如果出现异常则返回，如果成功，则返回true。
  5.     boolean offer(E e);
  6.     //移除队列元素，如果出现异常会抛出异常
  7.     E remove();
  8.     //移除队列元素，如果出现异常则返回null
  9.     E poll();
  10.     //获取队列头部元素，如果出现异常会抛出异常
  11.     E element();
  12.     //获取队列头部元素，但不进行删除操作。如果出现异常则返回null
  13.     E peek();
  14. }

Deque接口（双向队列）

Deque接口，是Queue接口的子接口，是指队列两端的元素，既能入队（offer）也能出队。
如果将Deque限制为只能从一端进行入队和出队，就是栈的数据结构的实现。对于栈而言，有入栈（push）和出栈（pop），遵循先进后出的规则。

  1. public interface Deque<E> extends Queue<E> {
  2.     //插入头部，异常会报错
  3.     void addFirst(E e);
  4.     //插入头部，异常返回false
  5.     boolean offerFirst(E e);
  6.     //获取头部，异常会报错
  7.     E getFirst();
  8.     //获取头部，异常不报错
  9.     E peekFirst();
  10.     //移除头部，异常会报错
  11.     E removeFirst();
  12.     //移除头部，异常不报错
  13.     E pollFirst();
  14.     //插入尾部，异常会报错
  15.     void addLast(E e);
  16.     //插入尾部，异常返回false
  17.     boolean offerLast(E e);
  18.     //获取尾部，异常会报错
  19.     E getLast();
  20.     //获取尾部，异常不报错
  21.     E peekLast();
  22.     //移除尾部，异常会报错
  23.     E removeLast();
  24.     //移除尾部，异常不报错
  25.     E pollLast();
  26. }

ArrayDeque是什么

ArrayDeque类是双端队列的实现类，类的继承结构如下面，继承自AbastractCollection（该类实现了部分集合通用的方法，其实现了Collection接口）。其实现的接口Deque接口中定义了双端队列的主要的方法，比如从头删除，从尾部删除，获取头数据，获取尾部数据等等。

  1. public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{}

ArrayDeque基本特征

就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。就是数组实现的双向队列。

  1. 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下）
  2. 非线程安全的，不支持并发访问和修改。
  3. 支持fast-fail（java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。抛出ConcurrentModificationException异常，产生fail-fast事件。）
  4. 作为栈使用的话比栈要快。
  5. 当队列使用比linklist要快。
  6. null元素被禁止使用。

ArrayDeque的成员变量

  1. //数组存储元素
  2. transient Object[] elements;
  3. //头部元素索引
  4. transient int head;
  5. //尾部元素索引
  6. transient int tail;
  7. //最小容量
  8. private static final int MIN_INITIAL_CAPACITY = 8;

ArrayDeque底层使用数组存储元素，同时还使用head和tail来表示索引，但注意tail不是尾部元素的索引，而是尾部元素的下一位，即下一个将要被加入的元素的索引。

ArrayDeque的初始化

  1. public ArrayDeque() {
  2.     elements = new Object[16];
  3. }
  5. public ArrayDeque(int numElements) {
  6.     allocateElements(numElements);
  7. }
  9. public ArrayDeque(Collection<? extends E> c) {
  10.     allocateElements(c.size());
  11.     addAll(c);
  12. }
  14. private void allocateElements(int numElements) {
  15.     int initialCapacity = MIN_INITIAL_CAPACITY;
  16.     // 如果给的参数 大于等于 8(最小容量)
  17.     if (numElements >= initialCapacity) {
  18.         initialCapacity = numElements;
  19.         initialCapacity |= (initialCapacity >>>  1);
  20.         initialCapacity |= (initialCapacity >>>  2);
  21.         initialCapacity |= (initialCapacity >>>  4);
  22.         initialCapacity |= (initialCapacity >>>  8);
  23.         initialCapacity |= (initialCapacity >>> 16);
  24.         initialCapacity++;
  26.         if (initialCapacity < 0)   // Too many elements, must back off
  27.             initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
  28.     }
  29.     elements = new Object[initialCapacity];
  30. }
  32. 如果initialCapacity为10的时候，那么二进制为 1010
  33. 经过initialCapacity |= (initialCapacity >>>  1)时，那么二进制为 1010 | 0101 = 1111
  34. 经过initialCapacity |= (initialCapacity >>>  2)时，那么二进制为 1111 | 0011 = 1111
  35. 后面计算的结果都是1111，可以理解为将二进制的低位数都补上1，这样出来的结果都是2^n-1
  36. 最后initialCapacity++，2^n-1+1出来的结果就是2^n

ArrayDeque的插入

  1. /**
  2.  * addFirst方法中使用了head-1和length-1相与的形式来计算，
  3.  * 那么，length-1这里是多少，因为规定了length必须是2的幂次，
  4.  * 所以length-1后二进制低位将全部为1，然后与head-1相与相当于对其进行取模。
  5.  */
  6. public void addFirst(E e) {
  7.     if (e == null)
  8.         throw new NullPointerException();
  9.     elements[head = (head - 1) & (elements.length - 1)] = e;
  10.     if (head == tail)
  11.         doubleCapacity();
  12. }
  14. public void addLast(E e) {
  15.     if (e == null)
  16.         throw new NullPointerException();
  17.     //tail中保存的是即将加入末尾的元素的索引
  18.     elements[tail] = e;
  19.     //tail向后移动一位
  20.     if ( (tail = (tail + 1) & (elements.length - 1)) == head)
  21.         //tail和head相遇，空间用尽，需要扩容
  22.         doubleCapacity();
  23. }
  25. 在存储的过程中，这里有个有趣的算法，
  26. 就是tail的计算公式(tail = (tail + 1) & (elements.length - 1))，
  27. 注意这里的存储采用的是环形队列的形式，也就是当tail到达容量最后一个的时候，
  28. tail就为等于0，否则tail的值tail+1
  30. (tail = (tail + 1) & (elements.length - 1))
  31. 证明：(elements.length - 1) = 2^n-1 即二进制的所有低位都为1，假设为 11111111
  32. 假设：tail为最后一个元素，则(tail + 1)为 (11111111 + 1) = 100000000
  33. 结果：(tail + 1) & (elements.length - 1) = 000000000，tail下一个要添加的索引为0

ArrayDeque的扩容

  1. /**
  2.  * 之所以说该ArrayDeque容量无限制，是因为只要检测到head==tail的时候，就直接调用doubleCapacity方法进行扩容。 
  3.  * 这个时候将数组展开，head和tail指向的是同一个位置，
  4.  * 那么，因为是循环数组，所以head左边可能存在一部分元素为p个，右边也可能存在一部分数据r=n-p个，
  5.  * 右边的部分复制到从0到r,左边的部分复制到从r到结束。这样原来的数据从0开始往下排列。
  6.  */
  7. private void doubleCapacity() {
  8.     assert head == tail; //扩容时头部索引和尾部索引肯定相等
  9.     int p = head;
  10.     int n = elements.length;
  11.     //头部索引到数组末端(length-1处)共有多少元素
  12.     int r = n - p; // number of elements to the right of p
  13.     //容量翻倍
  14.     int newCapacity = n << 1;
  15.     //容量过大，溢出了
  16.     if (newCapacity < 0)
  17.         throw new IllegalStateException("Sorry, deque too big");
  18.     //分配新空间
  19.     Object[] a = new Object[newCapacity];
  20.     //复制头部索引到数组末端的元素到新数组的头部
  21.     System.arraycopy(elements, p, a, 0, r);
  22.     //复制其余元素
  23.     System.arraycopy(elements, 0, a, r, p);
  24.     elements = a;
  25.     //重置头尾索引
  26.     head = 0;
  27.     tail = n;
  28. }

ArrayDeque的删除

ArrayDeque支持从头尾两端移除元素，remove方法是通过poll来实现的。因为是基于数组的，在了解了环的原理后这段代码就比较容易理解了

  1. /**
  2.  * 中间判断是不是null，可以看出该队列不支持null,
  3.  * 通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。
  4.  */
  5. public E pollFirst() {
  6.     int h = head;
  7.     @SuppressWarnings("unchecked")
  8.     E result = (E) elements[h];
  9.     // Element is null if deque empty
  10.     if (result == null)
  11.         return null;
  12.     elements[h] = null;     // Must null out slot
  13.     head = (h + 1) & (elements.length - 1);
  14.     return result;
  15. }
  17. public E pollLast() {
  18.     int t = (tail - 1) & (elements.length - 1);
  19.     @SuppressWarnings("unchecked")
  20.     E result = (E) elements[t];
  21.     if (result == null)
  22.         return null;
  23.     elements[t] = null;
  24.     tail = t;
  25.     return result;
  26. }
  28. /**
  29.  * 删除元素的基本思路为确定那一侧的数据少，少的一侧移动元素位置，
  30.  * 这样效率相对于不比较更高些，然后，判断head是跨越最大值还是为跨越最大值，
  31.  * 继而可以分两种不同的情况进行拷贝。但是该方法比较慢，因为存在数组的拷贝。
  32.  */
  33. private boolean delete(int i) {
  34.     checkInvariants();
  35.     final E[] elements = this.elements;
  36.     final int mask = elements.length - 1;
  37.     final int h = head;
  38.     final int t = tail;
  39.     final int front = (i - h) & mask;
  40.     final int back  = (t - i) & mask;
  42.     // Invariant: head <= i < tail mod circularity
  43.     if (front >= ((t - h) & mask))
  44.         throw new ConcurrentModificationException();
  46.     // Optimize for least element motion
  47.     // 为了最小的拷贝数据
  48.     if (front < back) {
  49.         // 递增的顺序时
  50.         if (h <= i) {
  51.             // 删除部分前面的向后移动
  52.             System.arraycopy(elements, h, elements, h + 1, front);
  53.         } else { // Wrap around
  54.             // 跨越最小与最大值
  55.             // 分两次拷贝
  56.             System.arraycopy(elements, 0, elements, 1, i);
  57.             // 最大的地方单独处理
  58.             elements[0] = elements[mask];
  59.             // 前面的部分向后移动一位
  60.             System.arraycopy(elements, h, elements, h + 1, mask - h);
  61.         }
  62.         elements[h] = null;
  63.         head = (h + 1) & mask;
  64.         return false;
  65.     } else {
  66.         // 递增的顺序时
  67.         if (i < t) { // Copy the null tail as well
  68.             // 拷贝i后面的部分数据前置
  69.             System.arraycopy(elements, i + 1, elements, i, back);
  70.             tail = t - 1;
  71.         } else { // Wrap around
  72.             // 跨越中间最大值的时候
  73.             // 后面向前拷贝
  74.             // 0处的值单独处置放在最大的下标处
  75.             // 后面的部分从1开始向前移动一个，原来的1在0处
  76.             System.arraycopy(elements, i + 1, elements, i, mask - i);
  77.             elements[mask] = elements[0];
  78.             System.arraycopy(elements, 1, elements, 0, t);
  79.             tail = (t - 1) & mask;
  80.         }
  81.         return true;
  82.     }
  83. }

ArrayDeque的查询

@SuppressWarnings("unchecked")
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)];
}

ArrayDeque是Deque接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于Stack；ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的LinkedList也要更好一些。