16 - type abstrait File FIFO
Nous avons vu la LISTE et la PILE, nous allons voir la FILE.
Documents de cours : open document ou pdf
Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)
1 - La File en tant que type abstrait de données
File, comme file d'attente en gros :
- on rajoute les éléments d'un côté MAIS
- on les extrait de l'autre.
1.1 - Définition du type abstrait de données FILE
Principe général d'organisation de la FILE : FIFO
Une File est un type abstrait de données ayant les propriétés suivantes :
- il s'agit d'une séquence finie et ordonnée de données (structure linéaire)
- on s'impose strictement de n'agir que sur les deux extrémités. On insère d'un côté et on supprime et lit de l'autre
- on insére un élément par l'entrée de la file qu'on nomme l'arrière. L'insertion se nomme l'enfilement
- on supprime l'élément du côté de la sortie de la file qu'on nomme l'avant. nomme le défilement
Un exemple de FILE : la colonne d'un puissance 4. Lorsqu'on lâche un jeton, il va se placer le plus près possible de la sortie (en bas) sans pouvoir dépasser les jetons déjà présents. Lorsqu'on va vouloir sortir les jetons, ils vont donc sortir dans le même ordre que l'ordre d'insertion.
On désigne également la pile sous l'acronyme FIFO pour First In First Out (à savoir), ou en français : Premier arrivé, premier parti..
Exemple
Trois façons de voir graphiquement une file où les éléments ont été insérés dans l'ordre chronologique suivant : 0 d'abord, puis 5, puis 10, et finalement 15.
Quatre versions équivalente en terme de
- Arrière à gauche, Avant à droite :
- Arrière à droite, Avant à gauche :
- Arrière en haut, Avant en bas :
- Arrière en bas, Arrière en haut :
Comme vous le voyez l'endroit où se trouve vraiment l'ARRIERE et l'AVANT importe peu. On peut aussi se représenter cela mentalement comme une file de personne.
1.2 - Fonctions primitives pour une FILE
Les fonction primitives définissent l'interaction basique qu'un utilisateur doit pouvoir effectuer avec les données si elles sont du type abstrait considéré.
Voici la description des fonctions primitives que les algorithmes vont pouvoir effectuer sur le type File.
- nouvelleFile() -> File : on crée une nouvelle file vide.
En anglais, cela pourrait donner newQueue(). - estFileVide(f:File) -> bool : prédicat qui renvoie True si la File p transmise est une File vide.
En anglais, cela pourrait donner isEmpty(). - enfiler(f:File, elt:Element) -> File : on renvoie une file en rajoutant l'élément elt à l'ARRIERE dans f.
En anglais, ça se nomme enqueue(). - defiler(f:File NON VIDE) -> File : on supprime l'élément à l'AVANT et renvoie la nouvelle File f.
En anglais, ça se nomme dequeue(). La fonction n'est pas définie si la file est vide. - lireAvant(p:File NON VIDE) -> Element : on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide.
En anglais, ça se nomme front().
Exemple de suppression / insertion
Partons de ceci :
Si on supprime un élément de la File, on obtient alors :
Si on supprime un élément de la File, on obtient alors :
Si on insère un élément 0 dans la File, on obtient alors :
1.3 - Différence fondamentale avec une Pile
Une File a deux extrémités (Arrire et Avant)
Une Pile n'a qu'une extrémité accessible, le Sommet
01° Fournir les contenus successifs de la pile f1 après exécution de chacune des instructions de l'algorithme suivant :
f1 ← nouvelleFile()
f1 ← enfiler(f1, 5)
f1 ← enfiler(f1, 7)
x ← lireAvant(f1)
f1 ← enfiler(f, x)
f1 ← enfiler(f, 4)
f1 ← defiler(f1)
...CORRECTION...
La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.
S'agissant de file, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.
f1 ← nouvelleFile()
La variable f1 est une file vide.
f1 ← enfiler(f, 5)
5 Avant et Arrière
f1 ← enfiler(f, 7)
7 Arrière / Back
5 Avant / Front
x ← lireAvant(p1)
7 Arrière / Back
5 Avant / Front
Aucun changement mais la variable x est affectée à la valeur 5.
p1 ← enfiler(f, x)
5 Arrière / Back
7
5 Avant / Front
p1 ← enfiler(f, 4)
4
5
7
5
p1 ← defiler(p1)
4
5
7
Attention, le 5 aura totalement disparu car on ne l'a pas stocké ailleurs.
02° On veut stocker séquentiellement 1 puis 2 puis 3 dans une file. Donner les instructions à utiliser et fournir la représentation finale de la File. Que va renvoyer la fonction lireAvant() ? La file est-elle modifiée après cette lecture ?
...CORRECTION...
f2 ← nouvelleFile()
f2 ← enfiler(f2, 1)
f2 ← enfiler(f2, 2)
f2 ← enfiler(f2, 3)
x ← lireAvant(f2)
Ceci donne :
3
2
1
La variable x va alors contenir la valeur 1.
D'après la description de la fonction lireAvant(), il n'y a pas modification de la file : il s'agit juste de lecture.
1.4 - Type mutable
Pour les implémentations qui utilisent une structure mutable, on trouve souvent les fonctions defiler() et lireAvant() regroupées dans une seule et même fonction qui va modifier la file sur place et qui renvoie l'élément de sortie avant qu'on vient de supprimer.
De même, la fonction enfiler() ne renvoie rien : elle modifie sur place le tableau par effet de bord.
Les prototypes de ces fonctions d'interface sont alors :
- enfiler(f:File, elt:Element) -> None : on rajoute un élément à l'arrière de la file en modifiant la file en place. On ne renvoie donc rien.
- defiler(f:File NON VIDE) -> Element : on supprime l'avant en modifiant la file en place et on renvoie l'élément qu'on vient de sortir de la file.
03° Fournir les contenus successifs de la File MUABLE f3 après exécution de chacune des instructions de l'algorithme suivant :
Attention, pensez à bien appliquer le nouveau prototype des fonctions : elles ne réagissent pas de la même façon que celles des questions 1 et 2 puisque nous travaillons avec une version mutable de pile.
f3 ← nouvelleFile()
enfiler(f3, 5)
enfiler(f3, 7)
x ← defiler(f3)
enfiler(f3, x)
enfiler(f3, 4)
defiler(f3)
...CORRECTION...
La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.
S'agissant de pile, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.
f3 ← nouvelleFile()
La variable f3 est une file vide.
enfiler(f3, 5)
5
enfiler(f3, 7)
7
5
x ← defiler(f3)
7
Cette fois, la fonction supprime l'avant et le renvoie, ce qui permet de le stocker dans la variable x qui est affectée à la valeur 5.
enfiler(f3, x)
5
7
enfiler(f3, 4)
4
5
7
defiler(f3)
4
5
Attention, ici on dépile mais on ne stocke pas le 7 : il a donc juste disparu à jamais.
1.5 - Fonctions optionnelles construites à partir des primitives
Les fonctions précédentes permettent de créer celles qui sont présentées ici. Selon les applications, nous en auront besoin ou pas, contrairement aux premières qui sont nécessaires pour manipuler les files.
- taille(f:File) -> int : on renvoie le nombre d'éléments dans la File. Cela peut être pratique pour éviter de dépasser la taile limite queue overflow en anglais).
- vider(f:File) -> File : on vide la file. Pour une file non-mutable, on renvoie donc une file vide. Cela peut être utile pour signaler qu'on se sépare d'éléments pourtant non traités (et qui ne le seront jamais).
En anglais, ça se nomme clear(). - mettreEnAttente(f:File) -> File : on défile le sommet et on enfile à nouveau la valeur dans la File.
Nous allons devoir utiliser certaines de ces fonctions pour résoudre l'exercice suivant.
04° Imaginer un algorithme permettant de gérer trois guichets f1, f2 et f3 d'un péage routier. Les clients font la queue physiquement et à partir d'un endroit un afficheur doit leur dire de se diriger vers un guichet particulier 1, 2 ou 3 en fonction de la file d'attente aux trois guichets.
Sur l'exemple, on voudrait que le véhicule à la première barrière soit envoyé vers le péage de haut : c'est celui avec le moins de monde pour l'instant.
Point important mais plein de subtilité
Comme pour la PILE, si vous avez à lire, modifier ou insérer régulièrement des éléments ailleurs qu'aux endroits prévus dans le cadre d'une FILE, c'est que vous utilisez le mauvais type abstrait.
S'il s'agit d'un détournement très occasionnel de la FILE, cela ne pose pas problème. Si c'est régulier, passez à la LISTE.
2 - Choix d'utilisation d'une file
05° Nous présentons ici plusieurs problèmes. Pour chacun des problèmes, dire si l'utilisation d'une file est adaptée, ou pas. Si la file n'est pas adaptée, expliquer le problème qu'on va rencontrer en résolvant le problème avec ce type de gestion.
A - Annulation des actions dans un logiciel.
On stocke les actions avec un enfilement. On utilise un défilement pour savoir ce qu'on doit annuler.
B - Réception et gestion des requêtes HTTP sur un serveur
La réception sera gérer par un enfilement. La gestion se fait progressivement avec un défilement.
C - Réception et gestion des demandes d'impression sur une imprimante partagée
La réception sera gérée par un enfilement. La gestion se fait progressivement avec un défilement.
D - Inversion des éléments d'un tableau
On stocke les éléments avec un enfilement en commençant par l'index 0. Une fois tout le tableau lu, on défile pour créer le nouveau tableau en commençant par l'index 0.
E - Classement des produits les plus vendus
On désire obtenir tous les mois une mise à jour des produits les plus vendus dans un magasin.
F - Gestion des clients arrivant dans un magasin
On place un client dans la file lorsqu'il rentre dans la boutique. On défile pour savoir qui servir.
G - Stockage des fonctions lors des appels
On stocke en mémoire les fonctions avec un enfilement lorsque le programme en a besoin. On défile lorsqu'elles répondent.
H - Questions et réponses d'un prof lors d'un cours
Les questions sont stockées avec un enfilement. La réponse à la question se fait progressivement avec un défilement.
I - Gestion des stocks
On enfile un produit lorsqu'il rentre en magasin. On doit le supprimer lorsqu'il sort.
3 - Types et structures linéaires
Choix de votre structure linéaire
Nous avons donc vu trois types abstraits linéaires :
- La LISTE qui permet de lire, d'insérer et supprimer n'importe quel élément à l'intérieur de la liste.
- Si on part sur une logique LIFO, on choisira une PILE. On insère et supprime uniquement sur l'une des extrémités.
- Si on part sur une logique FIFO, on choisira une FILE. On insère sur l'une des extrémités et on supprime sur l'autre.
4 - FAQ
Pas de question pour le moment
Activité publiée le 04 10 2020
Dernière modification : 25 10 2020
Auteur : ows. h.