Java集合ArrayDeque类实例分析
Java集合ArrayDeque类实例分析
前言
ArrayDeque类是双端队列的实现类，类的继承结构如下面，继承自AbastractCollection（该类实习了部分集合通用的方法，其实现了Collection接口），其实现的接口Deque接口中定义了双端队列的主要的方法，比如从头删除，从尾部删除，获取头数据，获取尾部数据等等。
publicclassArrayDequeextendsAbstractCollection implementsDeque ,Cloneable,Serializable
ArrayDeque基本特征
就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。
1.无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）
2.非线程安全的，不支持并发访问和修改。
3.支持fast-fail.
4.作为栈使用的话比比栈要快.
5.当队列使用比linklist要快。
6.null元素被禁止使用。
ArrayDeque实现方法解读
最小初始化容量限制
/** *Theminimumcapacitythatwe'lluseforanewlycreateddeque. *Mustbeapowerof2. */ privatestaticfinalintMIN_INITIAL_CAPACITY=8;
这里根据注释中提及，必须是2的幂次。仅仅通过这里是不会知道为何要这样设定的。
publicvoidaddFirst(Ee){
if(e==null)
thrownewNullPointerException();
elements[head=(head-1)&(elements.length-1)]=e;
if(head==tail)
doubleCapacity();
}
addFirst方法中使用了head-1和length-1相与的形式来计算，那么，length-1这里是多少，因为规定了length必须是2的幂次，所以length-1后二进制低位将全部为1，然后与head-1相与相当于对其进行取模。
扩容
之所以说该ArrayDeque容量无限制，是因为只要检测到head==tail的时候，就直接调用doubleCapacity方法进行扩容。
这个时候将数组展开，head和tail指向的是同一个位置，那么，因为是循环数组，所以head左边可能存在一部分元素为p个，右边也可能存在一部分数据r=n-p个，右边的部分复制到从0到r,左边的部分复制到从r到结束。这样原来的数据从0开始往下排列。
privatevoiddoubleCapacity(){
asserthead==tail;
intp=head;
intn=elements.length;
intr=n-p;//numberofelementstotherightofp
intnewCapacity=n<<1;
if(newCapacity<0)
thrownewIllegalStateException("Sorry,dequetoobig");
Object[]a=newObject[newCapacity];
System.arraycopy(elements,p,a,0,r);
System.arraycopy(elements,0,a,r,p);
elements=(E[])a;
head=0;
tail=n;
}
删除元素
删除元素的基本思路为确定那一侧的数据少，少的一侧移动元素位置，这样效率相对于不比较更高些，然后，判断head是跨越最大值还是为跨越最大值，继而可以分两种不同的情况进行拷贝。但是该方法比较慢，因为存在数组的拷贝。
privatebooleandelete(inti){
checkInvariants();
finalE[]elements=this.elements;
finalintmask=elements.length-1;
finalinth=head;
finalintt=tail;
finalintfront=(i-h)&mask;
finalintback=(t-i)&mask;
//Invariant:head<=i=((t-h)&mask))
thrownewConcurrentModificationException();
//Optimizeforleastelementmotion
//为了最小的拷贝数据
if(front
获取并删除元素
这里在举个简单点的例子，中间判断是不是null，可以看出该队列不支持null,通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。
publicEpollFirst(){
inth=head;
Eresult=elements[h];//Elementisnullifdequeempty
if(result==null)
returnnull;
elements[h]=null;//Mustnulloutslot
head=(h+1)&(elements.length-1);
returnresult;
}
感谢阅读，希望能帮助大家，谢谢大家对本站的支持！