1. Introduction

ArrayDeque s also known as Array Double Ended Queue. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue.
Few important features of ArrayDeque are as follows:
Null elements are prohibited in the ArrayDeque.

• List other collections, ArrayDeque is not thread-safe either.
• ArrayDeque class is likely to be faster than Stack when used as a stack.
• ArrayDeque class is likely to be faster than LinkedList when used as a queue.

首尾双端插入/删除时，LinkedList 指针额外消耗时间（allocation and GC）,ArrayDeque长度没有调整时不会启动GC。

2. Interfaces implemented by ArrayDeque

The ArrayDeque class implements these two interfaces:

• Queue Interface: It is an Interface which is a FIFO Data Structure where the elements are added from the back.

• Deque Interface: It is a Doubly Ended Queue in which you can insert the elements from both the sides. It is an interface that implements the Queue.

  栈操作：

• E pop()

• E peak()

• void push(E e)

  队列操作：

• boolean offer(E e)

• boolean offerLast(E e)
• E poll()
• E pollLast()
• E peek()

• E peekLast()

  3. 什么时候使用 LinkedList，什么时候使用 ArrayDeque?

  https://venus.cs.qc.cuny.edu/~mfried/cs313/list_comparison.html
  Sometimes it is difficult to predict which one is best without testing, but here are a few tips:

• Use an ArrayList if you need to access elements by index and you only need to insert/delete at the end.

• Use an ArrayDeque as a stack, queue or deque.
• Use a LinkedList when you need to add/remove elements from the middle of the list too often or if you need insertion at the ends to be worst-case O(1).

  4. 实现原理

  实现原理： https://www.cnblogs.com/loveLands/articles/9708717.html

  从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
  
  
  
  head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail不一定总是比head大。
  
  addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[—head] = e即可。
  实际需要考虑：1.空间是否够用 2.下标是否越界的问题
  
  空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
  
  下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数（其实只可能是-1），则相当于对其取相对于elements.length的补码。
  
  扩容函数doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。过程如下图所示：
  
  复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。