Stack (pile)
Dernière mise à jour
Une pile est une collection avec exactement une extrémité ouverte. Vous ajoutez une valeur en l'empilant au sommet, et vous en retirez une en dépilant ce même sommet : la dernière valeur entrée est donc toujours la première sortie. C'est ce que veut dire LIFO, et c'est toute la règle : impossible d'atteindre le milieu sans retirer d'abord ce qui se trouve au-dessus. Lancez la lecture ci-dessus et regardez la colonne grandir à chaque push et se réduire par cette même extrémité à chaque pop.
La contrainte est justement l'intérêt. Comme les deux opérations ne touchent que le sommet, chacune est en O(1) quelle que soit la hauteur de la pile, et c'est cette prévisibilité qui place les piles sous une grande partie de l'informatique : la pile d'appels qui exécute la récursivité, l'historique d'annulation d'un éditeur, l'appariement des parenthèses dans un analyseur syntaxique, et la pile explicite qui transforme un parcours en profondeur récursif en boucle. Changez l'extrémité de retrait et vous obtenez une Queue (file).
Complexité en temps et en espace
Pour la pile classique fondée sur un tableau ou sur une liste chaînée :
| Opération | Complexité | Remarques |
|---|---|---|
| Push | O(1) | O(1) amorti sur un tableau dynamique, qui se redimensionne de temps en temps. |
| Pop | O(1) | Toujours l'élément du sommet, aucun décalage n'est nécessaire. |
| Peek (sommet) | O(1) | Lit le sommet sans le retirer. |
| Recherche | O(n) | Ce n'est pas le rôle d'une pile : il faut dépiler jusqu'à l'élément voulu. |
| Espace | O(n) | Un emplacement par valeur stockée. |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | La pile démarre vide, le sommet ne pointant sur rien. |
| 2 | Push écrit la valeur à la position du sommet et remonte le sommet d'un cran. |
| 3 | Chaque push suivant se pose directement au-dessus de la valeur précédente. |
| 4 | Pop lit la valeur au sommet, puis redescend le sommet d'un cran. |
| 5 | La valeur renvoyée est toujours la plus récemment empilée. |
| 6 | Dépiler une pile vide est une erreur, appelée sous-dépassement de pile (stack underflow), c'est pourquoi le vrai code teste is_empty() d'abord. |
Exemple détaillé
Empilement de 3, 7, 5 puis vidage de la pile :
| Opération | Pile (de bas en haut) | Renvoie |
|---|---|---|
push(3) | [3] | rien |
push(7) | [3, 7] | rien |
push(5) | [3, 7, 5] | rien |
pop() | [3, 7] | 5, la valeur la plus récente |
pop() | [3] | 7 |
pop() | [] | 3, la plus ancienne, en dernier |
Quand utiliser une pile
| À utiliser quand | À éviter quand |
|---|---|
| Vous voulez récupérer d'abord l'élément le plus récent : annulation, boutons retour, appariement de parenthèses | Vous voulez d'abord l'élément le plus ancien, ce qui est une Queue (file) |
| Vous transformez un algorithme récursif en algorithme itératif | Vous devez chercher ou indexer au milieu des données |
| Vous analysez une structure imbriquée comme des expressions, du JSON ou du HTML | De nombreux lecteurs ont besoin d'un accès arbitraire, où un tableau ou une table associative convient mieux |
Vous voulez une insertion et un retrait O(1) garantis, sans rééquilibrage | Vous devez garder les données triées, ce que vous donne un tas ou un arbre |
Code de Stack
Une implémentation propre et exécutable de Stack en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Stack en Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Code de Stack en JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Code de Stack en Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Code de Stack en C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Code de Stack en C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}FAQ sur la pile
Que signifie LIFO ?
Last in, first out, dernier entré, premier sorti : la valeur empilée en dernier est la première dépilée. La pile d'assiettes est l'image habituelle : vous prenez l'assiette que vous venez de poser, pas celle du bas. Une Queue (file) suit la discipline inverse, FIFO.
Quelle est la différence entre une pile et une file ?
Uniquement l'extrémité par laquelle vous retirez. Les deux ajoutent par une extrémité en
O(1) ; une pile retire par cette même extrémité (LIFO), une file retire par l'autre (FIFO). Tout le reste, y compris le tableau de complexité ci-dessus, est identique.Quelles sont les principales opérations d'une pile ?
push ajoute une valeur au sommet, pop retire et renvoie la valeur du sommet, peek (parfois top) lit le sommet sans le retirer, et is_empty indique s'il reste quelque chose. Les quatre sont en O(1).Qu'est-ce qu'un débordement de pile (stack overflow) ?
C'est empiler sur une pile qui n'a plus de place. Le cas célèbre est la pile d'appels : chaque appel de fonction empile un cadre, donc une récursivité qui n'atteint jamais son cas de base continue d'empiler jusqu'à la limite de pile de l'environnement d'exécution, et le programme plante. L'erreur miroir, dépiler une pile vide, est un sous-dépassement de pile.
Comment une pile est-elle implémentée ?
Deux façons courantes. Un tableau dynamique empile et dépile en fin de tableau, ce qui est
O(1) amorti et favorable au cache : list de Python et ArrayDeque de Java fonctionnent ainsi. Une liste chaînée empile et dépile en tête, O(1) au pire cas et sans redimensionnement, mais coûte un pointeur par élément. std::stack de C++ est un adaptateur qui repose par défaut sur std::deque, un tableau segmenté, et accepte un autre conteneur si vous en passez un.Où les piles sont-elles utilisées dans les vrais programmes ?
La pile d'appels pour les appels de fonction et la récursivité, l'historique d'annulation et de rétablissement, la navigation arrière du navigateur, l'évaluation d'expressions et l'appariement de parenthèses dans les analyseurs syntaxiques, et la pile explicite qui convertit un parcours en profondeur récursif en boucle itérative.
Ressources associées
Plus de visualisations
