了解数据结构中的队列算法

Question

当一个元素被插入队列时，REAR = REAR + 1。当一个元素从队列中删除时，FRONT = FRONT + 1 当队列使用数组实现时。

现在，最初，两个 FRONT = REAR = -1 指示队列都是空的。添加第一个元素时，FRONT = REAR = 0（假设数组从0到n-1）。

现在，如果我们假设 FRONT = 0 and REAR = n-1 暗示队列已满的情况。当删除一些元素时，FRONT 指针会发生变化。让我们说 FRONT = 5 and REAR = 10。因此，数组位置 0 到 4 是空闲的。

当我现在想添加一个元素时，我在位置 0 添加并且 FRONT 指向它。但是位置1、2、3、4是免费的。

但是，当我下次尝试插入一个元素时，编译器会抛出一个错误，说队列已满。自 FRONT = 0 and REAR = n-1。如何在剩余位置插入并更好地理解这种排队算法？

我也想了解FRONT = REAR + 1如何作为检查队列是否已满的条件？

Answer 1

您想在这里根据相对的循环范围而不是绝对的线性范围来循环思考。因此，您不想过于关注 FRONT 和 REAR 的绝对值 indices/addresses。它们是相互关联的，您可以使用取模算法开始回到数组的开头，就像吃豆人离开屏幕时一样。当您将这些东西绘制出来以在白板上将数组真正绘制为一个圆圈时，它会很有用。

当我想现在添加一个元素时，我在位置 0 添加，FRONT 指向它。但是位置1、2、3、4是免费的。

我觉得你有点倒退了。根据您的逻辑，插入会提前 REAR，而不是 FRONT。在这种情况下，REAR 将为 0，而 FRONT 仍将为 5。如果您再次按下，REAR=1 并且您将覆盖第一个索引，并且 FRONT 仍然是 5.

如果N=3和FRONT=2和REAR=2，经过多次推入和弹出后我们在队列中有一个元素。当您推送（入队）时，我们设置：REAR=(REAR+1)%N 使 FRONT=2、REAR=0 给我们两个元素。如果我们再次推送，FRONT=2，REAR=1 给我们 3 个元素，队列已满。

视觉上：

     R
  [..x]
     F

   R
  [x.x]
     F

    R
  [xxx]
     F

...现在我们已经满员了。如果 REAR 的下一个循环索引是 FRONT，则队列已满。在FRONT=2、REAR=1的情况下，我们可以看到(REAR+1)%N == FRONT，所以是满的

如果我们在此时弹出（出队），我们将设置 FRONT=(FRONT+1)%N，它看起来像这样：

    R
  [xx.]
   F

我也想了解FRONT = REAR + 1是如何作为检查队列是否已满的条件？

当您使用这种循环索引时，这是不够的。我们需要稍微增加一下：FRONT == (REAR+1)%N 时队列已满。我们需要模运算来处理那些 "wrap around to the other side" 个案例。

了解数据结构中的队列算法

Understanding queue arithmetic in data structures

queue

data-structures