波波老师，循环队列这里浪费的那一个空间我有点疑问。

Question

波波老师，请问循环队列这里，您说的有目的性的浪费一个空间是 为了方便表示队列为空和队列为满吧？可是队列是否为空也可以用size==0判断，是否为满也可以用size==data.length判断吧？可能是因为我知识还不够深入，老师可以给我讲一讲 浪费的那一个空间的价值 体现在那里吗？

Answer 1

liuyubobobo 2018-07-25 02:40:29

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

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

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

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

再次赞一下你的问题！

• 提问者 慕虎3444883 #1

  非常感谢！

• 提问者 慕虎3444883 #2

  波波老师，循环队列的经典实现里浪费一个空间来区分队列空和满。如果是基于链表实现的队列，那就是浪费一个Node对象的空间，对象里还包含了成员变量，指向null的句柄我不知道占不占空间，但起码还有个指向next的节点引用；如果是基于动态数组，那就是浪费连续的一个内存空间，而且多了这个空间也有可能出现数组的capacity本该停留在扩容边缘的大小，却因为多了这一个空间而出现扩容造成空间和时间的开销，也有可能出现数组的capacity本该缩容，却因为多了这一个空间而不缩容造成空间上的浪费； 
  我的问题是：如果在队列里维护一个size变量，那这个变量也可以解决空和满的问题；而且这个变量作为成员变量，怎么看似乎也没有经典实现里的 浪费的那一个空间 的条件苛刻，甚至好像更节约空间....
  这是我昨天晚上睡前，看到这个一两年前提的问题突然想到的，不知道是我比那个时候考虑的更多了？还是说比那时候更生疏所以考虑的有问题了。。如果真的没有问题，那我想上边分析的这样去对比空间的开销有没有哪里不太恰当呢？因为我多多少少还是有点感觉上的东西。请bobo老师指教啦^_^！

• 提问者 慕虎3444883 #3

  -------------

点开查看后面3条评论

Answer 2

提问者 慕虎3444883 2018-07-24 21:12:24

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

• liuyubobobo #1

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