循环队列的哪个实现最好？

Question

我正在学习循环队列。哪个实现循环队列最好，数组实现还是链表实现？

Answer 1

如果你在一个链表中做它，那么它实际上可以是循环的，因为最后一个节点将指向第一个节点。但我认为你需要澄清你的意思是“最好的”。

Answer 2

我想说，链接列表版本将是两个解决方案中更好的一个事实，即您不必一直调整您自己的内存以允许更多元素进入您的阵列。以及Skilldrick在链接列表中所说的内容，它实际上指向它所属的位置（最后一个节点指向第一个，从而使其循环）。

Answer 3

这取决于您需要在循环列表中执行哪些操作。例如，如果您需要随机访问（“给我列表的第237项”），那么数组实现将会快得多。

另一方面，有了一个工具，你可能需要有时调整列表，这将是缓慢的。您可以将其分摊以获得每插入O（1）摊销时间，但在实时系统上，偶尔缓慢的操作可能是不可接受的。

Answer 4

循环队列是实现数组的有界队列。

它比普通的队列更好，因为在这里我们可以有效地利用内存空间。如果我们有一个普通队列并从那里删除了一些元素，那么会在那里创建空的空间，即使队列中有空单元，我们也不能插入任何新的元素，因为只能从一侧（即后面或尾部）进行插入，并且必须从另一侧（即前面或头部）完成删除。但是在循环排队的情况下，前面和后面彼此相邻。