关于循环队列中浪费一个空间的说法
来源：3-7 循环队列的实现
全是甘货
2019-04-15
老师，首先很感谢你让我把取余"%"这个运算符和圆环运算联系了起来！
对于循环队列中提到需要浪费一个空间的说法，我感到非常困惑。
学生认为不需要浪费一个空间也可以，反而浪费一个空间让我倍感不适，老师越是这么讲我越是不适（）
遂回家修改了一下您的代码
07-Implementation-of-Loop-Queue 中的LoopQueue.java
链接描述
我把部分代码作出了修改
//我认为不需要浪费一个空间，也就是不需要为了可以被浪费一个空间，而多申请一个空间
public LoopQueue(int capacity){
// data = (E[])new Object[capacity + 1];
data = (E[])new Object[capacity];
front = 0;
tail = 0;
size = 0;
}
public int getCapacity(){
//return data.length - 1;
return data.length;
}
private void resize(int newCapacity){
//E[] newData = (E[])new Object[newCapacity + 1];
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];
data = newData;
front = 0;
tail = size;
}
从运行结果上我发现似乎没什么差别，而且我看我们的时钟（他是一个圆环），他也不需要做浪费一个空间的特殊处理。
所以还是很希望老师能解答一下我的困惑，是不是我理解错了，我的修改是否会在某一时刻出现问题，老师请指出，非常感谢。
2回答
-
sacomplexOne
2019-06-27
size不是必须的. 可用 (tail + capacity - front) % capacity 来代替.或者说使用size来判断队列的空或者满就不必空出一个位置了了
012019-06-27 -
liuyubobobo
2019-04-15
由于你的代码部分只有resize，所以我可能看不出问题。但是没关系，整体，对于你的疑问，可以参考这里：http://coding.imooc.com/learn/questiondetail/70227.html
简单来说，如果我们合理的使用size，我们确实可以不浪费那一个空间。在这个课程的补充代码，我实现了一个不浪费空间版本的循环队列。可以参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/03-Stacks-and-Queues/Optional-01-Loop-Queue-without-Wasting-One-Space/src/LoopQueue.java
但是，对于循环队列的逻辑，完全可以只使用front和tail，不使用size，就搭建出来。此时，就必须要浪费一个空间。关键问题不在resize，在于：如果不浪费这个空间，无法区分判空和判满两个操作：）我强烈建议你仔细体会一下，思考一下，如果没有size，只有front和tail，怎么判空，怎么判满，如果不浪费那个空间，会出什么问题？
我在课程的补充代码，也实现了一版只是用front和tail的循环队列。可以参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/03-Stacks-and-Queues/Optional-02-Loop-Queue-without-Size-Member/src/LoopQueue.java
继续加油！：）
022019-04-15
相似问题
回答 1
回答 1