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.
FILE : on doit d'abord supprimer le jeton A avant de pouvoir accéder au jeton B. Si on rajoute un nouveau jeton, il va se placer en position E (Image dans le domaine public).
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 :
graph LR
I(("+"))-. insertion .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. suppression .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Arrière à droite, Avant à gauche :
graph RL
I(("+"))-. insertion .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. suppression .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Arrière en haut, Avant en bas :
graph TD
I(("+"))-. insertion .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. suppression .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Arrière en bas, Arrière en haut :
graph BT
I(("+"))-. insertion .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. suppression .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
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 Primitives d'une File
A (RAPPEL) Fonctions d'interface
Fonctions d'interface d'un module : en informatique, les fonctions d'interface caractérisent les fonctions qui sont utilisables par l'utilisateur d'un module.
B (RAPPEL) Primitives
Trois idées caractérisent ces fonctions particulières :
Les opérations primitives font partie des fonctions d'interface disponibles pour ce type abstrait de données.
Les opérations primitives sont les briques d'actions fondamentales permettant d'agir sur ce type de données.
Les futures implémentations des primitives devront avoir le coût le plus faible possible (se rapprochant d'un coût constant si possible).
C - Les primitives d'une File
nouvelleFile() -> File VIDE : 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 NON VIDE : 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(f: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().
Contrairement à la Liste, il n'y a pas de primitives liées au type intermédiaire Place : pas de fonctions acces(), successeur() ou contenu() nécessaires puisque l'utilisateur n'a le droit que d'accéder au sommet. On lui simplifie le travail en ne lui fournissant que les outils nécessaires à la gestion de ce type de structure.
Exemple de suppression / insertion
Partons de ceci :
graph LR
I(("+"))-. enfilement .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. défilement .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Si on supprime un élément de la File, on obtient alors :
graph LR
I(("+"))-. enfilement .-> D(Arrière 15) --> C[10] --> A(5 Avant) -. défilement .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Si on supprime un élément de la File, on obtient alors :
graph LR
I(("+"))-. enfilement .-> D(Arrière 15) --> A(10 Avant) -. défilement .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
Si on insère un élément 0 dans la File, on obtient alors :
graph LR
I(("+"))-. enfilement .-> D(Arrière 0) --> C[15] --> A(10 Avant) -. défilement .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
1.3 - Différence fondamentale avec une Pile
Une File a deux extrémités (Arrière et Avant)
graph LR
I(("+"))-. enfilement .-> D(Arrière 15) --> C[10] --> B[5] --> A(0 Avant) -. défilement .-> S(("-"))
style A fill:#f55,stroke:#333,stroke-width:2px
style D fill:#ff9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
Une Pile n'a qu'une extrémité accessible, le Sommet
graph LR
I(("+"))-. empilement -.-> D(Sommet 15) --> C[10] --> B[5] --> A(0)
S(("-"))-. dépilement -.- D
style A fill:#99f,stroke:#333,stroke-width:2px
style D fill:#fc9,stroke:#333,stroke-width:2px
style B fill:#99f,stroke:#333,stroke-width:2px
style C fill:#99f,stroke:#333,stroke-width:2px
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)
5Avant et Arrière
f1 ← enfiler(f, 7)
7Arrière / Back
5Avant / Front
x ← lireAvant(p1)
7Arrière / Back
5Avant / Front
Aucun changement mais la variable x est affectée à la valeur 5.
p1 ← enfiler(f, x)
5Arrière / Back
7
5Avant / 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 muable
Pour les implémentations qui utilisent une structure muable, 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 MUABLEf3 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 taille limite et provoquer une queue overflow.
vider(f:File) -> File : on vide la file. Pour une file immuable, 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 NON VIDE) -> File NON VIDE : on défile l'avant 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.
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.
