Algorithmes Python

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).

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

De la pile d'assiettes au code
stack.append("third")🍽️ Poser une assiette sur le dessus
stack.pop()⬆️ Retirer l'assiette du dessus
stack[-1]👀 Regarder l'assiette du dessus sans la prendre
stack📚 Les assiettes encore sur la pile
Dernier entré, premier sorti : seul le dessus est accessible.
En une phrase

Une pile est une collection LIFO (dernier entré, premier sorti) : les éléments sont ajoutés et retirés uniquement au sommet.

Points clés

  1. stack.append(...) empile un élément au sommet, c'est-à-dire à la fin de la liste.
  2. stack.pop() retire et renvoie l'élément du sommet, ici "third".
  3. stack[-1] lit l'élément du sommet sans le retirer.
  4. append et pop travaillent 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

Exécuter le code →
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")

print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Dépiler une pile vide

pop() sur une liste vide lève une IndexError.

Problème
item = stack.pop()
Correction
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.

Problème
stack.insert(0, item)
stack.pop(0)
Correction
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.

Tous les défis