理解数据结构中的队列算术

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

的绝对索引/地址。它们是相对的，当吃豆人离开屏幕一侧时，您可以使用模算术开始返回到数组的开头。当您绘制这些内容以在白板上将数组绘制为圆圈时，它会很有用。

当我现在想添加一个元素时，我在位置 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

时队列已满。我们需要模运算来处理那些“绕到另一边”的情况。