bobo老师,我有关于循环队列的问题,想请教下您
来源:3-8 数组队列和循环队列的比较
twodog二狗
2019-04-21
bobo老师,您好!我在慕课网上学习了您的课程《玩转数据结构》受益匪浅,真心地向您说声感谢!我正在学习您的课程《学习算法思想 修炼编程内功》,同时,也在复习《玩转数据结构》的课程。在复习到循环队列时,我产生了小小的问题,如果仅仅用front和tail来维护队列,不使用循环的机制,是否可以呢?:
public class MyQueue<E> implements Queue<E> {
private int front;
private int tail;
private E[]data;
public MyQueue(int capacity){
data = (E[])new Object[capacity+1];
}
public MyQueue(){
this(10);
}
@Override
public int getSize(){
return tail-front;
}
@Override
public boolean isEmpty(){
return front==tail;
}
@Override
public E getFront(){
return data[front];
}
private void resize(int newCapacity){
E[]newData = (E[])new Object[newCapacity+1];
for(int i=0;i<(tail-front);i++){
newData[i] = data[front+i];
}
data = newData;
tail = tail - front;
front = 0;
}
@Override
public void enqueue(E e){
if(tail == data.length-1)
resize((tail-front)*2);
data[tail] = e;
tail++;
}
@Override
public E dequeue(){
E ret = data[front];
// Loitering Object
data[front] = null;
front++;
if(((tail-front)==(data.length-1)/4) && (data.length-1)/2!=0)
resize((data.length-1)/2);
return ret;
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("MyQueue size=%d,capacity=%d\n",tail-front,data.length-1));
stringBuilder.append("front:[");
for(int i=front;i<tail;i++){
stringBuilder.append(data[i]);
if((i+1)!=tail){
stringBuilder.append(",");
}
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
}
对上述代码,我同ArrayQueue和LoopQueue一同做过测试,时间我觉得同LoopQueue差不多,但是我总是觉得自己的代码有一些问题,希望bobo老师能够指出我的问题,并且希望老师能够跟我说一下为什么要使用循环队列。
写回答
1回答
-
可以的。我在这个课程的补充代码中,提供了一个版本,不使用size,只是用front和tail,可以参考:)
为什么使用循环队列?因为循环队列的各个操作复杂度是O(1)啊!而我们在上一小节所实现的数组队列,不能做到这一点,出队操作是O(n),再回顾一下:)
继续加油!:)
032019-04-22
相似问题