Définition et opérations fondamentales des files (Queues)

Bonjour ! Bienvenue dans cette nouvelle leçon.

Introduction

Dans la leçon précédente, nous avons exploré en détail la structure de données de la pile, régie par le principe LIFO (Dernier Arrivé, Premier Sorti). Nous avons vu comment l'utiliser pour résoudre un problème concret : l'inversion d'une chaîne de caractères.

Aujourd'hui, nous allons découvrir une autre structure de données linéaire tout aussi fondamentale : la file (queue en anglais). Son principe de fonctionnement est l'exact opposé de celui de la pile. L'objectif de cette leçon est de vous amener à définir le concept de file, comprendre son principe FIFO (Premier Arrivé, Premier Sorti), et maîtriser ses opérations fondamentales : enfiler et défiler. Cette nouvelle structure est un outil essentiel dans la boîte à outils de tout développeur pour gérer des données de manière ordonnée.

1. Le concept de File et le principe FIFO

Imaginez une file d'attente au guichet d'un cinéma ou à la caisse d'un supermarché. La première personne qui arrive dans la file est la première à être servie et à en sortir. C'est le principe fondamental qui régit la structure de données que nous appelons une file.

En algorithmique, ce principe est connu sous l'acronyme FIFO : First-In, First-Out, ou en français, Premier Arrivé, Premier Sorti (PAPS).

C'est la différence majeure avec la pile que nous avons vue, qui fonctionne sur le principe LIFO (Dernier Arrivé, Premier Sorti), comme une pile d'assiettes.

Pour approfondir cette définition et voir comment on peut se représenter une file, je vous invite à lire la première partie de la ressource suivante.

16 - type abstrait File FIFO

L'article "type abstrait File FIFO" de Infoforall.fr introduit de manière claire le concept de file, son principe FIFO, et propose plusieurs schémas pour visualiser cette structure.

Lisez la section intitulée "1 - La File en tant que type abstrait de données", jusqu'à la sous-partie "1.2 Primitives d'une File". Concentrez-vous sur la définition du principe FIFO et les différentes manières de représenter graphiquement une file.

2. Les opérations fondamentales d'une File

Comme pour la pile, nous interagissons avec une file à l'aide d'un ensemble d'opérations de base, qu'on appelle aussi des primitives. Une file possède deux "extrémités" :

L'arrière (ou la queue), où l'on ajoute les nouveaux éléments.
L'avant (ou la tête), d'où l'on retire les éléments.

Les opérations fondamentales sont :

Enfiler (ou enqueue en anglais) : C'est l'action d'ajouter un élément à l'arrière de la file.
Défiler (ou dequeue en anglais) : C'est l'action de retirer l'élément qui se trouve à l'avant de la file.

À ces deux opérations principales s'ajoutent quelques fonctions utilitaires essentielles :

nouvelleFile() : Crée une file vide.
estFileVide() : Vérifie si la file est vide (renvoie Vrai ou Faux).
lireAvant() (ou front) : Permet de consulter l'élément à l'avant de la file sans le retirer.

La ressource suivante détaille chacune de ces primitives.

16 - type abstrait File FIFO

Continuons avec le même document qui liste et décrit les primitives d'une file de manière très structurée.

Lisez la section "1.2 Primitives d'une File". Prenez note de chaque primitive, de ce qu'elle fait, et de son nom équivalent en anglais, car vous les rencontrerez souvent.

L'image ci-dessous illustre parfaitement le déroulement des opérations enfiler et défiler.

Illustration des Opérations Enfiler et Défiler dans une File (Queue) — Cette image montre la dynamique d'une file. En haut, l'élément 'd' est ajouté à l'arrière (Entrée) de la file via l'opération `enfiler`. Au centre, la file contient les éléments 'd', 'c', 'b', 'a'. En bas, l'élément 'a', qui était le premier entré, est retiré de l'avant (Sortie) via l'opération `défiler`, respectant ainsi l'ordre FIFO.

3. Exercice pratique : Tracer l'exécution d'un algorithme

Votre préférence allant à la pratique, le meilleur moyen de solidifier votre compréhension est de tracer manuellement l'état d'une file au fil des opérations.

Considérez l'algorithme suivant :

VARIABLES
    f1 : File
    x : Entier

DEBUT
    f1 ← nouvelleFile()
    enfiler(f1, 5)
    enfiler(f1, 7)
    x ← lireAvant(f1)
    enfiler(f1, x)
    enfiler(f1, 4)
    defiler(f1)
FIN

Votre tâche :
Prenez une feuille de papier et tracez l'état de la file f1 et la valeur de la variable x après l'exécution de chaque instruction. Représentez la file verticalement, avec l'avant en bas et l'arrière en haut, comme dans une file d'attente.

Correction de l'exercice

Une fois que vous avez terminé, comparez votre travail avec la solution détaillée ci-dessous.

f1 ← nouvelleFile()
- f1 est une file vide.
- Représentation : []
enfiler(f1, 5)
- On ajoute 5. Il est à la fois à l'avant et à l'arrière.
- Représentation f1 :
```
[ 5 ] ← Arrière / Avant
```
enfiler(f1, 7)
- On ajoute 7 à l'arrière. 5 reste à l'avant.
- Représentation f1 :
```
[ 7 ] ← Arrière
[ 5 ] ← Avant
```
x ← lireAvant(f1)
- On lit l'élément à l'avant sans le retirer.
- La file f1 ne change pas.
- La variable x prend la valeur 5.
- Représentation f1 :
```
[ 7 ] ← Arrière
[ 5 ] ← Avant
```
- x: 5
enfiler(f1, x)
- On ajoute la valeur de x (c'est-à-dire 5) à l'arrière.
- Représentation f1 :
```
[ 5 ] ← Arrière
[ 7 ]
[ 5 ] ← Avant
```
enfiler(f1, 4)
- On ajoute 4 à l'arrière.
- Représentation f1 :
```
[ 4 ] ← Arrière
[ 5 ]
[ 7 ]
[ 5 ] ← Avant
```
defiler(f1)
- On retire l'élément à l'avant de la file, qui est 5. L'élément suivant (7) devient le nouvel avant.
- Représentation finale de f1 :
```
[ 4 ] ← Arrière
[ 5 ]
[ 7 ] ← Avant
```

Cet exercice simple met en évidence comment la file préserve l'ordre d'insertion, contrairement à la pile où l'ordre est inversé.

Conclusion

Félicitations ! Vous venez d'ajouter une nouvelle structure de données fondamentale à votre arsenal.

Les points clés à retenir :

Une File (Queue) est une structure de données linéaire basée sur le principe FIFO (First-In, First-Out) : Premier Arrivé, Premier Sorti.
Elle fonctionne comme une file d'attente : les éléments sont ajoutés à l'arrière et retirés de l'avant.
Les opérations fondamentales sont enfiler (ajouter à l'arrière) et défiler (retirer de l'avant).
La différence avec une Pile (LIFO) est cruciale : la pile inverse l'ordre des éléments, tandis que la file le conserve.

Et après ?

Maintenant que vous comprenez le concept de file et ses opérations, la prochaine étape logique est de l'utiliser pour résoudre un problème. Dans la prochaine leçon, nous utiliserons une file pour simuler un scénario simple de file d'attente. Ce sera une excellente occasion de mettre en pratique ce que vous venez d'apprendre dans un contexte très concret et intuitif.

Recommended resources