循环队列没有浪费条目或使用计数器

Question

是否可以通过使用a来实现循环队列array,而不需要计数器来计算队列中的项目数或不浪费数组的任何条目？

我猜:

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

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

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

2.它指向要插入下一个元素的位置

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

Answer 1

您的担忧通常被认为是循环队列的完全与空难度.引用:

为了解决这种混乱,有许多解决方案:

1. 始终保持一个插槽打开.
2. 使用填充计数来区分这两种情况.
3. 使用额外的镜像位来区分这两种情况.
4. 使用读取和写入计数来获取填充计数.
5. 使用绝对指数.
6. 记录上次操作.

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

#3 - 使用镜像位

只添加一个额外的布尔值或枚举,基本上isEmpty或isFull.这种方法的想法,逻辑和证明更复杂.

#5 - 绝对指数

执行操作时指数会递增,而从不减少.它们本质上是所执行的每种类型的操作数量的计数器.这有其他缺点.

#6 - 记录最后一次操作

基本上与#3相同,但语义不同.

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

Answer 2

当我实现它时，我使用了一个名为“空”的附加布尔值。你是对的，在两个指针位于同一位置的情况下，人们无法区分。

根据您使用的指针，您可以使用一个指针的最低位来存储空变量。
如果 size 是一个可变整数，您还可以使用负值来指示队列没有元素。