Cours d'algorithmique : FILES D'ATTENTE cours avec des exemples

MODELISATION DE LA STRUCTURE 

 

Introduction

Une file d'attente est une structure qui stocke de manière ordonnée des éléments, mais rend accessible  uniquement  un  seul  d'entre eux,  appelé  la  tête  de  la  file.  Quant  on  ajoute  un élément, celui-ci devient le dernier élément qui sera accessible. Quant on retire un élément de la file, on retire toujours la tête, celle-ci étant le premier élément qui a été placé dans la file. Pour résumer,  le premier élément ajouté dans  la pile est  le premier élément à en être retiré. Cette structure est également appelée une liste FIFO (First In, First Out). 

Généralement, il y a deux façons de représenter une file d'attente. La première s'appuie sur la structure  de  liste  chaînée  vue  précédemment. La  seconde manière  utilise  un  tableau d'une façon assez particulière que l'on appelle modélisation par "tableau circulaire".  

     

Modélisation par liste chaînée

La  première  façon de modéliser  une  file  d'attente consiste  à  utiliser  une  liste chaînée en n'utilisant que  les  opérations  ajouterQueue  et  retirerTete. Dans  ce cas, on  s'aperçoit  que  le premier élément entré est toujours le premier élément sorti. La figure suivante représente une file d'attente par cette modélisation. La  file contient les chaînes de caractères suivantes qui ont été ajoutées dans cet ordre: "Paris", "Marseille", "Bordeaux", "Lyon" et "Toulouse".  

       

Pour cette modélisation, la structure d'une file d'attente est celle d'une liste chaînée. 
 

type FILE_LST: LISTE; 

Modélisation par tableau circulaire

La  deuxième manière  de modéliser  une  file  d'attente  consiste  à  utiliser  un  tableau. L'ajout d'un élément se fera à la suite du dernier élément du tableau. Le retrait d'un élément de la file se  fera en  enlevant le  premier  élément  du  tableau.  Il  faudra  donc  deux  indices  pour  ce tableau, le premier qui indique le premier élément de la file et le deuxième qui indique la fin de la file. La figure suivante représente une file d'attente par cette modélisation. Elle reprend la même pile que pour l'exemple de modélisation par liste chaînée.  

     

 

On peut noter que progressivement, au cours des opérations d'ajout et de retrait, le tableau se déplace  sur  la droite dans  son espace mémoire. A un moment,  il va en atteindre  le bout de l'espace.  Dans  ce cas,  le  tableau  continuera  au début  de  l'espace  mémoire  comme  si  la première et  la  dernière case  étaient  adjacentes, d'où  le  terme  "tableau  circulaire".  Ce mécanisme  fonctionnera  tant  que  le  tableau n'est  effectivement  pas  plein.  Pour  illustrer, reprenons  l'exemple précédent auquel on applique  trois opérations de retrait de  l'élément de tête.  On  ajoute  également  en queue  les  éléments suivants  et  dans  cet  ordre:  "Orléans", "Nantes", "Poitiers", "Nice".  

La  file d'attente contient alors, et dans cet ordre:  "Lyon",  "Toulouse", "Orléans", "Nantes", "Poitiers"  et  "Nice". On  s'aperçoit  que,  ayant  atteint  la  fin du  tableau,  la  file  redémarre  à l'indice 0.  

Voici la  structure  de  données  correspondant  à  une  file d'attente  représentée par  un  tableau circulaire. 

          
structure FILE_TAB:
 ELEMENT tab[NMAX];
 ENTIER  tete;
 ENTIER  fin;
fin structure;

  
NMAX est une constante représentant la  taille du  tableau alloué.  tete est l'indice de  tableau qui  pointe  sur  la  tête  de  la  file  d'attente.  fin  est  l'indice  de  tableau qui  pointe  sur  la case suivant le dernier élément du tableau, c'est-à-dire la prochaine case libre du tableau.  

