Les piles : comprendre le fonctionnement LIFO

Une seule extrémité accessible

Une pile est une structure linéaire dont les ajouts et retraits se font au même endroit, appelé sommet. Empiler ajoute un élément au sommet. Dépiler retire et renvoie celui qui s’y trouve. Le dernier élément entré est donc le premier sorti : Last In, First Out, ou LIFO.

L’interface comporte aussi un test de vacuité et éventuellement une consultation du sommet sans retrait. Une pile vide ne possède pas de sommet. Le contrat doit préciser ce qui arrive lors d’un retrait à vide : précondition à respecter ou erreur documentée. Renvoyer arbitrairement zéro serait ambigu si zéro est une donnée possible.

LIFO exprime une contrainte sur l’ordre des opérations observables. Une pile peut être dessinée verticalement ou horizontalement, et son sommet peut être placé à gauche ou à droite. Ce qui compte est que l’élément ajouté le plus récemment parmi ceux encore présents soit le prochain retiré. Le contrat ne demande ni un tri des valeurs, ni la conservation d’un ordre d’arrivée à la sortie.

Une réalisation simple en Python

Une liste Python peut représenter une pile dont le sommet est à droite. append empile et pop() dépile le dernier élément. Si l’on adopte une autre convention graphique, il faut l’annoncer. Le sens LIFO dépend des opérations, pas de la manière dont le dessin est orienté sur la page.

Empiler A, B puis C donne [A, B, C], avec C au sommet. Deux dépilements renvoient C puis B et laissent [A]. Consulter A ne le retire pas. Une trace utile sépare donc les valeurs renvoyées du contenu encore conservé dans la pile.

pile = []
pile.append("A")
pile.append("B")
pile.append("C")
dernier = pile.pop()  # "C"
sommet = pile[-1]    # "B", toujours présent

Vérifier un emboîtement de délimiteurs

Pour vérifier des parenthèses, crochets et accolades, on lit le texte de gauche à droite. Une ouverture est empilée. À la rencontre d’une fermeture, la pile doit être non vide et son sommet doit être l’ouverture correspondante. On la dépile alors. À la fin, la pile doit être vide.

L’expression ([ ]) est correcte : le crochet, ouvert le plus récemment, se ferme avant la parenthèse. En revanche ([)] est incorrecte, même si chaque type possède autant d’ouvertures que de fermetures. Compter ne vérifie pas l’ordre d’imbrication ; la pile le mémorise.

Le contenu de la pile est un résumé du préfixe déjà lu : il contient les ouvertures qui attendent encore leur fermeture, dans leur ordre d’apparition. Le sommet est donc la dernière ouverture non refermée. Cette propriété explique le bon choix de structure et permet de justifier l’algorithme, au-delà de la simple analogie avec une pile d’assiettes.

Trois erreurs différentes à diagnostiquer

Une fermeture sur pile vide signifie qu’aucune ouverture ne lui correspond. Une fermeture incompatible avec le sommet révèle un mauvais emboîtement. Une pile encore remplie à la fin indique des ouvertures jamais refermées. Ces diagnostics aident à comprendre un échec au lieu d’afficher seulement « faux ».

Chaque caractère est lu une fois et chaque délimiteur est empilé puis éventuellement dépilé. Le coût du parcours est linéaire dans ce modèle. La mémoire nécessaire dépend du nombre maximal d’ouvertures simultanément en attente. L’atelier ignore les autres caractères : il illustre l’emboîtement, sans analyser toute la syntaxe d’un langage.

Exemple suivi : distinguer trois diagnostics

Pour ([{}]), les trois premières lectures empilent parenthèse, crochet, accolade. Le sommet est alors l’accolade ; les trois fermetures dépilent dans l’ordre inverse. La pile finale est vide et le texte est correct. Sa profondeur maximale est trois, même si la taille finale vaut zéro.

Pour ([)], le premier échec arrive à l’indice 2 : la fermeture de parenthèse rencontre un crochet au sommet. Pour ()), la dernière fermeture rencontre une pile vide. Pour ((), aucune fermeture ne provoque d’erreur, mais une ouverture reste à la fin. Ces diagnostics ne se corrigent pas de la même façon. Un bon vérificateur doit donc distinguer incompatibilité, fermeture sans ouverture et ouverture restant en attente.

Transférer l’idée à une fonction annuler

Une application simplifiée mémorise dans une pile les opérations réversibles effectuées : écrire A, écrire B, écrire C. Annuler retire la plus récente, donc C, puis B au prochain appel. Cette discipline correspond au besoin de revenir en arrière dans l’ordre inverse de construction. Une file ferait annuler A d’abord et ne suivrait pas ce contrat.

Pour un exercice autonome, précisez ce qu’une opération enregistre et comment elle s’inverse. Une pile de lettres suffit à modéliser l’ajout de caractères, mais ne décrit pas toutes les possibilités d’un traitement de texte. Si une fonction rétablir est ajoutée, une seconde pile peut mémoriser les opérations annulées ; ses règles doivent être spécifiées, notamment lorsqu’une nouvelle modification arrive. L’intérêt de la structure provient des opérations attendues, pas du nom de l’application.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Dépiler pour simplement regarder le sommet.

Consulter doit laisser la structure intacte. Un retrait modifie l’état et peut faire disparaître une information nécessaire.

Tester seulement le nombre d’ouvertures et de fermetures.

L’ordre et le type des délimiteurs comptent aussi ; une pile mémorise les ouvertures en attente.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Asie · Jour 2 : Taquin : déplacements légaux et résolution par historique
• Bac 2025 · Asie · Jour 1 - Remplacement : Pseudo-tri dictatorial : listes, maillons et piles
• Bac 2025 · Polynésie · Jour 2 : Transformer des mots avec un parcours en largeur

Le prochain pas

• Les files : comprendre le fonctionnement FIFO
• La récursivité : comprendre les appels et les résultats
• Parcourir un graphe en profondeur : DFS

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.