Introduction
La file d'attente circulaire (aussi appelé une queue) offre la possibilité d'avoir une liste d'éléments dont le premier entrée (Enqueue) est le premier à sortir (Dequeue). Les anglais l'appel FIFO, soit l'abréviation de l'anglicisme First-in First-out. Contrairement, à un vulgaire tableau allant dans une direction unidirectionnel comme une pile, on ne peut pas simplement enlever au début et retirer à la fin, car on risquerait d'avoir un gaspillage d'espace assez rapidement. Pour résoudre le problème, on place au index sur l'élément entrant courant et un index sur l'élément sortant courant et s'ils ne sont pas égale, on peut en rajouter autant que l'on veut. Lorsque les éléments insérés ont atteint la fin du tableau, il recommence au début du tableau et ainsi de suite. On obtient ainsi un mouvement circulaire.
Voici un tableau fictif de 7 lettres entrant et 2 sortant et leurs positions dans le tableau :
| ENTREE | SORTIE | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| A | - | A | ||||
| B | - | A | B | |||
| C | - | A | B | C | ||
| D | - | A | B | C | D | |
| E | - | A | B | C | D | E |
| - | A | - | B | C | D | E |
| F | - | F | B | C | D | E |
| - | B | F | - | C | D | E |
| G | - | F | G | C | D | E |
Algorithme
Voici l'algorithme de cette technique :
|
MODULE taille RETOURNER (N - f + r) mod N MODULE estVide RETOURNER f = r * Dequeue MODULE extraire SI estVide ALORS Message "File d'attente vide" FIN SI e ← Q[f] Q[f] ← NIL f ← (f + 1) mod N RETOURNER e * Enqueue MODULE insertion(o) SI taille = N - 1 ALORS Message "File d'attente pleine" FIN SI Q[r] ← o |
Exemple
L'exemple suivant permet, écrit en Free Pascal, permet d'utiliser une file d'attente circulaire à l'aide d'un tableau :
- Program FileCirculairesSamples;
-
- Const
- Maximum = 5;
-
- Type
- Objet=Integer;
- FileCirculaire=Record
- Element:Array[0..Maximum] of Objet;
- IndexIn,IndexOut:0..Maximum;
- Plein:Boolean;
- End;
-
- Var
- FC:FileCirculaire;
- Valeur:Objet;
- I:Integer;
-
- Procedure Initialisation(Var FC:FileCirculaire);Begin
- FC.IndexIn := 0;
- FC.IndexOut := 0;
- FC.Plein := False;
- End;
-
- Function EstVide(FC:FileCirculaire):Boolean;Begin
- EstVide := (FC.IndexIn = FC.IndexOut) and Not FC.Plein;
- End;
-
- Procedure Insertion(Var FC:FileCirculaire;Valeur:Objet);Begin
- If FC.Plein Then Begin
- WriteLn('Tampon plein');
- End
- Else
- Begin
- FC.Element[FC.IndexIn] := Valeur;
- FC.IndexIn:=(FC.IndexIn+1) mod (Maximum+1);
- FC.Plein:=FC.IndexIn=FC.IndexOut;
- End;
- End;
-
- Procedure Extraire(Var FC:FileCirculaire;Var Valeur:Objet);Begin
- If EstVide(FC)Then WriteLn('File circulaire vide')
- Else
- Begin
- Valeur:=FC.Element[FC.IndexOut];
- FC.IndexOut:=(FC.IndexOut+1) mod (Maximum + 1);
- FC.Plein:=False;
- End;
- End;
-
- BEGIN
- Initialisation(FC);
- Insertion(FC,5);
- Insertion(FC,10);
- Insertion(FC,15);
- Insertion(FC,17);
- Extraire(FC,Valeur);
- Insertion(FC,20);
- Insertion(FC,25);
- Insertion(FC,27);
- Extraire(FC,Valeur);
- Insertion(FC,30);
- For I:=1 to 5 do Begin
- Extraire(FC,Valeur);
- WriteLn(Valeur);
- End;
- END.
on obtiendra le résultat suivant :
1517
20
25
27