arrays - 不浪费条目或使用计数器的循环队列

Question

是否可以使用 array 来实现循环队列？ ，没有计数器来计算队列中的项目数或不浪费数组的任何条目？

我猜的:

这是不可能的，假设我们有两个指针 front和 rear ，第一个指向队列的第一个元素，

我们可以通过两种方式定义后指针:

1.它指向插入队列的最后一个元素，因此下一个条目是下一个将要插入的元素的可能位置

2.指向下一个元素要插入的地方

在任何一种情况下，如果我们不浪费数组的至少一个条目，或者如果我们不保持计数器计数 the number of inserted - number of deleted elements，我们就无法区分满队列和空队列。

Answer 1

您的担忧通常被认为是 full vs. empty difficulty的循环队列。引用:

To solve this confusion there are a number of solutions:

1. Always keep one slot open.
2. Use a fill count to distinguish the two cases.
3. Use an extra mirroring bit to distinguish the two cases.
4. Use read and write counts to get the fill count from.
5. Use absolute indices.
6. Record last operation.

您在问题中直接提到的数字 1、2 和 4。除了数组和开始/结束(或您命名的前/后)索引/指针之外，它们确实消耗了一定数量的内存。其他解决方案也消耗内存。

#3 - 使用镜像位

只添加一个额外的 bool 值或枚举，本质上是 isEmpty或 isFull .这种方法的思想、逻辑和证明是 more complicated .

#5 - 绝对指数

执行操作时索引会增加，并且永远不会减少。它们本质上是执行的每种类型操作数量的计数器。这有 other drawbacks .

#6 - 记录上次操作

本质上与#3 相同，但语义不同。

无论如何，所有这些链接都指向维基百科文章。我强烈推荐它。可能还有其他方法，但很难改进您文章中概述的 6 种方法之一。它们都有缺点和优点，因此在确定实现之前仔细考虑预期的用例。