Cette page suit toujours le même plan : le vocabulaire, un exemple concret, l'implémentation en Python, une démonstration interactive, le code Python, puis la complexité.
Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.
| Mot | Définition précise |
|---|---|
| File | Une structure linéaire dans laquelle on ajoute les éléments d'un côté (la queue) et on les retire de l'autre côté (la tête). |
| FIFO | « First In, First Out », c'est-à-dire « premier arrivé, premier sorti » : le principe de fonctionnement d'une file. Le premier élément ajouté est toujours le premier retiré. |
| Enfiler | Ajouter un élément à la queue de la file (c'est-à-dire à la fin). |
| Défiler | Retirer et renvoyer l'élément qui est à la tête de la file (c'est-à-dire le plus ancien). |
| Tête de file | L'élément le plus ancien de la file ; c'est celui qui sera retiré au prochain défilement. |
| Queue de la file | L'endroit où on ajoute les nouveaux éléments (ce n'est pas un élément, mais une position). |
| File vide | Une file qui ne contient aucun élément ; on ne peut pas défiler une file vide. |
| Structure de données abstraite | Une structure définie par les opérations qu'on peut faire dessus (ici enfiler et défiler), sans imposer une seule façon de l'implémenter en mémoire. |
On utilise une file d'attente à la caisse d'un magasin. Les clients arrivent dans cet ordre : Alice, puis Bob, puis Chloé. Le principe FIFO garantit qu'ils seront servis exactement dans cet ordre : Alice d'abord, car elle est arrivée en premier.
| Opération | Code Python | Effet |
|---|---|---|
| Créer une file vide | file = [] | une liste vide |
| Enfiler un élément (l'ajouter à la queue) | file.append(x) | x est ajouté à la fin de la liste |
| Défiler un élément (le retirer de la tête, et le renvoyer) | file.pop(0) | le premier élément de la liste est retiré et renvoyé |
| Regarder la tête sans la retirer | file[0] | le premier élément, sans modifier la file |
| Tester si la file est vide | file == [] | True ou False |
pop(0) et pas pop() ?file.pop(), sans indice, retire et renvoie le dernier élément de la liste : c'est le comportement d'une pile (LIFO), pas d'une file. Pour respecter le principe FIFO d'une file, il faut retirer le premier élément, donc écrire file.pop(0).
file = []file.append("Alice") # on enfile Alicefile.append("Bob") # on enfile Bobfile.append("Chloé") # on enfile Chloépremier = file.pop(0) # on défile : renvoie "Alice"file.append("David") # on enfile Davidsuivant = file.pop(0) # on défile : renvoie "Bob"dernier = file.pop(0) # on défile : renvoie "Chloé"
file.append(x) se fait en temps constant, O(1), quel que soit le nombre d'éléments déjà présents dans la file.file.pop(0) est plus coûteux : après avoir retiré le premier élément, Python doit décaler tous les éléments restants d'une case vers la gauche. Le coût est donc proportionnel au nombre d'éléments restants, soit O(n).collections.deque, qui permet de défiler en O(1) grâce à popleft() : from collections import deque, puis file = deque(), file.append(x) pour enfiler, file.popleft() pour défiler.append(x) (ajout à la fin) et on défile avec pop(0) (retrait au début).pop(0) coûte O(n) à cause du décalage des éléments restants ; collections.deque permet de défiler en O(1) avec popleft().