2回答

liuyubobobo

2018-07-25

已采纳

大赞！你说的对，用size判断可以不浪费这个空间：）

我所讲的需要浪费一个空间，其实完全基于只使用front和tail这两个变量：）这是循环队列的一个经典实现。实际上，整个循环队列，只使用front和tail就够了，size可以通过front和tail推导出来。有兴趣可以试试看？

如果使用size做判断，front，tail和size都需要。因为还是需要使用front和tail来记录入队的位置或者出队的元素：）

不过对于现代计算机，这些对性能的影响近乎为0。所以你使用size判断非常非常没问题！我局限在过去自己学习的经典实现的框框里啦！

再次赞一下你的问题！

3

6

st2020

我刚想问同一个问题，看到有人问过了，浪费一个空间似乎不是必须的，如果要用 front == tail 来区别是满了还是空了，再加上一个 data[front] != null 是否也可以判断？不浪费一个空间的话代码似乎更容易了解。个人想法

2020-11-26

共6条回复

慕虎3444883

提问者

2018-07-24

刚才测试循环队列和数组队列的出队耗时，100万个整数，数组队列花了6分多钟，循环队列只花了零点零几秒，差距好大呀。我第一次测试的时候出了问题。当时采用了问题中所说的用size是否为零来定义isEmpty方法，结果抛出了循环队列为空的异常...该为老师讲的front==tail就成功了。。可size不就是表示队列中有的的元素个数嘛，怎么回事儿啊？

3

1

liuyubobobo

这就是O(n^2)和O(n)的差距，也是我们要学习算法和数据结构的意义：）对于你说的后面的问题，应该是基于size实现的有问题。理论上是可以的。自己仔细debug调试找一下为什么？加油！：）

2018-07-25

共1条回复