ArrayDeque
数组循环队列，这个数据结构设计的挺有意思的。
据说此类很可能在用作堆栈时快于 Stack，在用作队列时快于 LinkedList。
一、容量
1.1默认容量是8=2^3
1.2指定初始化容容量
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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
}
elements = new Object[initialCapacity];
}
此方法是给数组分配初始容量，初始容量并不是numElements，而是大于指定长度的最小的2的幂正数
所以ArrayDeque的容量一定是2的幂整数
计算的方法是用或运算
1.3或运算的特点：
得到的结果大于等于任意一个操作数
结果有趋向每个位都为1的趋势
所以这样运算下来，运算得到的结果的二进制一定是每个位都是1,再加一个，就刚好是2的整数幂了
1.4扩展容量
当头尾指针相遇，则数组存满了
此时要扩展容量，会调用
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;//bit count faster
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//copy the right of head(include head)
System.arraycopy(elements, 0, a, r, p);//copy the left of the tail(exclude tail)
elements = a;
head = 0;
tail = n;
}
1.5细说doubleCapacity
注意看：
1.求两本容量，n<<1，使用位运算要快于四则运算，因为这更贴近运算器电路的设计
2.复制原来的数组到目标数组要注意顺序！
可以看到，复制分两次复制进行，第一次复制head指针右边的元素（包括head指针指向的那个），第二次复制left指针左边的元素（不包括tail指针指向的那个）
扩展为原来两本的容量，结果还是2的幂整数
为什么容量一定要是2的幂整数呢？待会说
二、头尾指针
一开始，头尾指针都在下标为0的地方，如果向队头插入数据，头指针向左移，向队尾插入数据，尾指针向右移
tail指针所在的位置，不存储数据，代表下一次addLast存储的地方
三、add
队列提供增加到队首和队尾的两种方法，注意看怎么处理指针临界状态和指针循环
3.1addLast
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
移动tail指针，用了与运算
与运算的特点：
结果一定小于等于任意一个操作符的值
与正数进行与运算结果一定为证
当tail+1了之后，超过数组长度，用与运算可以起到循环指针的效果，相当于(tail+1%elements.length)
因为elements.length一定是2的整数幂，当-1了之后每一位一定是1，当tile+1超过数组长度的时候，刚好是2的整数幂，则是10***00这种形式，所以与运算了之后，一定等于0
3.2addFirst
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
当head-1<0的时候，用与运算可以得到绝对值，并且循环指针
因为当head超过数组，head-1刚好是-1，则二进制每个都是1，与运算了之后，一定是111***111的正数，刚好是数组的最后一个位置
四、指针相遇
当tail == head的时候，首尾指针重合，此时队列已满，需要扩展队列，调用doubleCapacity
五、利用空间局部性
在方法中需要多次调用的全局变量，最好创建一个局部变量来访问
因为全局变量是在静态存储区中的，局部变量是放在栈中的，和方法的指令中同一个区域，所以访问会更快，提高程序性能
就像下面这样
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
创建了一个mask，来存放elements.length-1
6.优化删除策略
private boolean delete(int i) {
checkInvariants();
final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
final int front = (i - h) & mask;
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
//最优化删除策略
if (front < back) {//如果要删除的元素在前半段
if (h <= i) {//如果head在要删除元素的前面
System.arraycopy(elements, h, elements, h + 1, front);//将要删除元素的前继元素往后移动一格
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);//把i前面的元素往后挪一格
elements[0] = elements[mask];
System.arraycopy(elements, h, elements, h + 1, mask - h);//head-数组末端(不包括数组末端) 都往后移一格
}
elements[h] = null;//帮助垃圾收集
head = (h + 1) & mask;//头指针回退一格
return false;
} else {
if (i < t) { // Copy the null tail as well
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
}
这段源码我觉得很值得一看，他用了最优删除策略，都适用与数组实现的数据结构
当删除的时候，先计算删除点是在队列的上半段还是下半段
如果是上半段，则上半段移动一格
这样子可以达到最少的元素移动！
对于这种循环队列，需要注意删除元素的位置，有两种特殊位置
6.1第一种特殊位置
此时删除节点在队列的上半段，但是上半段是断开的
这个时候要移动上半段的话，要分两次移动
第一次移动删除元素前面的，第二次移动头指针到数组末端
6.2第二种特殊位置
查看原文：http://blog.zswlib.com/2016/10/27/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90arraydeque/