关于循环队列中浪费一个空间的说法

Question

老师，首先很感谢你让我把取余"%"这个运算符和圆环运算联系了起来！

对于循环队列中提到需要浪费一个空间的说法，我感到非常困惑。
学生认为不需要浪费一个空间也可以，反而浪费一个空间让我倍感不适，老师越是这么讲我越是不适（）
遂回家修改了一下您的代码
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;
}

从运行结果上我发现似乎没什么差别，而且我看我们的时钟（他是一个圆环），他也不需要做浪费一个空间的特殊处理。

所以还是很希望老师能解答一下我的困惑，是不是我理解错了，我的修改是否会在某一时刻出现问题，老师请指出，非常感谢。

Answer 1

sacomplexOne 2019-06-27 22:55:07

size不是必须的. 可用 (tail + capacity - front) % capacity 来代替.或者说使用size来判断队列的空或者满就不必空出一个位置了了

• sacomplexOne #1

  创建一个大小为10的循环队列,然后运行一下,按照老师main测试一下,你会发现会输出9个数,而不是10个

Answer 2

liuyubobobo 2019-04-15 14:38:16

由于你的代码部分只有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

继续加油！：）

• 提问者 全是甘货 #1

  不是老师，我把构造方法，resize方法，和getcapicity方法改了一下，我只是写了修改的代码，其他代码和你写的是一样的，请帮我再看看，谢谢老师

• liuyubobobo 回复 提问者 全是甘货 #2

  这个课程实现的代码，enqueue部分if((tail + 1) % data.length == front)决定了必须浪费一个空间，和resize没关系。你现在的代码，配合课程的enqueue，是错误的。因为enqueue保证了你的数组容量其实是数组长度减一。你现在反回实际数组长度，不是真正的队列容量。