La structure de données pile (stack) en Python
Dans cette leçon, vous allez utiliser une liste Python pour implémenter les opérations de base d'une pile : empiler (push), dépiler (pop) et consulter le sommet (peek).
Introduction
Le problème
Les boutons annuler, le bouton retour d'un navigateur et la vérification des parenthèses ont tous besoin de retenir des éléments et de reprendre d'abord le plus récent. Une pile est la structure de données faite exactement pour cela.
Imaginez-le ainsi
Une pile est comme une pile d'assiettes à la cantine. Vous posez les nouvelles assiettes sur le dessus et prenez celles du dessus. La dernière assiette ajoutée est la première utilisée, et vous ne pouvez pas tirer une assiette du milieu.
stack.append("third")🍽️ Poser une assiette sur le dessusstack.pop()⬆️ Retirer l'assiette du dessusstack[-1]👀 Regarder l'assiette du dessus sans la prendrestack📚 Les assiettes encore sur la pileUne pile est une collection LIFO (dernier entré, premier sorti) : les éléments sont ajoutés et retirés uniquement au sommet.
Points clés
stack.append(...)empile un élément au sommet, c'est-à-dire à la fin de la liste.stack.pop()retire et renvoie l'élément du sommet, ici"third".stack[-1]lit l'élément du sommet sans le retirer.appendetpoptravaillent tous deux à la fin de la liste, donc ils sont rapides.
Quand l’utiliser ?
- Les historiques annuler et rétablir.
- Vérifier la correspondance des parenthèses et analyser des expressions.
- Le parcours en profondeur et le retour arrière sans récursion.
Quand s'en passer
- Les éléments doivent sortir dans leur ordre d'arrivée : c'est une file.
- Vous avez besoin d'éléments du milieu ou par position : une liste normale ou une autre structure convient mieux.
Voir comment ça marche
Faites push et pop pour voir que le dernier élément entré est toujours le premier à sortir.
Code d’exemple
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Résultat de l’exécution
popped: third
top: second
stack: ['first', 'second']
Explication du code
La méthode append() ajoute un élément au sommet de la pile, et pop() retire et renvoie l'élément du sommet, c'est pourquoi "third" sort en premier. stack[-1] permet de consulter le sommet sans le retirer. Les opérations append() et pop() en fin de liste ont une complexité moyenne de O(1).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Dépiler une pile vide
pop() sur une liste vide lève une IndexError.
item = stack.pop()
if stack:
item = stack.pop()
Utiliser le début de la liste comme sommet
insert(0, x) et pop(0) déplacent chaque élément, ce qui est lent.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Moyen
- Mini Stack-Language Interpreter Evaluate a small stack language. Difficile