Structure linéaire de données : les files

file.md 2025-07-26

1 / 5

TP 3 : Structure linéaire de données : les files

Nous avons vu dans les TP précédents deux structures linéaires de données, les listes et les piles. Nous

allons aujourd'hui en voir une troisième : les files. Le type abstrait de données "file", comme nous allons le

voir ci-après, est une liste possédant des restrictions au niveau de lʼajout ou de la suppression de ces

éléments. En effet ces actions ne pourront être réalisées que selon certaines modalités.

I. Le TAD file

1) Le fonctionnement d'une file

Les files sont fondées sur le principe du "premier arrivé, premier sorti" : elles sont dites de type FIFO

(First In, First Out). Cʼest le principe de la file dʼattente devant un guichet.

Lʼinsertion dʼun élément dans une file sʼappelle une opération de mise en file "Enfiler" et la suppression

dʼun élément sʼappelle une opération de retrait de la file "Défiler". Dans la file, nous maintenons toujours

deux pointeurs, lʼun pointant sur lʼélément qui a été inséré en premier et qui est toujours présent dans la

liste avec le pointeur en avant et lʼautre pointant sur lʼélément inséré en dernier avec le pointeur arrière.

file.md 2025-07-26

2 / 5

En général, on utilise une file pour mémoriser temporairement des transactions qui doivent attendre

pour être traitées. Voici quelques exemples dʼapplications :

les serveurs dʼimpression, qui doivent traiter des requêtes dans lʼordre dans lequel elles arrivent, et

les insère dans une file dʼattente (ou une queue)

les requêtes entre machines sur un réseau

certains moteurs multi-tâches, dans un système dʼexploitation, qui doivent accorder du temps

machine à chaque tâche, sans en privilégier une plus quʼune autre

un algorithme de parcours en largeur (que nous verrons plus tard) utilise une file pour mémoriser les

nœuds visités

on utilise des files pour créer toutes sortes de mémoires tampons (buffers en anglais)

etc...

2) Comparaison pile vs file

Voici un tableau qui compare ces deux structures linéaires de données :

Pile File

Les objets sont insérés et supprimés à 1

seule extrémité Les objets sont insérés et retirés aux 2 extrémités.

Dans les piles, un seul pointeur est utilisé. Il

pointe vers le haut de la pile.

Dans les files, deux pointeurs différents sont utilisés

pour les extrémités : la tête et la fin.

Dans les piles, le dernier objet inséré est le

premier à sortir.

Dans les files, lʼobjet inséré en premier est le premier

qui sera supprimé.

Les piles suivent lʼordre Last In First Out

(LIFO) Les files suivent lʼordre First In First Out (FIFO)

Les opérations de pile sʼappellent Empiler et

Dépiler. Les opérations de file sont appelées Enfiler et Défiler.

file.md 2025-07-26

3 / 5

3) Les primitives du TAD file

Une file est une structure abstraite de données. Si lʼon reprend l'idée de la file d'attente les opérations

permises sont le suivantes :

on peut enfiler un élément (une personne arrive en queue de file)

on peut défiler un élément (la personne en début de file sort de la file).

on peut savoir si la file est vide ou non.

on peut afficher la longueur de la file (nombre de personnes la composant)

Voici résumé sous la forme dʼun tableau les opérations que l'on peut réaliser sur un objet de type File :

. Indiquez quelles seront les instructions dans lʼordre chronologique permettant de créer la file

12, 14, 8, 7, 19 et 22, lʼélément de tête

...