c - 循环排队问题

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

#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 */
}

他进一步指出：当存储索引比检索索引少一个时，队列已满；否则，队列中还有空间容纳另一个事件。
因此，根据作者的说法，如果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;

}

我的密码正确吗？

最佳答案

作者的实现没有错，而且是有意的，但是除非考虑/查看出列过程，否则您不会看到它。问题是如何确定队列是否为空？
spos == rpos时队列为空。如果您在spos+1 == rpos时没有说队列已满，但是spos == rpos您已经失去了区分已满队列和空队列的能力。
您是正确的，但是注意到您将保留一个队列条目为空。您的队列将只容纳99个项目，而不是100个。这个“丢失”是您需要在不使用rpo、spos和queue之外的任何其他变量的情况下区分完整循环队列和空循环队列所付出的代价。