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

Question

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

但是是否存在队列比使用循环队列更受青睐的用例？

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

循环队列的定义=环形缓冲区实现。遵循先进先出。没有覆盖。

Answer 1

注意：在许多语言中，aqueue只是一个接口，并没有说明任何有关实现的信息。

当使用基于数组的循环队列（也称为环形缓冲区）时，您必须处理推送到已满缓冲区的情况。你可以：

1. 忽略插入
2. 覆盖最旧的条目
3. 阻塞直到再次有空间
4. （重新）分配内存并复制所有内容
5. 使用过大的缓冲区，这样这种情况就不会发生

这些选项都有缺点。如果您可以忍受它们，或者您知道您永远不会填充缓冲区，那么环形缓冲区就是您的最佳选择。

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

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

• 实时视频和音频处理
• 实时渲染
• 联网
• 当您不希望线程在推送新作业时阻塞太长时间时，可以使用线程池。

然而，基于线性数组的队列也会遇到同样的缺点。我看不出选择线性队列而不是循环队列的理由。
（除了实现复杂性稍高之外。）

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