La pile (LIFO)

La pile : empiler et dépiler

Le principe LIFO

Une pile (en anglais stack) est une structure de données où le dernier élément ajouté est toujours le premier à en sortir. On appelle ce principe LIFO, pour « Last In, First Out » (dernier entré, premier sorti). Imagine une pile d'assiettes : tu poses toujours la nouvelle assiette sur le dessus, et quand tu en retires une, tu prends forcément celle du dessus, jamais celle du fond.

Les deux opérations de base

Une pile ne propose que deux opérations essentielles :

empiler (push) : ajouter un élément au sommet de la pile ;
dépiler (pop) : retirer et renvoyer l'élément au sommet de la pile.

On y ajoute souvent une opération sommet (peek), qui regarde l'élément du dessus sans le retirer, et un test est_vide.

Schéma : évolution d'une pile

Pile vide :                 []

empiler(3)  ->               [3]
empiler(7)  ->               [3, 7]
empiler(9)  ->               [3, 7, 9]        (9 est au sommet)

depiler() -> 9                [3, 7]          (9 sort en premier, il était le dernier entré)
depiler() -> 7                [3]

vue verticale :
   +---+
   | 9 |   (sommet, dernier arrivé)
   +---+
   | 7 |
   +---+
   | 3 |   (base, premier arrivé)
   +---+

Ordre inverse garanti

Ce qui rend la pile utile, c'est que l'ordre de sortie est toujours l'inverse exact de l'ordre d'entrée. Si tu empiles 3, puis 7, puis 9, tu es certain de récupérer 9 en premier, puis 7, puis 3 en dernier.

Piège classique