Files (queues)

1. Définition et principe fondamental

Une file est une structure de données linéaire, dynamique et ordonnée, dans laquelle les éléments sont manipulés selon une stratégie précise :

FIFO → First In, First Out
Cela signifie que le premier élément ajouté est le premier à être retiré.

C’est une organisation très courante dans les situations où l’ordre naturel d’arrivée doit être respecté.

2. Structure logique d’une file

On peut imaginer une file comme une file d’attente où :

Les éléments entrent par l’arrière (on enfile).

Les éléments sortent par l’avant (on défile).

Contrairement à une pile :

On ne retire jamais un élément autre que celui en tête de file (le plus ancien).

On ne peut pas accéder directement aux éléments situés au milieu.

On ne modifie que l’entrée (arrière) ou la sortie (avant).

3. Opérations fondamentales

Voici les trois opérations essentielles d’une file :

Opération	Description	Python (liste)
`enfiler(x)`	ajoute un élément à la fin	`file.append(x)`
`défiler()`	retire et retourne le premier élément	`file.pop(0)`
`est_vide()`	teste si la file est vide	`len(file) == 0`

4. Implémentation en Python

Création

file = []

Enfiler un élément

file.append("élément")

Ajoute un élément à la fin de la file, comme rejoindre une file d’attente.

Défiler un élément

premier = file.pop(0)

Retire et retourne l’élément en tête de la file, celui arrivé en premier.

❗ Attention : si la file est vide, pop(0) provoque une erreur. Il faut donc vérifier que la file n’est pas vide avant.

Tester si la file est vide

if len(file) == 0:
    print("file vide")

5. Contraintes importantes

Une file est une structure fermée : on ne peut pas accéder librement aux éléments internes.

On ne doit pas modifier un élément au milieu.

On respecte strictement l’ordre FIFO : premier arrivé, premier sorti.

La file est ordonnée dans l’ordre d’arrivée.

6. Avantages et intérêt algorithmique

La file permet de gérer des flux ou des séquences de manière ordonnée et juste.

Elle est très utile pour modéliser des systèmes où l’ordre d’attente est important.

Les files sont la base d’algorithmes fondamentaux comme le parcours en largeur (BFS).

7. Différence avec une pile

Structure	Ordre de sortie	Description
Pile	LIFO	Dernier arrivé, premier sorti
File	FIFO	Premier arrivé, premier sorti

8. Exemples d’utilisation

Gestion des tâches dans une imprimante

Traitement des requêtes sur un serveur

Parcours d’un graphe en largeur (BFS)

Simulation d’attente dans une file d’attente

9. Bonnes pratiques pour le bac

Toujours tester si la file est vide avant d’utiliser pop(0).

Ne jamais manipuler directement les éléments internes de la liste.

Comprendre la différence entre enfiler (ajout à la fin) et défiler (retrait au début).

Savoir traduire un algorithme en pseudo-code utilisant une file en Python simple.

📌 En résumé

Une file suit le modèle FIFO : on retire les éléments dans l’ordre exact de leur arrivée.

En Python, on utilise une liste avec append() pour enfiler et pop(0) pour défiler.

La file sert à gérer des situations où l’ordre naturel d’arrivée doit être respecté.

C’est une structure essentielle à connaître et à manipuler pour l’épreuve de NSI.