Cette page ne présente pas une nouvelle structure : elle compare les trois structures déjà vues dans les fiches listes, piles et files. Elle est utile en fin de révision, pour vérifier qu'on ne les confond pas.
Principe, en une phrase
Une liste est une suite ordonnée dont on peut lire ou modifier n'importe quel élément par son indice ; une pile n'autorise l'ajout et le retrait que d'un seul côté, en LIFO (dernier arrivé, premier sorti) ; une file impose que le premier élément ajouté soit toujours le premier retiré, en FIFO (premier arrivé, premier sorti).
1. Vocabulaire commun, rappelé rapidement
Mot
Définition précise
Indice
Le numéro qui repère un élément dans une liste, à partir de 0. Concept propre aux listes : une pile ou une file n'a pas d'indices, seulement un sommet ou une tête/queue.
LIFO
« Dernier arrivé, premier sorti » : le principe de fonctionnement d'une pile.
FIFO
« Premier arrivé, premier sorti » : le principe de fonctionnement d'une file.
Empiler / Dépiler
Ajouter / retirer un élément au sommet d'une pile.
Enfiler / Défiler
Ajouter un élément à la queue d'une file / retirer l'élément qui est à sa tête.
Structure de données abstraite
Une structure définie par les opérations qu'on peut faire dessus, sans imposer une seule façon de l'implémenter en mémoire. Une pile et une file sont deux structures abstraites différentes, même quand elles sont toutes les deux implémentées avec une liste Python.
2. Tableau de comparaison générale
Critère
Liste
Pile (LIFO)
File (FIFO)
Règle d'accès
n'importe quel élément, par son indice
seulement le sommet
seulement la tête (pour retirer), la queue (pour ajouter)
Où on ajoute
n'importe où (indice choisi)
au sommet
à la queue (à la fin)
Où on retire
n'importe où (indice choisi)
au sommet
à la tête (au début)
Exemple physique
un tableau de cases numérotées
une pile d'assiettes
une file d'attente
Ajouter, en Python
l.insert(i, x) ou l.append(x)
pile.append(x)
file.append(x)
Retirer, en Python
l.pop(i) ou l.remove(x)
pile.pop()
file.pop(0)
3. Le même scénario, appliqué à une pile et à une file
On applique exactement la même suite d'opérations à une pile et à une file, en partant à chaque fois d'une structure vide : ajouter Alice, Bob, puis Chloé ; retirer un élément ; ajouter David ; retirer deux éléments.
Étape
Opération
État de la pile (LIFO)
État de la file (FIFO)
0
départ
[]
[]
1
ajouter Alice
[Alice]
[Alice]
2
ajouter Bob
[Alice, Bob]
[Alice, Bob]
3
ajouter Chloé
[Alice, Bob, Chloé]
[Alice, Bob, Chloé]
4
retirer un élément
dépiler → Chloé ; reste [Alice, Bob]
défiler → Alice ; reste [Bob, Chloé]
5
ajouter David
[Alice, Bob, David]
[Bob, Chloé, David]
6
retirer un élément
dépiler → David ; reste [Alice, Bob]
défiler → Bob ; reste [Chloé, David]
7
retirer un élément
dépiler → Bob ; reste [Alice]
défiler → Chloé ; reste [David]
Résultat final de la pile
[Alice]
Résultat final de la file
[David]
La même suite d'opérations, deux résultats différents
Avec exactement les mêmes opérations, la pile et la file ne conservent pas la même personne : la pile conserve Alice, la toute première arrivée, car les derniers arrivés sont toujours retirés en premier (LIFO). La file conserve David, le tout dernier arrivé, car les premiers arrivés ont déjà tous été retirés (FIFO). C'est cette différence qu'il faut savoir expliquer à l'écrit.
Dans les deux cas, on part de la même méthode append(x) pour ajouter un élément : c'est le choix de la méthode utilisée pour retirer un élément (pop() ou pop(0)) qui distingue une pile d'une file.
5. Quelle structure choisir face à un exercice ?
Si l'énoncé demande d'accéder à un élément n'importe où, par sa position : c'est une liste.
Si l'énoncé impose que le dernier élément traité soit le premier ressorti (annuler une action, appels de fonctions récursives, vérifier des parenthèses) : c'est une pile (LIFO).
Si l'énoncé impose que les éléments soient traités exactement dans leur ordre d'arrivée (file d'attente, tâches à exécuter dans l'ordre) : c'est une file (FIFO).
Dans tous les cas, une pile ou une file s'implémente en pratique avec une liste Python : ce qui change, ce n'est pas la structure de données utilisée en mémoire, mais les seules opérations qu'on s'autorise à utiliser dessus.
6. Complexité récapitulative
Opération
Liste (position quelconque)
Pile (au sommet)
File (à la tête, avec une liste)
Ajouter
O(n), sauf à la fin : O(1)
O(1)
O(1) (l'ajout se fait toujours à la fin)
Retirer
O(n), sauf à la fin : O(1)
O(1)
O(n) à cause du décalage ; O(1) avec collections.deque
Accéder à un élément précis
O(1), par indice
seulement le sommet, O(1)
seulement la tête, O(1)
Rechercher une valeur
O(n)
non prévu par cette structure
non prévu par cette structure
7. Points clés à retenir
Une liste donne accès à n'importe quel élément par son indice ; une pile et une file ne donnent accès qu'à un seul élément à la fois (le sommet, ou la tête).
Pile = LIFO (dernier arrivé, premier sorti) ; file = FIFO (premier arrivé, premier sorti).
Avec une liste Python : append(x) sert à ajouter dans les deux cas ; pop() retire le dernier élément (pile), pop(0) retire le premier (file).
Dépiler est en O(1), mais défiler avec pop(0) est en O(n) à cause du décalage des éléments ; collections.deque corrige ce défaut pour les files.
Ces trois structures sont des structures de données abstraites : ce qui les distingue, ce sont les opérations autorisées, pas la façon dont elles sont stockées en mémoire.