一、类签名
ArrayDeque是实现 Deque 接口且容量可变的双端队列数组。数组实现的双端队列没有容量限制，需要更多空间时再进行扩容。此类线程不安全，如果没有外部同步约束，就不支持多线程并发。值得注意的是，本双端队列不接受空对象，作为栈使用时比 Stack 快，作为队列使用时比 LinkedList 快。
大多数 ArrayDeque 方法执行消耗常量时间，除了 remove(Object) 、 removeFirstOccurrence ， removeLastOccurrence 、 contains 、 iterator 和批量操作是线性时间消耗的。
publicclassArrayDeque<E>extendsAbstractCollection<E>implementsDeque,Cloneable,Serializable
其次，虚拟机擅长基于有效切片中索引的递增、递减操作，对简单数组循环进行优化。例如：
for(inti= start;i
源码来自 JDK11
二、数据成员
保存双端数组队列变量。当数组的 cells 没有持有双端队列元素时为空。数组存在至少一个空位，作为队列的尾部
transientObject[] elements;
头元素在数组中的索引值，下标值对应元素由remove()或pop()方法移除。若队列没有元素，head为 [0, elements.length) 间任意值，与尾引用值相同
transientinthead;
下一个元素存入数组尾部的索引值，所以 elements[tail] 一直为空
transientinttail;
三、常量
可申请数组的最大容量值。有些虚拟机实现会在数组中保留 header words 。所以尝试分配更大数组空间会导致 OutOfMemoryError 。使用此值避免了这种问题。
privatestaticfinalintMAX_ARRAY_SIZE = Integer.MAX_VALUE -8;
四、扩容方法
增加至少 needed 个数组空间，值必须为正数。方法计算新容量值时，已经完成整形值向上溢出的处理
privatevoidgrow(intneeded){// 获取原数组容量值finalintoldCapacity = elements.length;// 可 newCapacity = oldCapacity + jump // 或 newCapacity = oldCapacity + needed// 或 newCapacity = MAX_ARRAY_SIZE// 或 newCapacity = Integer.MAX_VALUEintnewCapacity;// 若原容量值小于64，则jump为原值加2，否则jump为原值一半intjump = (oldCapacity <64) ? (oldCapacity +2) : (oldCapacity >>1);// 计算jump是否比理想扩容值needed小if(jump < needed || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE >0) newCapacity = newCapacity(needed, jump);// 根据newCapacity创建新数组，并把原数组元素拷贝到新数组finalObject[] es = elements = Arrays.copyOf(elements, newCapacity);// Exceptionally, here tail == head needs to be disambiguatedif(tail < head || (tail == head && es[head] !=null)) {// wrap around; slide first leg forward to end of arrayintnewSpace = newCapacity - oldCapacity; System.arraycopy(es, head, es, head + newSpace, oldCapacity - head);for(inti = head, to = (head += newSpace); i < to; i++) es[i] =null; }}// 为边缘条件进行容量计算，尤其是向上移除的情况privateintnewCapacity(intneeded,intjump){finalintoldCapacity = elements.length, minCapacity;if((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE >0) {// 最大容量值溢出if(minCapacity <0)thrownewIllegalStateException("Sorry, deque too big");// 设置为最大值returnInteger.MAX_VALUE; }if(needed > jump)returnminCapacity;// needed <= jumpreturn(oldCapacity + jump - MAX_ARRAY_SIZE <0) ? oldCapacity + jump : MAX_ARRAY_SIZE;}
进群：697699179可以获取Java各类入门学习资料！
这是我的微信公众号【编程study】各位大佬有空可以关注下，每天更新Java学习方法，感谢！
学习中遇到问题有不明白的地方，推荐加小编Java学习群：697699179内有视频教程 ，直播课程 ，等学习资料，期待你的加入
五、构造方法
构造默认队列，初始容量为16
publicArrayDeque(){ elements =newObject[16];}
通过指定容量值构造双端数组队列
publicArrayDeque(intnumElements) {// 若numElements大于1小于MAX_VALUE，大小为numElements+1elements =newObject[(numElements <1) ? 1 : (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : numElements +1];}
通过指定集合构造双端数组队列，初始队列大小为执行集合元素数量值
publicArrayDeque(Collectionc) { this(c.size()); copyElements(c);}
六、静态方法
// 循环递增i，实现对i取模的能力。先决条件和事后条件为：0 <= i < modulusstaticfinalintinc(inti,intmodulus){if(++i >= modulus) i =0;returni;}// 循环递减i，实现对i取模的能力。先决条件和事后条件为：0 <= i < modulusstaticfinalintdec(inti,intmodulus){if(--i <0) i = modulus -1;returni;}// 循环增加指定距离值到i，实现对i取模的能力// 先决条件: 0 <= i < modulus, 0 <= distance <= modulus// 返回值：index 0 <= i < modulusstaticfinalintinc(inti,intdistance,intmodulus){if((i += distance) - modulus >=0) i -= modulus;returni;}// 从i减去j，并对i取模的能力// 索引i必须在逻辑上在索引j之前// 先决条件: 0 <= i < modulus, 0 <= j < modulus； // 返回值：j到i之间的环形距离；staticfinalintsub(inti,intj,intmodulus){if((i -= j) <0) i += modulus;returni;}// 返回数组中索引值为i的元素@SuppressWarnings("unchecked")staticfinalEelementAt(Object[] es,inti){return(E) es[i];}
七、成员方法
元素主要的插入、获取方法是 addFirst 、 addLast 、 pollFirst 、 pollLast ，其他方法都在此基础上实现
7.1 add
把执行元素插入到队列头部，若元素为空抛出NullPointerException
publicvoidaddFirst(E e){if(e ==null)thrownewNullPointerException();finalObject[] es = elements; es[head = dec(head, es.length)] = e;if(head == tail) grow(1);}
把执行元素插入到队列尾部，若元素为空抛出NullPointerException
publicvoidaddLast(E e){if(e ==null)thrownewNullPointerException();finalObject[] es = elements; es[tail] = e;if(head == (tail = inc(tail, es.length))) grow(1);}
把指定集合的所有元素添加到队列的尾部
publicbooleanaddAll(Collection c) {finalints, needed;if((needed = (s =size()) + c.size() +1- elements.length) >0) grow(needed); copyElements(c);returnsize() > s;}
7.2 copyElements
把集合C的元素添加到本队列尾部
privatevoidcopyElements(Collection<? extends E> c){ c.forEach(this::addLast);}
7.3 offer
把指定元素插入到队列头部
publicbooleanofferFirst(E e){ addFirst(e);returntrue;}
把指定元素插入到队列头部
publicbooleanofferLast(E e){ addLast(e);returntrue;}
7.4 remove
若找不到头元素就抛出NoSuchElementException
publicEremoveFirst(){ E e = pollFirst();if(e ==null)thrownewNoSuchElementException();returne;}
若找不到最后一个元素就抛出NoSuchElementException
publicEremoveLast(){ E e = pollLast();if(e ==null)thrownewNoSuchElementException();returne;}
7.5 poll
publicEpollFirst(){finalObject[] es;finalinth; E e = elementAt(es = elements, h = head);if(e !=null) { es[h] =null; head = inc(h, es.length); }returne;}publicEpollLast(){finalObject[] es;finalintt; E e = elementAt(es = elements, t = dec(tail, es.length));if(e !=null) es[tail = t] =null;returne;}
7.6 get
找不到元素抛出NoSuchElementException
publicEgetFirst(){// 通过head索引值获取元素E e = elementAt(elements, head);if(e ==null)thrownewNoSuchElementException();returne;}
找不到元素抛出NoSuchElementException
publicEgetLast(){finalObject[] es = elements; E e = elementAt(es, dec(tail, es.length));if(e ==null)thrownewNoSuchElementException();returne;}
7.7 peek
publicE peekFirst() {returnelementAt(elements, head);}publicE peekLast() {finalObject[] es;returnelementAt(es = elements, dec(tail, es.length));}
7.8 firstOccurrence
移出第一个命中的指定元素。如果队列存在多个相同元素，每次调用方法仅移除一个。每次查找均从的头部开始，逐个遍历元素寻找匹配项。元素名并移除成功返回 true ，元素为null或不包含该元素返回 false 。
publicboolean removeFirstOccurrence(Object o) {if(o !=null) { final Object[] es = elements;for(int i = head,end= tail,to= (i <=end) ?end: es.length; ; i =0,to=end) {for(; i
移出最后一个命中的指定元素。如果队列存在多个相同元素，每次调用方法仅移除一个。元素名并移除成功返回 true ，元素为null或不包含该元素返回 false 。
publicboolean removeLastOccurrence(Object o) {if(o !=null) { final Object[] es = elements;for(int i = tail,end= head,to= (i >=end) ?end:0; ; i = es.length,to=end) {for(i--; i >to-1; i--)if(o.equals(es[i])) { delete(i);returntrue; }if(to==end) break; } }returnfalse;}
7.9 队列方法
// 把指定元素插入到队列尾部publicbooleanadd(E e){ addLast(e);returntrue;}// 把指定元素插入到队列尾部publicbooleanoffer(E e){returnofferLast(e);}// 获取并移除队列头元素，若队列没有元素则抛出NoSuchElementExceptionpublicEremove(){returnremoveFirst();}// 获取并移除队列头元素，如果元素不存在返回nullpublicEpoll(){returnpollFirst();}// 仅获取元素队列头元素，但不从队列中不会移除。如果队列为空，则此方法会抛出异常publicEelement(){returngetFirst();}// 仅获取元素队列头元素，但不从队列中不会移除。如果队列为空，则此方法返回nullpublicEpeek(){returnpeekFirst();}
7.10 栈方法
// 向栈中压入元素，即向本队列头部插入元素。若指定元素为空抛出NullPointerExceptionpublicvoidpush(E e){ addFirst(e);}// 从栈中弹出元素，即从本队列头部移除并返回元素。若队列为空抛出NoSuchElementExceptionpublicEpop(){returnremoveFirst();}// 从元素数组中移除指定索引的元素。booleandelete(inti){finalObject[] es = elements;finalintcapacity = es.length;finalinth, t;// number of elements before to-be-deleted eltfinalintfront = sub(i, h = head, capacity);// number of elements after to-be-deleted eltfinalintback = sub(t = tail, i, capacity) -1;if(front < back) {// move front elements forwardsif(h <= i) { System.arraycopy(es, h, es, h +1, front); }else{// Wrap aroundSystem.arraycopy(es,0, es,1, i); es[0] = es[capacity -1]; System.arraycopy(es, h, es, h +1, front - (i +1)); } es[h] =null; head = inc(h, capacity);returnfalse; }else{// move back elements backwardstail = dec(t, capacity);if(i <= tail) { System.arraycopy(es, i +1, es, i, back); }else{// Wrap aroundSystem.arraycopy(es, i +1, es, i, capacity - (i +1)); es[capacity -1] = es[0]; System.arraycopy(es,1, es,0, t -1); } es[tail] =null;returntrue; }}
7.11 集合方法
返回双端队列包含元素的数量
publicintsize() {returnsub(tail, head, elements.length);}
若双端队列不含任何元素返回true。在头引用和尾引用指向同一个对象的时候能表示双端队列为空。
publicbooleanisEmpty(){returnhead == tail;}
7.12 位操作
privatestaticlong[] nBits(intn) {returnnewlong[((n -1) >>6) +1];}privatestaticvoidsetBit(long[] bits,inti){ bits[i >>6] |=1L<< i;}privatestaticbooleanisClear(long[] bits,inti){return(bits[i >>6] & (1L<< i)) ==0;}
7.13 contains
如果队列包含指定元素返回true。一般来说，队列可能存在多个相同的元素。所以本方法返回true表示队列至少存在一个元素与指定元素相等
publicboolean contains(Object o) {if(o !=null) { final Object[] es = elements;for(int i = head,end= tail,to= (i <=end) ?end: es.length; ; i =0,to=end) {for(; i
7.14 remove
从队列中移除指定单个元素。如果队列不含该元素，则队列不会改变。一般来说，队列可能会含有多和相同的元素，每次仅移除其中一个。
publicbooleanremove(Object o){returnremoveFirstOccurrence(o);}
7.14 clear
从移除队列中所有元素
publicvoidclear(){ circularClear(elements, head, tail); head = tail =0;}
调用以下方法
// Nulls out slots starting at array index i, upto index end.// Condition i == end means "empty" - nothing to do.privatestaticvoidcircularClear(Object[] es, int i, intend) {// assert 0 <= i && i < es.length;// assert 0 <= end && end < es.length;for(intto= (i <=end) ?end: es.length; ; i =0,to=end) {for(; i
7.15 toArray
返回包含双端队列所有元素的数组，元素顺序和双端队列元素顺序一致。
publicObject[] toArray() {returntoArray(Object[].class);}private T[] toArray(Class klazz) {// 获取元素数组finalObject[] es = elements;finalT[] a;// 分别获取头引用和未引用finalint head =this.head, tail =this.tail, end;if((end = tail + ((head <= tail) ?0: es.length)) >=0) {// Uses null extension feature of copyOfRangea = Arrays.copyOfRange(es, head, end, klazz); }else{// 整形上溢a = Arrays.copyOfRange(es,0, end - head, klazz); System.arraycopy(es, head, a,0, es.length - head); }if(end != tail) System.arraycopy(es,0, a, es.length - head, tail);returna;}
传入目标数组，并把双端队列所有元素放入该数组，元素顺序和双端队列元素顺序一致。返回数组的类型和传入数组类型相同。如果传入数组大小不足容纳所有元素，方法会创建新数组，且新容量和所放入元素数量一致，然后放入所有元素并返回。所以，会出现传入数组和返回数组不是同一个对象的现象。
如果传入数组空间足够存入所有元素，该数组的下一个空间会被置为 null 。
本方法可以实现队列转数组的功能： String[] y = x.toArray(new String[0]); 。且值得注意的是，传入 toArray(new Object[0]) 和 传入 toArray() 的效果完全相同。
数组元素的运行时类型不匹配双端队列元素的运行时类型时，抛出 ArrayStoreException ； 数组为空抛出 NullPointerException ；
@SuppressWarnings("unchecked")public T[] toArray(T[] a) {finalintsize;if((size=size()) > a.length)returntoArray((Class) a.getClass());finalObject[] es = elements;for(inti = head, j =0, len = Math.min(size, es.length - i); ; i =0, len = tail) { System.arraycopy(es, i, a, j, len);if((j += len) ==size)break; }if(size< a.length) a[size] =null;returna;}
