Les Files (Queues)
Notion de File (Queue)
◼ Les files sont très utilisées en informatique
◼ Notion intuitive :
File d'attente à un guichet, file de documents à imprimer, …
◼ Une file est une structure linéaire permettant de stocker et de
restaurer des données selon un ordre FIFO (First In, First Out
ou « premier entré, premier sorti »)
◼ Dans une file :
Les insertions (enfilements) se font à une extrémité appelée queue de
la file et les suppressions (défilements) se font à l'autre extrémité
appelée tête de la file
Exemple de File (1)
◼ Ajouter dans cet ordre A B C D E F
File
Exemple de File (2)
A B C D E F
File
Opérations sur une File
◼ file_vide : File file_vide()
opération d'initialisation ; la file créée est vide
◼ est_vide : int est_vide(File f)
teste si file vide ou non
◼ tête : Element tete(File f)
permet de consulter l'élément situé en tête de file ; n'a pas de
sens si file vide
◼ enfiler : File enfiler(File f, Element e)
ajoute un élément dans la file
◼ défiler : File defiler(File f)
enlève l'élément situé en tête de file ; n'a pas de sens si file vide
Représentation d'une File
◼ Représentation contiguë (par tableau) :
Les éléments de la file sont rangés dans un tableau
Deux entiers représentent respectivement les positions de la tête et
de la queue de la file
◼ Représentation chaînée (par pointeurs) :
Les éléments de la file sont chaînés entre eux
Un pointeur sur le premier élément désigne la file et représente la
tête de cette file
Un pointeur sur le dernier élément représente la queue de file
Une file vide est représentée par le pointeur NULL
Représentation Contiguë d'une File
(par tableau simple)
◼ tête de file : position précédant premier élément
◼ queue de file : position du dernier élément
◼ Initialisation : tête queue -1
◼ Inconvénient : on ne peut plus ajouter des
éléments dans la file, alors qu'elle n'est pas
pleine !
Représentation Contiguë d'une File
(par tableau simple) (1)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab tab 5 2 10 20 30 40 50
tete -1 tete -1
File initialement vide de taille File après ajout de 5, 2, 10, 20,
queue -1 maximale = 10 queue 6 30, 40 et 50
(1) (2)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab 10 20 30 40 50 tab
tete 1 tete 6
File après suppression de 5 et 2 File après suppression de 10,
queue 6 queue 6 20, 30, 40 et 50
(3) (4)
Représentation Contiguë d'une File
(par tableau simple) (2)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab tab 5 15 10
tete 6 tete 6
File après ajout de
queue 6 queue 9 5, 15 et 10
File vide
(5) (6)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab 10 tab 10
tete 8 tete 8
File après suppression 5 et On ne peut plus ajouter dans
queue 9 15 queue 9 la file !!
(7) (8)
File Contiguë
File
0 1 2 3 4 5 6 7 8 9
tab 10 20 30 40 50
tete 1
queue 6 Tableau de taille
maximale 10
Position qui précède le premier
élément de la file
Position du dernier élément de la
file
Réalisation d'une File Contiguë
Représentation Contiguë d'une File
(par tableau simple avec décalage)
◼ Décaler les éléments de la file après chaque
suppression
◼ Inconvénient : décalage très coûteux si la file
contient beaucoup d'éléments
Représentation Contiguë d'une File
(par tableau simple avec décalage) (1)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab tab 5 2 10 20 30 40 50
tete -1 tete -1
File initialement vide de taille File après ajout de 5, 2, 10, 20,
queue -1 maximale = 10 queue 6 30, 40 et 50
(1) (2)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab 10 20 30 40 50 tab
tete -1 tete -1
File après suppression de 5 et 2 File après suppression de 10,
queue 4 queue -1 20, 30, 40 et 50
(3) (4)
Représentation Contiguë d'une File
(par tableau simple avec décalage) (2)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab tab 5 15 10
tete -1 tete -1
File après ajout de
queue -1 queue 2 5, 15 et 10
File vide
(5) (6)
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
tab 10 tab 10 5 6 20 8 35 25 33 4 80
tete -1 tete -1
Après ajout de 5, 6, 20, 8, 35, 25,
File après suppression 5 et
queue 0 15 queue 9 33, 4 et 80, File pleine!!
(7) (8)
File chaînée
File Tête de la file pointée
par tete Pointeur
NULL
Cellule contenant la
valeur 30
10 20 30 50 NULL
tete
Queue de file pointée par
queue queue
File Chaînée
Une cellule contient un
élément et un pointeur sur
l'élément suivant
Type File : structure à deux
champs (pointeurs de tête et de
queue de file)
Réalisation d'une File Chaînée
Applications d'une File
Exemples
◼ Gestion des travaux d’impression d’une imprimante :
Cas 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
◼ Ordonnanceur (dans les systèmes d’exploitation) :
Maintenir une file de processus en attente d’un temps machine ;
◼ Parcours « en largeur » d’un arbre
