Problème de file d'attente circulaire

Question

J'apprends des files d'attente à partir d'un livre. J'ai eu un problème en apprenant la file d'attente circulaire. L'auteur à partir duquel j'apprends utilise le code suivant pour expliquer comment un élément est inséré dans une file d'attente circulaire.

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

Il déclare en outre que: La file d'attente est pleine lorsque l'index de magasin est un de moins que l'indice récupérer; sinon, il y a de la place dans la file d'attente pour un autre événement.

SO, acc. à l'auteur, si spos (qui contient l'index du prochain emplacement de stockage libre) est égal à 4 et rpos = 5, puis la file d'attente est pleine. N'est-ce pas incorrect? Parce que spos = 3 signifie que l'emplacement de la mémoire à p [3] est vide.

---

J'ai donc décidé de changer le programme.

#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; 

} 

Mon code est-il correct?

Answer 1

La mise en œuvre de l'auteur n'est pas fausse et est intentionnelle, mais vous ne la verrez pas à moins de penser au processus de dequeue. Le problème est de savoir comment déterminez-vous si la file d'attente est vide?

La file d'attente est vide lorsque spos == rpos. Si vous ne dites pas que la file d'attente est pleine quand spos+1 == rpos, mais spos == rpos vous avez perdu la capacité de faire la différence entre une file d'attente pleine et vide.

Vous avez raison mais vous remarquerez que vous laisserez une entrée de file d'attente libre. Votre file d'attente ne contiendra que 99 éléments et non 100. Ce "manquant" est le prix que vous payez pour avoir besoin de faire la distinction entre une file circulaire pleine et vide sans utiliser de variables supplémentaires en dehors de rpos, spos et queue.