有没有队列比循环队列更好的用例？

Question

循环队列显然更好，因为它帮助我们利用通过弹出元素而留下的空白空间。它还节省了可能用于在每次弹出后对元素进行横向移动的时间。

但是，有没有使用队列比使用循环队列更好的用例呢？

Queue =的定义我们将采用线性数组实现。遵循FIFO，无覆盖

循环队列的定义=环形缓冲区实现。遵循FIFO。无覆盖。

Answer 1

注意:在许多语言中，queue只是一个接口，并没有说明任何关于实现的内容。

当使用基于数组的循环队列，也就是环形缓冲区时，您必须处理推入满缓冲区的情况。您可以：

在有足够的空间和内存之前，

1. 忽略最旧的条目
3. ，并复制所有的内容
4. 使用超大的缓冲区，因此这种情况永远不会发生

这些选项都有缺点。如果你可以忍受它们，或者你知道你永远不会填满缓冲区，那么ring buffer就是可行的选择。

选项3和4会导致口吃。根据您的用例，您可能更喜欢更长但稳定的访问时间和可靠性，而不是偶尔的峰值，因此选择linked list或其他类型的动态实现，如deque。

示例用例是任务，其中您必须实现稳定的帧/采样率或吞吐量，并且不能容忍卡顿，例如：

当您不希望线程在推送新作业时阻塞太长时间时，可以使用

• 实时视频和音频processing
• Realtime rendering
• Networking
• Thread池。

然而，基于线性数组的队列将遭受相同的缺点。我看不出有什么理由选择线性队列而不是环形队列。

(除了实现复杂度稍高之外。)

C++中的std::queue默认使用deque作为底层容器。deque本质上是一个动态的数组数组，对于大多数用例来说，它似乎是一个很好的基础，因为它以小块的形式分配内存，从而减少了卡顿。