Проблема круговой очереди

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

Он также заявляет, что: Очередь заполнена, когда индекс хранилища равен на единицу меньше, чем индекс извлечения; в противном случае в очереди есть место для другого события.

ТАК, в соотв. автору, если 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.