循环队列问题

Question

我正在从一本书中学习队列。在学习循环队列时遇到了问题。我所学的作者使用以下代码片段来解释如何将元素插入循环队列。

#define MAX 100
char *p[MAX];
int spos = 0; // spos: holds the index of the **next free** storage location

int rpos = 0;// rpos: holds the index of the next item to retrieve

void qstore(char *q)
{
  /* The queue is full if either spos is one less than rpos
      or if spos is at the end of the queue array and rpos
      is at the beginning.
  */
  if(spos+1= =rpos || (spos+1==MAX && !rpos)) <-- /***Problem is here**. Is it even  
                                                    correct?*/
  {
     printf(''List Full\n");
     return;
  }
  p[spos] = q;
  spos++;

  if(spos==MAX) 
  spos = 0; /* loop back */
}

他进一步指出：当存储索引比检索索引小1时，队列已满；否则，队列中还有空间来容纳另一个事件。 因此，根据作者的说法，如果spos（它保存了下一个自由存储位置的索引）等于4且rpos=5，则队列已满吗？这不正确吗？因为spos=3意味着p[3]中的内存位置为空。

---

因此，我决定更改程序。

#define MAX 100
char *p[MAX];
int spos = 0; // spos: holds the index of the **last allocated** storage location

int rpos = 0;// rpos: holds the index of the next item to retrieve

void qstore(char *q)
{
  /* The condition for queue full is same as the previous program*/

 /* The queue is full if either spos is one less than rpos
      or if spos is at the end of the queue array and rpos 
      is at the beginning.
  */

if((spos+1==rpos) || (spos+1==MAX && rpos==0)) // Also changed syntax of test condition.
 {
   printf("Queue Full\n");
 } 

spos++

if((spos+1==MAX) && (rpos!=0))
 {
   spos=0;
 }
else
{
  spos++;
}

 p[spos]=q;

}

我的代码正确吗？

- Naruto Uzumaki

---

你能否说一下，你引用的是哪本书/作者？ - Jens Gustedt

C语言程序设计: 完整参考(第4版), 作者Ed Herbert Schildt - Naruto Uzumaki

Answer 1

作者的实现没有问题，而是有意为之，但除非你思考或查看出队过程，否则你不会注意到它。问题在于如何确定队列为空？

当时，队列为空。如果您不认为当时队列已满，但，那么您将失去区分满队列和空队列的能力。

然而，您正确地注意到您将留下一个队列条目可用。您的队列只能容纳99个项目而不是100个。这个“缺失”就是您需要在不使用任何额外变量的情况下区分满循环队列和空循环队列所付出的代价。

- shf301

---

是的，你的代码有问题。它将spos增加了两次，所以你只会使用p中的每个其他条目。 - shf301

哦！那是一个无意的错误。我编辑了这段代码。之前没有else检查，后来我添加了它，可能忘记删除之前的语句了。如果我在if-else块之前删除那个额外的增量，我的代码会正确吗？ 我想不会，也许我需要考虑空值，并且我可能会在查找空队列检查时遇到问题。 - Naruto Uzumaki

一种不浪费队列空间的好方法是将队列大小设置为2的幂，并使读/写索引在更大的2的幂处循环。这样，可以轻松区分队列满和队列空的情况，而无需额外的存储空间（除非队列大小为256或65,536个元素）。在C语言中，最简单的方法是让索引只是无符号整数类型，并在需要时进行循环。 - supercat