利用dequeue来实现resize这个思路怎么样?

利用dequeue来实现resize这个思路怎么样?

resize()部分代码:

private void resize(int newCapacity){
E[] resizedData=(E[])new Object[newCapacity+1];
for(int i=0;i<getCapacity();i++){
if(front!=tail) {
resizedData[i] =dequeue();
}else{
front=0;
tail=i;
data=resizedData;
break;
}
}
}

LoopQueue部分全部代码:

public class LoopQueue<E> implements Queue<E>{
private E[] data;
private int front,tail,size;

public LoopQueue(int capacity){
data=(E[])new Object[capacity+1];
front=0;
tail=0;
size=0;
}

public LoopQueue(){
this(10);
}

public int getCapacity(){
return data.length-1;
}

private void resize(int newCapacity){
E[] resizedData=(E[])new Object[newCapacity+1];
for(int i=0;i<getCapacity();i++){
if(front!=tail) {
resizedData[i] =dequeue();
}else{
front=0;
tail=i;
data=resizedData;
break;
}
}
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return front==tail;
}

@Override
public void enqueue(E e) {
if((tail+1)%data.length==front) {
resize(getCapacity() * 2);
}
data[(tail)%data.length] = e;
tail = (tail + 1) % data.length;
size++;
}

@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("Queue is empty!");
}
E ret=data[front];
data[front]=null;
front=(front+1)%data.length;
size--;
// if(size<getCapacity()/4 && getCapacity()/2>1){
// resize(getCapacity()/2);
// }
return ret;
}

@Override
public E getFront() {
return data[front];
}

@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append(String.format("Queue: size=%d, Capacity=%d\n",size,getCapacity()));
res.append("front [");
for(int i=0;i<size; i++){
res.append(data[(i+front)%data.length]);
if(i!=size-1){
res.append(", ");
}
}
// for(int i=front;i!=tail;i=(i+1)%data.length){
// res.append(data[i]);
// if((i+1)%data.length!=tail){
// res.append(", ");
// }
// }
res.append("] tail");
return res.toString();
}
}


考虑到dequeue正好可以按顺序返回队列中的值,就想着用dequeue来实现resize,不过在完成之后发现没有考虑到dequeue中也需要存在resize缩小的操作,后期在dequeue中加入resize会出现一些错误,这样的错误似乎有些难分析

正在回答

登陆购买课程后可参与讨论,去登陆

1回答

是的。resize 是在 Array 中的,而 Array 是 Queue 的基础,所以使用 Queue 中的方法反过来实现 Array 中的方法是不合适的。


继续加油!:)

问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2594    人
  • 解答问题       1091    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师