ArrayDeque使用&实现原理分析
学习Okhttp实现源码时，发现其任务分发时用到了ArrayDeque。因此了解一下ArrayDeque的使用方式和实现原理。
一、Dequedeque（double-ended queue）双端队列，是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。假设两端分别为端点A和端点B，在实际应用中：
可以有输出受限的双端队列（即端点A允许插入和删除，端点B只允许插入的双端队列）；
可以有输入受限的双端队列（即端点A允许插入和删除，端点B只允许删除的双端队列）；
如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈；
deque（double-ended queue）也是一种队列，了解deque时首先需要回忆一下queue的使用和实现原理。
对于Queue（先进先出）的详细使用方式和实现原理，可参考文章：
BlockingQueue使用方式 及 源码阅读
https://blog.csdn.net/xiaxl/article/details/80774479
Deque实现了以下功能方法，供开发者使用：
// 源码来自：android-29/java/util/Deque public interface Deque<E> extends java.util.Queue<E> { /** * 添加元素 */ // 在队列前边 添加元素，返回是否添加成功 boolean offerFirst( E e); // 在队列后边 添加元素，返回是否添加成功 boolean offerLast( E e); // 在队列前边 添加元素 void addFirst(E e); // 在队列后边添加元素 void addLast( E e); /** * 删除元素 */ // 删除第一个元素，返回删除元素的值；如果元素为null，将返回null； E pollFirst(); // 删除最后一个元素，返回删除元素的值；如果为null，将返回null； E pollLast(); // 删除第一个元素，返回删除元素的值；如果元素为null，将抛出异常； E removeFirst(); // 删除最后一个元素，返回删除元素的值；如果为null，将抛出异常； E removeLast(); // 删除第一次出现的指定元素 boolean removeFirstOccurrence( java.lang.Object o); // 删除最后一次出现的指定元素 boolean removeLastOccurrence( java.lang.Object o); /** * 取数据 */ // 获取第一个元素，没有返回null； E peekFirst(); // 获取最后一个元素，没有返回null； E peekLast(); // 获取第一个元素,如果没有则抛出异常; E getFirst(); // 获取最后一个元素，如果没有则抛出异常； E getLast(); /** * 队列方法------------------------------------------ */ // 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败则返回false是。 boolean offer(E e); // 删除队列头的元素，如果队列为空，则返回null； E poll(); // 返回队列头的元素，如果队列为空，则返回null； E peek(); // 向队列中添加一个元素。若添加成功则返回true；若因为容量限制添加失败，则抛出IllegalStateException异常。 boolean add(E e); // 删除队列头的元素，如果队列为空，则抛出异常； E remove(); // 返回队列头的元素，如果队列为空，将抛异常； E element(); /** * 堆栈方法------------------------------------------ */ // 栈顶添加一个元素 void push( E e); // 移除栈顶元素,如果栈顶没有元素将抛出异常 E pop(); } 二、ArrayDeque 源码学习 2.1、变量说明 // 源码来自：android-29/java/util/ArrayDeque // 用数组存放队列元素； transient Object[] elements; // 头部index transient int head; // 下一个要添加到尾步的index (除tail=0时，当前的尾部为tail-1)； transient int tail;head 与 tail 对应的index位置示例如下图所示：
addFirst 方法：在队列前面 添加元素；
代码实现中：从数组的末尾向前添加数据，如上图添加顺序为 E1、E2、...；
addLast方法：在队列后面 添加元素；
代码实现中：在数组的前边向后添加数据，如上图添加顺序为 Ea、Eb、...；
head 为当前头部的index；
tail 为下一个要添加的尾部的index；
2.2、构造方法 // 源码来自：android-29/java/util/ArrayDeque // 构造方法：默认数组长度为8 public ArrayDeque() { // 创建一个长度为16的数组 elements = new Object[16]; } // 构造方法：根据自定义长度 分配数组空间 public ArrayDeque(int numElements) { // 根据输入长度 分配数组空间 allocateElements(numElements); } // 找到大于需要长度的最小的2的幂整数 private void allocateElements(int numElements) { // MIN_INITIAL_CAPACITY为8 int initialCapacity = MIN_INITIAL_CAPACITY; // 假设用户输入的为9 if (numElements >= initialCapacity) { // initialCapacity = 9; initialCapacity = numElements; // initialCapacity = 9 | ( 9 >>> 1) // initialCapacity = ( 1001 ) | ( 0100 ) = 1101 = 13; initialCapacity |= (initialCapacity >>> 1); // initialCapacity = 13 | ( 13 >>> 2) // initialCapacity = ( 1101 ) | ( 0011 ) = 1111 = 15; initialCapacity |= (initialCapacity >>> 2); // initialCapacity = 15 | ( 15 >>> 4) // initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15; initialCapacity |= (initialCapacity >>> 4); // initialCapacity = 15 | ( 15 >>> 8) // initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15; initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); // 15+1 = 16; initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1; // Good luck allocating 2^30 elements } // 创建数组（数组的长度为：大于需要长度的最小的2的幂整数） elements = new Object[initialCapacity]; }以上两个构造方法实现中：
第一个构造方法，创建一个默认长度为8的数组；
第二个构造方法，如代码中注释举例，其会通过allocateElements(numElements)将数组的长度定义为2的倍数（找到大于需要长度的最小的2的幂整数）；