OPERATIONS SUR LA STRUCTURE 

Introduction

A partir de maintenant, nous allons employer le type FILE qui représente une file d'attente au sens général, c'est-à-dire sans se soucier de sa modélisation. FILE représente aussi bien une file  d'attente  par  liste chaînée  (FILE_LST)  qu'une  file  d'attente  par  tableau  circulaire (FILE_TAB). Voici les opérations que nous allons détailler pour ces deux modélisations.  

 

• initialiserFile(FILE * f) 

Initialise la file pointée par f, i.e. fait en sorte que la file soit vide.   

• BOOLEEN <-- fileVide(FILE f)  

Indique si la file f est vide.  

• ELEMENT  <--  teteFile(FILE f)  

Retourne l'élément en tête de la file f.  

• BOOLEEN  <--  entrerElement(FILE * f, ELEMENT e)  

Entre l'élément e dans la file pointée par f.  

• BOOLEEN  <--  sortirElement(FILE * f, ELEMENT * e)  

Sort et copie à l'adresse e l'élément en tête de la file pointée par f.  

     
Les prototypes de ces opérations (paramètres et  type de retour) sont les mêmes quelque soit la modélisation choisie.  

Opérations pour la modélisation par liste chaînée

Initialiser une file 

Cette fonction initialise les valeurs de la structure représentant la file pointée par f pour que celle-ci  soit  vide. Dans  le  cas d'une  représentation par  liste chaînée,  il  suffit d'initialiser  la liste chaînée qui représente la file d'attente.  

       
fonction initialiserFile(FILE * f):
 initialiserListe(f);
fin fonction;

File vide ?

     
Cette fonction indique si la file f est vide. Dans le cas d'une représentation par liste chaînée, la file est vide si la liste qui la représente est vide.  

            
fonction BOOLEEN  <--  fileVide(FILE f):
 rendre listeVide(f);
fin fonction;

Tête d'une file

        
Cette fonction retourne l'élément en tête de la file f. Dans le cas d'une représentation par liste  chaînée, cela revient à retourner la valeur de l'élément en tête de la liste. A n'utiliser que si la file f n'est pas vide. 

        
ELEMENT  <--  teteFile(FILE f):
 si (non fileVide(f)) alors
  rendre teteListe(f);
 sinon
  /* Erreur */
 fin si;
fin fonction;

Entrer un élément dans une file

        
Cette fonction place un élément e en queue de la file pointée par f. Pour la représentation par liste  chaînée,  cela  revient  à  ajouter  l'élément  e  en queue de  la  liste. VRAI  est  retournée  si l'ajout a bien pu se faire. 

          
fonction BOOLEEN  <--  entrerElement(FILE * f, ELEMENT e):
 rendre ajouterQueue(f,e);
fin fonction;

Sortir un élément d'une file

       
Cette fonction retire l'élément en tête de la file pointée par f et stocke sa valeur à l'adresse e. Pour la représentation par liste chaînée, cela revient à récupérer la valeur de l'élément en tête de  liste  avant  de  le  supprimer  de  cette  dernière.  Si  la  file  n'est  pas  déjà  vide,  VRAI  est retournée. 

          
fonction BOOLEEN  <--  sortirElement(FILE * f, ELEMENT * e):
 si (non fileVide(*f)) alors
  *e  <--  teteFile(*f);
  rendre retirerTete(f);
 sinon
  rendre FAUX;
 fin si;
fin fonction; 

Opérations pour la modélisation par tableau circulaire

Initialiser une file

        
Cette fonction initialise les valeurs de la structure représentant la file pointée par f pour que celle-ci  soit  vide.  Dans  le  cas  d'une  représentation par  tableau  circulaire, on  choisira  de considérer  la  file  vide  lorsque  f tete = f fin. Arbitrairement, on  choisit ici  de mettre  ces deux indices à 0 pour initialiser une file d'attente vide.  

           
fonction initialiserFile(FILE * f):
 f --> tete  <--  0;
 f --> fin  <-- 0;
