Cette page suit toujours le même plan : le vocabulaire, un exemple concret, l'implémentation en Python, une démonstration interactive, le code Python, puis la complexité.
Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.
| Mot | Définition précise |
|---|---|
| Pile | Une structure linéaire dans laquelle on ajoute et on retire les éléments toujours du même côté, appelé le sommet. |
| LIFO | « Last In, First Out », c'est-à-dire « dernier arrivé, premier sorti » : le principe de fonctionnement d'une pile. Le dernier élément ajouté est toujours le premier retiré. |
| Empiler | Ajouter un élément sur le sommet de la pile. |
| Dépiler | Retirer et renvoyer l'élément qui est au sommet de la pile (c'est-à-dire le dernier ajouté). |
| Sommet de la pile | L'élément le plus récent de la pile ; c'est celui qui sera retiré au prochain dépilement. |
| Pile vide | Une pile qui ne contient aucun élément ; on ne peut pas dépiler une pile vide. |
| Structure de données abstraite | Une structure définie par les opérations qu'on peut faire dessus (ici empiler et dépiler), sans imposer une seule façon de l'implémenter en mémoire. |
On utilise une pile de dossiers posés sur un bureau, un par-dessus l'autre. On empile le dossier d'Alice, puis celui de Bob, puis celui de Chloé, dans cet ordre : le dossier d'Alice se retrouve donc tout en bas de la pile, et celui de Chloé tout en haut. Le principe LIFO impose de toujours traiter en premier le dossier du dessus, c'est-à-dire le dernier posé.
| Opération | Code Python | Effet |
|---|---|---|
| Créer une pile vide | pile = [] | une liste vide |
| Empiler un élément (le poser sur le sommet) | pile.append(x) | x est ajouté à la fin de la liste |
| Dépiler un élément (le retirer du sommet, et le renvoyer) | pile.pop() | le dernier élément de la liste est retiré et renvoyé |
| Regarder le sommet sans le retirer | pile[-1] | le dernier élément, sans modifier la pile |
| Tester si la pile est vide | pile == [] | True ou False |
pop() sans indice, et pas pop(0) ?pile.pop(), sans indice, retire et renvoie le dernier élément ajouté à la liste, c'est-à-dire le sommet de la pile : c'est bien le comportement LIFO attendu. pile.pop(0) retirerait le premier élément ajouté, ce qui correspondrait au fonctionnement d'une file (FIFO), pas d'une pile.
pile = []pile.append("Alice") # on empile le dossier d'Alicepile.append("Bob") # on empile le dossier de Bobpile.append("Chloé") # on empile le dossier de Chloédernier = pile.pop() # on dépile : renvoie "Chloé"pile.append("David") # on empile le dossier de Davidsuivant = pile.pop() # on dépile : renvoie "David"encore = pile.pop() # on dépile : renvoie "Bob"
pile.append(x) se fait en temps constant, O(1), quel que soit le nombre d'éléments déjà présents dans la pile.pile.pop() est également en O(1) : retirer le dernier élément d'une liste Python ne demande aucun décalage des autres éléments, contrairement à pop(0).collections.deque.append(x) et on dépile avec pop() (sans indice).collections.deque.