循环队列问题

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时,队列已满; 否则,队列中有另一个事件的空间.

所以,acc.对于作者,如果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;

}

我的代码是否正确？

Answer 1

作者的实现没有错并且是有意的,但除非你考虑/看到出列过程,否则你不会看到它.问题是如何确定队列何时为空？

队列为空时spos == rpos.如果您没有说队列已满spos+1 == rpos,但spos == rpos您已经无法区分完整队列和空队列.

你是正确的但是注意到你将留下一个队列条目免费.您的队列只能容纳99个项而不是100个."缺失"是您需要在不使用rpos,spos和queue之外的任何其他变量的情况下区分完整和空循环队列所需的价格.