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