Sommaire

Files

1. Principes de la file

a. Modèle de données file

La file est une liste qui stocke les éléments avec un ordre spécifique. C’est comme une file d’attente à la caisse d’un magasin. Les personnes arrivent une à une et constituent la file et elles partent une à une dans l’ordre d’arrivée après avoir payé. Il y a la personne en tête de file, la première et la personne en queue de file, la dernière. C’est l’ordre du premier arrivé premier sorti, "first in first out" dit FIFO en informatique :

images/06ri39.PNG

b. Implémentation statique ou dynamique

Une file est une liste particulière qui utilise les deux côtés début et fin à la différence d’une pile qui n’en utilise qu’un. L’implémentation peut se faire en dynamique avec des pointeurs ou en contigu avec un tableau.

Allocation dynamique de mémoire

Représentation d’une file en dynamique :

images/06ri40.PNG

Il est nécessaire d’avoir deux pointeurs pour une file : un pour gérer les entrées en queue et un pour gérer les sorties en tête. En dynamique une file n’a pas de taille limite, hormis celle de la mémoire centrale (RAM) disponible.

Allocation contiguë de mémoire

Représentation d’une file en contigu :

images/06ri41.png

La gestion d’une file en contigu est moins aisée qu’elle n’en a l’air au premier abord. ...