Section courante

A propos

Section administrative du site

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 :

  1. Program FileCirculairesSamples;
  2.  
  3. Const
  4.  Maximum = 5;
  5.  
  6. Type
  7.  Objet=Integer;
  8.  FileCirculaire=Record
  9.   Element:Array[0..Maximum] of Objet;
  10.   IndexIn,IndexOut:0..Maximum;
  11.   Plein:Boolean;
  12.  End;
  13.  
  14. Var
  15.  FC:FileCirculaire;
  16.  Valeur:Objet;
  17.  I:Integer;
  18.  
  19. Procedure Initialisation(Var FC:FileCirculaire);Begin
  20.  FC.IndexIn := 0;
  21.  FC.IndexOut := 0;
  22.  FC.Plein := False;
  23. End;
  24.  
  25. Function EstVide(FC:FileCirculaire):Boolean;Begin
  26.  EstVide := (FC.IndexIn = FC.IndexOut) and Not FC.Plein;
  27. End;
  28.  
  29. Procedure Insertion(Var FC:FileCirculaire;Valeur:Objet);Begin
  30.  If FC.Plein Then Begin
  31.   WriteLn('Tampon plein');
  32.  End
  33.   Else
  34.  Begin
  35.   FC.Element[FC.IndexIn] := Valeur;
  36.   FC.IndexIn:=(FC.IndexIn+1) mod (Maximum+1);
  37.   FC.Plein:=FC.IndexIn=FC.IndexOut;
  38.  End;
  39. End;
  40.  
  41. Procedure Extraire(Var FC:FileCirculaire;Var Valeur:Objet);Begin
  42.  If EstVide(FC)Then WriteLn('File circulaire vide')
  43.   Else
  44.  Begin
  45.   Valeur:=FC.Element[FC.IndexOut];
  46.   FC.IndexOut:=(FC.IndexOut+1) mod (Maximum + 1);
  47.   FC.Plein:=False;
  48.  End;
  49. End;
  50.  
  51. BEGIN
  52.  Initialisation(FC);
  53.  Insertion(FC,5);
  54.  Insertion(FC,10);
  55.  Insertion(FC,15);
  56.  Insertion(FC,17);
  57.  Extraire(FC,Valeur);
  58.  Insertion(FC,20);
  59.  Insertion(FC,25);
  60.  Insertion(FC,27);
  61.  Extraire(FC,Valeur);
  62.  Insertion(FC,30);
  63.  For I:=1 to 5 do Begin
  64.   Extraire(FC,Valeur);
  65.   WriteLn(Valeur);
  66.  End;
  67. END.

on obtiendra le résultat suivant :

15
17
20
25
27

Dernière mise à jour : Vendredi, le 21 avril 2017