Définition
File :
En informatique, une file (en anglais "queue") est une structure de données de type FIFO (anglais pour First In, First Out), c'est à dire fondée sur le principe « premier arrivé, premier sorti » . Les premiers éléments ajoutés à la file seront les premiers à être récupérés.
La manière la plus simple de comprendre le fonctionnement d'une file est d'imaginer une file d'attente à une caisse. Un traitement (le paiement de l'article) doit être appliqué à chacune des données (ici les clients). La structure se comporte de sorte que le premier client entré dans la file d'attente sera traité en premier lors de l'opération associée. Un client arrivant est enfilé , c'est à dire qu'il prend sa place dans la file d'attente. Il sera alors traité suivant son ordre d'arrivée. Une fois en tête de file, on dit qu'il est défilé pour être traité.
Il peut être déduit de cet exemple qu'un caisser traitant une file de client aura besoin de quatre primitives ou fonctions de service associées à une structure de type file:
- enfiler (en anglais "enqueue"): ajouter un élément à la file
- défiler (en anglais "dequeue"): enlever un élément de la file
- la file est-elle vide?
- combien y'a-t-il d'éléments dans la file?
Structure d'une file
Une file est représentée en mémoire par une structure de donnée contenant un tableau dont les éléments sont du type souhaité. Le comportement de file FIFO est obtenu par l'ajout et le jeu sur deux indices: tete et queue , respectivement la position dans le tableau du premier élément appelé 'tête de file', et celle du dernier élément appelé 'queue de file'. A ces deux indices, est ajouté tailleMax , la taille maximale de la file.
Par convention, l'indice de la tete d'une file vide est -1.
Structure de File en Pseudo-Code :
Structure De File:
- tableau_de_Element
- tailleMax
- tete
- queue
Fin de structure
Structure FIFO pour une File en C (cliquer pour ouvrir)
typedef struct file
{
Element * pTabElement; // Pointeur vers le tableau des éléments
int iTailleMax; // Taille maximale de la File
int iTete; // Indice de la tête de file : -1 si File vide
int iQueue; // Indice de la queue de file
}
File;
Primitives
La file est-elle vide ?
Nous avons rappelé en présentation de la structure de file que la convention voulait que la tête d'une file vide ait pour indice -1. C'est donc ce qu'il suffit de vérifier pour savoir si la file est vide.
Primitive 'FileVide' en Pseudo-Code :
Fonction FileVide (File F):
Si tete[F] = -1 alors
retourner VRAI
Sinon
retourner FAUX
FinSi
FinFonction
Implémentation en C de la primitive 'FileVide' (cliquer pour ouvrir)
int FileVide ( File* f)
{
if ( f-> iTete == - 1 ) // Si tete[F]=-1 :
return 1 ; // c'est que la file est vide
else
return 0 ;
}
Nombre d'éléments dans la file
Le nombre de personnes dans une file d'attente est le nombre de personne entre la première et la dernière. Dans une file, le dernier élément est repéré par queue[F] et le premier tete[F]. Le nombre de personne dans la file est alors tout simplement la soustraction des deux.
Primitive 'NbreElement' en Pseudo-Code :
Fonction NbreElement (File F):
taille = iQueue[F] - iTete[F]
retourner taille
FinFonction
Implémentation en C de la primitive 'NbreElement' (cliquer pour ouvrir)
int NbreElement ( File* f)
{
int taille;
/* vérification séparée du cas 'FileVide' */
if ( f-> iTete == - 1 ) // Si la tête vaut -1
return 0 ; // alors la liste est vide
taille = f-> iQueue - f-> iTete; // taille = position du dernier - position du 1er
return taille;
}
Enfilage
Enfiler un élément dans une file revient simplement à l'ajouter à la fin de celle-ci. Une simple vérification toutefois: il faut que la file ne soit pas pleine!
Primitive 'Enfiler' en Pseudo-Code :
Fonction Enfiler(File F, Element NouvElement):
Si NbreElement[F] < tailleMax[F] alors
# Ajout du nouvel élément #
# en queue de la file #
file[queue[F]] = nouvElement
incrémente queue[F]
Sinon
Afficher "File pleine";
FinSi
FinFonction
Implémentation en C de la primitive 'Enfiler' (cliquer pour ouvrir)
int Enfiler ( File* f, Element* pNouvElement)
{
if ( NbreElement( f) < f-> iTailleMax) // si la file n'est pas pleine...
{
f-> pTabElement[ f-> iQueue] = pNouvElement; // Ajout du nouvel élément en queue
if ( p-> iTete == - 1 ) // Si la vide est vide:
p-> iTete = 0 ; // Déplacement de la tete
f-> iQueue = ( f-> iQueue+ 1 ) % p-> iTailleMax; // Déplacement de la queue de file
return 1 ; // SUCCES
} else // Sinon
return 0 ; // ECHEC (cause: file pleine)
}
Défilage
Le défilage consiste tout simplement à enlever le premier élément en tête de file, à condition bien-sûr que celle-ci ne soit pas vide.
Primitive 'Défiler' en Pseudo-Code :
Fonction Defiler (File F): Element:
Si (F non vide) alors
Element = file[tete[F]]
incrémente tete[F]
Sinon
Afficher "File vide"
FinSi
Retourner element
FinFonction
Implémentation en C de la primitive 'Defiler' (cliquer pour ouvrir)
Element* Defiler ( File* f)
{
Element* pTempElement;
if ( FileVide[ f] ) // Si la file est vide:
return NULL; // ECHEC (cause: file vide)
pTempElement = f-> pTabElement[ f-> iTete] ] ; // Récupération de l'élément
p-> iTete = ( p-> iTete+ 1 ) % p-> iTaille; // Décalage de la tête
if ( p-> iTete == p-> iQueue) // Si la file devient vide:
{
p-> iTete = - 1 ; // Application de la convention
p-> iQueue = 0 ; // Réinitialisation de la file
}
return pTempElement; // Renvoit de l'élément défilé
}