fin fonction;

File vide ?

       
Cette  fonction  indique  si la  file  f  est  vide.  Dans  le  cas  d'une  représentation par  tableau circulaire, la file est vide lorsque f.tete = f.fin.  

           

fonction BOOLEEN  <--  fileVide(FILE f):
 rendre (f.tete = f.fin);
fin fonction;

Tête d'une file 

Cette  fonction  retourne  l'élément  en  tête  de  la  file  f. Dans  le  cas  d'une  représentation par tableau circulaire, il suffit de retourner l'élément pointé par l'indice de tête dans le tableau. A n'utiliser que si la file f n'est pas vide.  

               
ELEMENT  <--  teteFile(FILE f):
 si (non fileVide(f)) alors
  rendre (f.tab[f.tete]);
 sinon
  /* Erreur */
 fin si;
fin fonction;

Entrer un élément dans une file

Cette  fonction place un  élément  e  en queue de  la  file  f. Pour  la  représentation par  tableau circulaire,  l'élément  est  placé  dans  la  case  pointée  par  l'indice  fin.  Ce  dernier  est  ensuite augmenté d'une unité, en tenant compte du fait qu'il faut revenir à la première case du tableau si il a atteint la fin de celui-ci. D'où l'utilisation de l'opérateur mod qui retourne le reste de la division entre ses deux membres. Si le tableau n'est pas plein au moment de l'insertion, VRAIest retournée. 

         
fonction BOOLEEN  <--  entrerElement(FILE * f, ELEMENT e):
 si ((f --> fin + 1) mod NMAX = f --> tete) alors rendre FAUX;
 f --> tab[f --> fin]  <--  e;
 f --> fin  <--  (f --> fin + 1) mod NMAX;
 rendre VRAI;
fin fonction;

         
On détecte  que  le  tableau  est  plein  si  l'indice  fin  est juste  une case avant l'indice  tete. En effet, si on ajoutait une case, fin deviendrait égal à  tete, ce qui est notre configuration d'une file  vide.  La  taille maximale  de  la  file  est  donc  NMAX  -  1, une  case  du  tableau  restant toujours inutilisée.  

Sortir un élément d'une file 

       
Cette  fonction  retire  l'élément  en  tête  de  la  file  f  et  stocke  sa  valeur  à  l'adresse  e. Pour  la représentation par tableau circulaire, cela revient à récupérer la valeur de l'élément en tête de file avant de  le  supprimer en augmentant l'indice  tete d'une unité.  Il ne  faut pas oublier de ramener tete à la première case du tableau au cas où il a atteint la fin de ce dernier. VRAI est retournée s'il restait au moins un élément dans la file.  

               
fonction BOOLEEN   sortirElement(FILE * f, ELEMENT * e):
 si (fileVide(*f)) alors rendre FAUX;
 *e <-- teteFile(*f);
 f --> tete <--  (f -->tete + 1) mod NMAX;
 rendre VRAI; 

fin fonction; 

 

CONCLUSION 

Ce genre de  structure de données est très utilisée par  les mécanismes d'attente. C'est  le cas notamment d'une imprimante en réseau, où les tâches d'impressions arrivent aléatoirement de n'importe  quel  ordinateur  connecté. Les  tâches sont  placées  dans  une  file  d'attente,  ce  qui permet  de  les  traiter  selon  leur  ordre  d'arrivée.  Les  remarques  concernant les  différences la modélisation par liste chaînée et la modélisation par tableau circulaire sont les mêmes que pour la structure de file. Très peu de différences sont constatées. En résumé, la modélisation par liste chaînée sera un peu plus lente, mais plus souple quant à sa taille.  

------------------------------------------------------------------------------------------------------
 <<< CHAPITRE III : LES PILS

            >>> CHAPITRE V : ARBRES BINAIRES