雙端隊列惠昔，在OkHttp#Dispatcher有用到
一 構(gòu)造
這個數(shù)據(jù)結(jié)構(gòu)有兩個構(gòu)造，默認(rèn)的容積(capacity)為8胃榕，而通過構(gòu)造參數(shù)傳入的并不是簡單的按照傳入值來確定容積(capacity)
最后的容積總是為2 的 n次方，8 <capacity < 2^31 ，這樣做的好處可以方便elements - 1用作&運算符加快運算
二 添加元素
舉例一個容積為8的ArrayDeque换淆，添加元素時的位置
-
addFirst()8 > 7 > 6 > 5 > 4 > ...
-
addLast()0 > 1 > 2 > 3 > 4 > ...
同時躁愿，如果頭(head)尾(tail)相等時营搅，
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;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
會創(chuàng)建一個雙倍的數(shù)組，然后使用System.arraycopy 兩次將舊的數(shù)組中的元素復(fù)制到新數(shù)組中备埃，第一次拷貝右邊的(head - elements.length],第二次拷貝左邊的(0 - head],然后將head置為0,tail置為原數(shù)組的長度
addFirst(e)中的elements[head = (head - 1) & (elements.length - 1)] = e; 的作用
int a = -1;
int mod = 16;
if (a == -1){
System.out.println("a == -1 ---------------");
System.out.println(a & (mod - 1));
System.out.println(mod - 1);
}
a = 14;
if (-1 < a && a < mod){
System.out.println("-1 < a && a < mod ---------------");
System.out.println(a & (mod - 1));
System.out.println(a);
}
a = 16;
if (a == mod){
System.out.println("a == mod ---------------");
System.out.println(a & (mod - 1));
System.out.println(0);
}
輸出
a == -1 ---------------
15
15
-1 < a && a < mod ---------------
14
14
a == mod ---------------
0
0
也就是說辅搬，如果 head = 0 的時候，那么在存放新元素(指addFirst)的索引為elements.length -1 ,而其他時候存放新元素的索引為head - 1,
如果 head = elements.length - 1 的時猿妈，進(jìn)行取值操作于游， 取值后 head 會成為0
