educoder数据结构循环队列

下面是好好范文网小编收集整理的educoder数据结构循环队列，仅供参考，欢迎大家阅读！

循环队列

数组队列的出队操作的复杂度是O(n)，性能很差，解决方法就是使用循环队列（Loop Queue）

在循环队列中，需要对队为空和队为满的时候进行判断，为了区分队空和队满两个条件，需要浪费capacity一个空间，让rear指针一直指向一个空的位置；

当 rear= =front 时，队为空；

当 (rear+1)%n= =front (n为数字角标的最大值)时，队为满.

示意图如下：

循环队列实现

//循环队列publicclassArrayQueueLoop<E>implementsQueue<E>{private E data;privateint front;privateint rear;privateint size;//无参构造函数publicArrayQueueLoop        data=(EObject//因为有一个空的空间        front        rear        size//获取长度@OverridepublicintgetSizereturn size@OverridepublicbooleanisEmptyreturn size==0&&front==rear@Overridepublicvoidenqueue(E ereardata.length==front){resizedata.length        data[rear]=e;        rear=(reardata.length;        size@Overridepublic E dequeueisEmptyIllegalArgumentException        E ret=data[front];        front=(frontdata.length;        sizesize<=(data.length&&(data.lengthresize((data.lengthreturn ret;}//改变数组长度    privatevoidresize(int newLen){        E newData=(EObject[newLen p=front;int i            newData[i]=data[p];            i++;            p=(pdata.lengthp==rear        front        rear=size;        data=newData;}//获取队头元素@Overridepublic E getFrontisEmptyIllegalArgumentException("队列为空"return data[front//获取队尾元素@Overridepublic E getRearisEmptyIllegalArgumentException("队列为空"return data[(reardata.length)%data.length//清空队列@Overridepublic        data=(EObject//因为有一个空的空间        front        rear        size//自定义格式打印元素@Overridepublic String toString        StringBuilder sb=newStringBuilder        sb.append(String.format("ArrayQueueLoop: %d/%dn",size,data.length        sb.appendisEmpty            sb.append i=front;i!=rear;i=(idata.length){                sb.append(data[iidata.length==rear){                    sb.append                    sb.appendreturn sb.toString@Overridepublic Iterator<E>iteratorreturnnewArrayQueueLoopIteratorprivateclassArrayQueueLoopIteratorimplementsIterator{int p=front;@OverridepublicbooleanhasNextreturn p!=rear;}@Overridepublic Object             E ret=data[p];            p=(pdata.length;return ret