这个通过数组实现队列的伪代码有效吗？

Question

编写一个伪代码，通过名为 Q 的大小为 n 的数组实现队列，索引从 1 开始（即 Q 的索引从 1 开始，而不是通常的 0）。

代码中必须使用下面两个函数Q.head和Q.tail，其说明如下：

Q.head ：此函数返回数组 Q 中要插入下一个元素的索引。

Q.tail：此函数返回数组 Q 中第一个元素存储在开头的索引。

必须采取预防措施来解决代码中的上溢和下溢错误。

提供的代码必须具有名为 Enqueue、Dequeue 的 3 个核心函数，如下所述：

Enqueue：该函数接受两个参数并在队列中添加一个新元素，

Dequeue ：此函数不接受任何元素参数，并按照通常的 FIFO（先进先出）顺序将元素从队列中出列。

我正在学习的书是 Cormen、Leiserson、Rivest 和 Stein 的《算法导论》。书上给出的东西如下：

在我们的 ENQUEUE 和 DEQUEUE 过程中，我们省略了下溢和溢出的错误检查。

伪代码假设 n=Q.length。

ENQUEUE(Q,x)
1 Q[Q.tail]=x
2 if Q:tail = = Q.length
3 Q:tail=1
4 else Q.tail = Q.tail + 1
DEQUEUE(Q)
1 x=Q[Q.head]
2 if Q.head == Q.length
3 Q.head=1
4 else Q.head = Q.head + 1
5 return x

---

可以看出上面的伪代码采用了循环队列的方式，通过数组Q来实现队列。

但我认为，这使问题变得不必要的复杂，我们也可以“正常”解决这个问题，即无需实现循环队列方法。因此，我继续编写了一个不使用循环队列方法的伪代码，如下所示：

Enqueue(Q,x)

   if (Q.tail==Q.length +1)

               error overflow

   else

           Q[Q.tail]=x
           Q.tail=Q.tail+1

  Dequeue(Q)

         int  fl=0, x=0

         If (Q.head<=Q.length )

              {

                x=Q[Q.head]

                 fl=1

              }

          If (Q.head<Q.length)

               Q.head=Q.head+1

                return x

          else 

                 print("Queue Empty")
                 error underflow

上面的伪代码是书中给出的方法的有效替代方法吗？

如果我提供的伪代码有任何问题，请告诉我。

Answer 1

来自原始示例，带注释：

ENQUEUE(Q,x)
    Q[Q.tail] = x
    if Q:tail == Q.length
        # not necessarily overflow -- this is just circular wrapping
        Q:tail = 1
    else
        Q.tail = Q.tail + 1

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        # not necessarily underflow -- this is just circular wrapping
        Q.head = 1
    else
        Q.head = Q.head + 1
    return x

请注意，这已经与您的陈述相矛盾：

Q.head ：此函数返回数组 Q 中要插入下一个元素的索引。

Q.tail：此函数返回数组 Q 中第一个元素存储在开头的索引。

这是错误的。

Q.head

存储出队时将“返回”的下一个元素的索引。 Q.tail 存储入队时元素的下一个

可用

位置的索引。 您的任务是检测上溢和下溢。首先考虑边缘情况...

鉴于上述情况，您如何知道队列已满？嗯，

Q.head

必须等于

Q.tail

，因为当您填满队列时，所有其他“可用”位置都已被使用。但是你怎么知道队列是空的呢？因为

also

肯定意味着两者相等。 如何区分它们？使用哨兵值。您可以随心所欲地执行此操作。一种自然的方法是考虑：

“如果 'head' 表示下一个要出队的项目的位置，并且队列为空，则该值没有意义”

。 这是一个很好的候选人。您可以使用一个特殊值来表示“无处指向”。如果队列为空，则将头设置为零。现在您有了区分满和空的真正方法，您可以按如下方式调整算法：

ENQUEUE(Q,x)
    # Raise error if queue has no available space
    if Q.tail == Q.head
        raise Q.overflow

    # Queue is no longer empty
    if Q.head == 0
        Q.head = Q.tail

    # Push data to queue
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else
        Q.tail = Q.tail + 1

DEQUEUE(Q)
    # Raise error if queue is empty
    if Q.head == 0
        raise Q.underflow

    # Pop data from queue
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else
        Q.head = Q.head + 1

    # Mark queue empty if we just popped the last item
    if Q.head == Q.tail
        Q.head = 0

    return x