杭州网站优化平台,网站开发调试工具,如何在第三方网站做推广,网站点播视频如何做用java以数组为底层结构创建循环队列
循环队列相对于普通队列最大的变化就是添加了一个头指针head#xff0c;尾指针tail。原先的普通数组队列当入队列再出队列之后#xff0c;前面就会空出位置#xff0c;如果要再添加元素的话只能往尾部添加#xff0c;当添加到容积大小…用java以数组为底层结构创建循环队列
循环队列相对于普通队列最大的变化就是添加了一个头指针head尾指针tail。原先的普通数组队列当入队列再出队列之后前面就会空出位置如果要再添加元素的话只能往尾部添加当添加到容积大小的索引时就会自动扩容往后添加但永远都不能在前面出队的空出的位置添加前面的位置就浪费了。循环队列很有效的解决了这一问题通过两个指针对capacity容积取余来改变指针指向位置从而杜绝上述问题。
尾指针是入队位置的索引每入队一个元素后tail。头指针是出队元素的索引每出队一个元素后head。但是怎么才能循环呢当尾指针等于capacity时说明需要改变尾指针到开头位置来插入元素了tail(tail1)%capacity。如果用这样的方法那队满条件也得改变(tail1)%capacityhead。
代码如下
looparr底层结构循环数组
public class LoopArrT {private T[] value; //保存数据int size; //实际存放个数int capacity; //容积private int head;private int tail;// 构造方法public LoopArr(int capacity){//因为队满时要空出来一个位置所以容积需要相较于之前的普通数组加1if(capacity0){this.capacity11;}else {this.capacitycapacity1;}this.size0;this.headthis.tail0;this.value(T[])(new Object[this.capacity]);//不可以直接new一个T[]类型所以需要先new一个Object[]类型然后转为T[]}//判断数组是否为空public boolean IsEmpty(){if(this.headthis.tail){return true;}else{return false;}}//向数组中添加元素public void add(T data){//扩容if((this.tail1)%this.capacitythis.head){ //如果数组满了就重新设置容积resize((this.capacity-1)*21); //先把容积变为原先的容积再×2加1是循环队列队满时有一个空}this.value[this.tail]data;//因为是循环的当队尾指到最后了就需要重新回到第一个位置继续加this.tail(this.tail1)%this.capacity;this.size;}//移除队首元素public T remove(){//缩容if(this.sizethis.capacity/4this.capacity/20){resize((this.capacity-1)/21); //与扩容同理}if(IsEmpty()){return null;}else{T ethis.value[head];this.value[head]null;//head指向末尾时需要重新循环到开头所以如下this.head(this.head1)%this.capacity;this.size--;return e;}}//重新给容积private void resize(int newcapacity){//由于数组的容积都是不变的所以需要新建一个数组T [] newvalue(T[])(new Object[newcapacity]);//转移数组for (int i 0; i this.size; i) {newvalue[i]this.value[(this.headi)%this.capacity]; //给新数组赋值此时capacity还没有变所以%this.capacity}//改变容器数组this.valuenewvalue;this.capacitynewcapacity;this.head0; //从头开始this.tailthis.size; //尾指针指向最后一个元素的下一个位置也就是size}public int getHead() {return head;}public int getTail() {return tail;}//获取索引位置的值public T getindexdata(int index){if(index0||indexthis.capacity){throw new IllegalArgumentException(index is invalid.);}return this.value[index];}//获取实际长度public int getSize() {return this.size;}//获取数组的容积public int getCapacity() {return this.capacity;}
}队列接口用于被循环队列实现功能
public interface selfqueueT {//入队void offer(T e);//出队T poll();//查看队首元素T peak();//队列中元素的个数int getsize();//队列是否为空boolean IsEmpty();
}LoopQueue
public class LoopQueueT implements selfqueueT {private LoopArrT data;public LoopQueue(){this.datanew LoopArrT(10);}//入队public void offer(T e) {this.data.add(e);}//出队public T poll() {return this.data.remove();}//获得队首元素public T peak() {return this.data.getindexdata(this.data.getHead());}//获取长度public int getsize() {return this.data.getSize();}//获取容积public int getcapacity(){return this.data.getCapacity();}//判断是否为空public boolean IsEmpty() {return this.data.IsEmpty();}
}测试
public class queuetestT {public void test(LoopQueue queue, ListT list){//开始时间long startTimeSystem.nanoTime();//入队System.out.println(队尾先进入队顺序);for (int i 0; i list.size(); i) {queue.offer(list.get(i));System.out.print(list.get(i) );}System.out.println(size:queue.getsize());System.out.println(capacity:queue.getcapacity());System.out.println(队列中元素个数queue.getsize());System.out.println(队头元素queue.peak());//出队System.out.println(队头先出出队顺序);while(!queue.IsEmpty()){T e (T) queue.poll();System.out.print(e );}//结束时间long endTimeSystem.nanoTime();System.out.println(总耗时(endTime-startTime)/1000000000.0s);}public static void main(String[] args) {queuetestInteger qtnew queuetestInteger();selfqueueInteger queuenew LoopQueueInteger(); //继承了selfqueue的LoopQueue来实现selfqueueListInteger listnew ArrayListInteger();Random rnew Random();for (int i 0; i 30; i) {list.add(r.nextInt(100));}qt.test((LoopQueue) queue,list);}
}
