6

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

我猜：

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

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

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

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

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

4

4 回答 4

5

您的担忧通常被认为是循环队列的完整与空的难度。报价：

为了解决这种混乱，有许多解决方案：

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

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

#3 - 使用镜像位

只添加一个额外的布尔值或枚举，本质上是isEmptyor isFull。这种方法的思想、逻辑和证明比较复杂。

#5 - 绝对指数

执行操作时，索引会递增，并且永远不会减少。它们本质上是执行每种类型的操作数量的计数器。这还有其他缺点。

#6 - 记录最后一次操作

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

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

于 2013-10-30T20:00:41.253 回答
2

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

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

于 2013-06-22T10:20:30.943 回答
1

一开始，让first=0，rear=-1；

我们通过以下方式添加它..... array[rear]; 后方=（后方+1）%MAX；

我们通过以下方式删除它.. array[front]; 前=（前+1）%MAX；

在从数组中删除一个元素时，我们可以在它之后添加一个条件，如下所示......
if(front==rear+1) first=0, rear=-1

那么空的条件可以给出为......

if(rear==-1) printf("Empty");

完整的条件将是......

if ( ( front==(rear+1) || (front==0 && rear==(n-1) ) && rear!=-1 ) printf("Full");

这可能有效。没有使用“计数”功能

于 2013-12-04T17:31:48.273 回答
0

另一种方法是使用三个指针，其中第三个指针指向两个指针之间的位置。有多种方法可以实现这一点。不过要注意的关键是中间指针只需要告诉以下两件事。

  • 队列是空的。所有指针都指向同一个地方（后指针的第二个定义）。
  • 队列有 1 个元素，删除一个元素将使其为空。中间指针和另一个指针指向同一个地方。

这可以简单地通过将中间指针保持在第一个和最后一个之间来完成，只要队列有 1 个或多个元素，就可以从第一个或最后一个指针偏移一个。

这可能充其量只是对使用计数器的轻微改进，甚至可能是最差的。

于 2013-06-23T02:27:15.847 回答