File
DÉFINITIONS
• Une file (en anglais queue) est une structure de données basée sur le principe «
premier arrivé, premier sorti » (en anglais FIFO: First In First Out),
• Le fonctionnement ressemble à une file d'attente : les premières personnes à
arriver sont les premières personnes à sortir de la file.
DÉFINITIONS
• Une file d'attente peut être définie comme une collection d'éléments dans
laquelle tout nouvel élément est inséré (ajouté) à la fin (queue) et tout élément
ne peut être supprimé (retiré) que du début (tête).
UTILISATION
• Les files d’attente sont utilisées:
• en programmation comme des buffers (mémoire tampon = espace de
mémorisation temporaire),
• pour gérer des objets qui sont en attente d’un traitement ultérieur, tel que la
gestion des documents à imprimer, des programmes à exécuter, des messages
reçus,...etc.
MODÈLE
• Les opérations habituelles sur les files sont :
• Initialisation de la file
• Vérification du contenu de la file (vide ou pleine)
• Enfilement : ajout d’un élément à la queue de la file
• Défilement : retrait d’un élément de la tête de la file
Opération Rôle
Initfile(F) initialiser une file vide
Filevide(F) tester si la file est vide
Filepleine(F) tester si la file est pleine
Enfiler(F,Val) ajouter Val à la queue de file
Défiler(F,Val) retirer dans Val l'élément en tête de file
IMPLÉMENTATION
• Les files d’attente peuvent être présentées en deux manières:
• statique en utilisant les tableaux,
• dynamique en utilisant les listes linéaires chaînées.
• L’implémentation statique peut être réalisée par
• décalage en utilisant un tableau avec une tête fixe, toujours à 0, et une queue
variable.
• tableau circulaire où la tête et la queue sont toutes les deux variables.
IMPLÉMENTATION DYNAMIQUE
• La représentation dynamique utilise une liste linéaire chaînée (LLC). L’enfilement
se fait à la queue de la liste et de défilement se fait de la tête. La file d’attente,
dans ce cas, peut devenir vide, mais ne sera jamais pleine.
Tête Queue
Enfilement
1 @50 2 @10 3
Défilement @100 @50 @10
• Les opérations de base sont :
• Initialisation de la file
• Enfilement : insertion d’un élément à la queue de la LLC
• Défilement : suppression d’un élément de la tête de la LLC
• Vérification si la LLC n’est pas vide
IMPLÉMENTATION DYNAMIQUE
Définition de la structure :
TYPE Maillon = STRUCTURE
val : typeqq;
suiv: * Maillon;
FIN.
TYPE File_Attente = STRUCTURE
Tête, Queue : *Maillon;
FIN.
VAR F: File_Attente;
IMPLÉMENTATION DYNAMIQUE
Modèle Implémentation
Procedure InitFile(Var F:File)
Debut
Initfile
[Link] ← NIL; [Link]← NIL;
Fin.
Fonction FileVide(F:File):Boolean
Debut
FileVide
Retourner ([Link] = NIL );
Fin.
IMPLÉMENTATION DYNAMIQUE
Modèle Implémentation
Procedure Defiler(Var F:File, Var X: Entier)
Debut
SI (NON FileVide(F)) FAIRE
P ← [Link];
X ← Valeur([Link]);
[Link] ← Suivant([Link]);
Defiler SI [Link] = Nil alors
F,Queue ← Nil;
Fsi;
Liberer(P);
Fsi;
Fin.
IMPLÉMENTATION DYNAMIQUE
Modèle Implémentation
Procedure Enfiler(Var F:File, X: Entier)
Var P: *Maillon;
Debut
P = Allouer (); Aff_Val(P, X); aff_suiv(P, NIL);
SI (NON FileVide(F)) FAIRE
Enfiler aff_suiv([Link], P);
SINON
[Link] ← P;
Fsi;
[Link] ← P;
Fin.
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
• A chaque enfilement, on incrémente la queue.
Tête=0 Queue=4
5 8 9 15 50
0 1 2 3 4
Enfiler 55
Tête=0 Queue=5
5 8 9 15 50 55
0 1 2 3 4 5
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
• A chaque défilement, on fait un décalage.
• La tête n'est plus une caractéristique puisqu'elle est toujours égale à 0
Tête=0 Queue=4
5 8 9 15 50
0 1 2 3 4
Défiler (Décalage)
Tête=0 Queue=3
8 9 15 50
0 1 2 3 4
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
Queue=4
5 8 9 15 50
0 1 2 3 4 Max-1
Tableau T
Définition de la structure :
TYPE File_Attente = STRUCTURE
T : TABLEAU[Max] de Typeqq;
Queue : ENTIER;
FIN
VAR F : File_Attente;
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
Modèle Implémentation
Procedure InitFile(Var F:File)
Debut
Initfile
[Link] ←-1;
Fin.
Fonction FileVide(F:File):Boolean
Debut
FileVide
Retourner ([Link] = -1);
Fin.
Fonction FilePleine(F:File):Boolean
Debut
FilePleine
Retourner ([Link] = Max-1);
Fin.
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
Modèle Implémentation
Procedure Defiler(Var F:File, Var X: Entier)
Var I: Entier;
Debut
SI (NON FileVide(F))
X ← F.T[0];
POUR I ← 0 à [Link] – 1 FAIRE
Defiler
F.T[I] ← F.T[I+1];
FAIT;
[Link] ← [Link] – 1;
Fsi;
Fin.
IMPLÉMENTATION STATIQUE PAR DÉCALAGE
Modèle Implémentation
Procedure Enfiler(Var F:File, X: Entier)
Debut
SI (NON FilePleine(F)) ALORS
Enfiler [Link] ← [Link] + 1;
F.T[[Link]] ←X;
Fsi;
Fin.
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
• Les incrémentations se font modulo Max afin de réutiliser des cases libérées:
• Tete ← (Tete+1) mod Max & Queue ← (queue+1) mod Max
• Par convention,
• L'élément d'indice tête sera sacrifié (case vide).
• Le premier élément se trouve alors à l'indice (tête+1 mod Max)
Tête=0 Queue=4
8 9 15 50
0 1 2 3 4 9
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Tête=2 Queue=9
15 50 14 10 2 6 9
0 1 2 3 4 9
• Enfiler(F,-8)
Queue←
Queue=0 Tête=2 (Queue+1) Mod Max
-8 15 50 14 10 2 6 9
0 1 2 3 4 9
• Enfiler (F, 11) File Pleine,
Queue=1 Tête=2 Tête=(Queue+1) Mod
Max
-8 11 15 50 14 10 2 6 9
0 1 2 3 4 9
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Tête=0 Queue=4
8 9 15 50
0 1 2 3 4 9
• Défiler(F,V)
Tête=1 Queue=4
9 15 50
0 1 2 3 4 9
• Pour i←1 à 3 faire Défiler (F, V) Tête=4 File Vide,
Tête=Queue
Queue=4
0 1 2 3 4 9
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Tête=1 Queue=4
9 15 50
0 1 2 3 4 9
Tableau T
Définition de la structure :
TYPE File_Attente = STRUCTURE
T : TABLEAU[Max] de Typeqq;
Tête, Queue : ENTIER;
FIN.
VAR F : File_Attente;
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Modèle Implémentation
Procedure InitFile(Var F:File)
Debut
Initfile
F.Tête ←0; [Link] ←0;
Fin.
Fonction FileVide(F:File):Boolean
Debut
FileVide
Retourner (F.Tête = [Link]);
Fin.
Fonction FilePleine(F:File):Boolean
Debut
FilePleine
Retourner (F.Tête = ( ([Link] +1) Mod Max ));
Fin.
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Modèle Implémentation
Procedure Defiler(Var F:File, Var X: Entier)
Var I: Entier;
Debut
SI (NON FileVide(F)) FAIRE
Defiler X ← F.T[[Link]];
[Link] ← ([Link] + 1)Mod Max;
Fsi;
Fin.
IMPLÉMENTATION PAR UN TABLEAU CIRCULAIRE
Modèle Implémentation
Procedure Enfiler(Var F:File, X: Entier)
Debut
SI (NON FilePleine( F)) FAIRE
Enfiler [Link] ← ([Link] + 1) Mod Max;
F.T[[Link]] ← X;
Fsi;
Fin.