data-structures - 循环队列的缺点？

Question

最近，在一次采访中，有人问我使用循环队列的缺点。我什么都想不出来。在互联网上搜索我发现的唯一答案是它比线性队列难以实现:)。有没有其他的缺点？

Answer 1

我想说循环队列的最大缺点是您只能存储 queue.length 元素。如果您将其用作缓冲区，则会限制您的历史深度。

另一个较小的缺点是很难在不保留额外信息的情况下区分空队列和满队列。

Answer 2

面试官正在寻找的答案可能取决于上述问题中没有的其他上下文。

例如，对于高度并发的生产者/消费者系统，通常会考虑循环队列。当队列已满时，队列前面和后面的操作可能会争用相同的缓存行，这在这样的上下文中可能是个问题。

或者面试官想让你谈谈与基于循环数组的队列相比，在垃圾收集语言中创建无锁链接队列要容易得多。

或者，如果您使用具有周期性移位的线性队列而不是循环队列，那么您可以如何更好地利用您的语言提供的向量容器。

Answer 3

在我看来，任何遍历队列的代码都必须跟踪第一个节点才能检测到遍历的结束。但是在多线程环境中，另一个线程可能会删除第一个节点，这会导致遍历线程进入无限循环。因此，遍历线程必须在其通过队列的循环期间保持第一个节点锁定。