Проблема с круговой очередью

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

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

SO, 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

Реализация автора не является ошибочной и преднамеренной, но вы ее не увидите, если не подумаете о процессе dequeue. Проблема в том, как определить, будет ли очередь пуста?

Очередь пуста, когда spos == rpos. Если вы не скажете, что очередь заполнена, когда spos+1 == rpos, но spos == rpos, вы потеряли возможность рассказать разницу между полной и пустой очередью.

Вы правы, однако, заметили, что вы оставите одну запись в очереди свободной. Ваша очередь будет содержать только 99 элементов, а не 100. Это «отсутствует» - это цена, которую вы платите за то, что вам нужно различать полную и пустую круглую очередь без использования каких-либо дополнительных переменных, кроме rpos, spos и queue.