Accueil › Coding & algorithmique › La pile : parenthèses, historique et pile monotone
La pile : parenthèses, historique et pile monotone
Piles, files et tasavance
La pile sert dès qu'il y a imbrication ou qu'il faut revenir en arrière.
Deque<Character> pile = new ArrayDeque<>(); // jamais Stack
pile.push(c);
pile.pop();
pile.peek();
pile.isEmpty();
Motif 1 — appariement :
static boolean equilibre(String s) {
Map<Character, Character> paires = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> pile = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (paires.containsValue(c)) pile.push(c);
else if (paires.containsKey(c)) {
if (pile.isEmpty() || pile.pop() != paires.get(c)) return false;
}
}
return pile.isEmpty(); // ← ne pas oublier : « ((( » n'est pas équilibré
}
Un simple compteur suffirait pour un seul type de parenthèse — mais échouerait sur ([)]. C'est le contre-exemple à donner.
Motif 2 — pile monotone, pour « le prochain élément plus grand » :
static int[] prochainPlusGrand(int[] t) {
int[] r = new int[t.length];
Arrays.fill(r, -1);
Deque<Integer> pile = new ArrayDeque<>(); // on empile les INDEX
for (int i = 0; i < t.length; i++) {
while (!pile.isEmpty() && t[pile.peek()] < t[i])
r[pile.pop()] = t[i]; // i est le prochain plus grand
pile.push(i);
}
return r;
}
O(n) malgré le while imbriqué : chaque index entre une fois et sort au plus une fois.
Les termes à connaître
- Pile (LIFO)
Dernier entré, premier sorti. En Java :
Dequeimplémenté parArrayDeque, avecpush,pop,peek.Stackest obsolète (synchronisée, héritant deVector).- Motif « appariement »
Empiler ce qui ouvre, dépiler ce qui ferme : parenthèses, balises, blocs. La pile est la seule structure qui respecte l'imbrication.
- Pile monotone
Une pile dont les éléments restent triés (croissants ou décroissants). Elle résout « le prochain élément plus grand » pour tous les éléments en O(n) au total.
- Amortissement
Dans une pile monotone, chaque élément est empilé une fois et dépilé au plus une fois : 2n opérations, donc O(n) malgré la boucle
whileimbriquée.- Empiler les index
Souvent on empile l'index plutôt que la valeur : on garde ainsi l'accès à la valeur et à la position, nécessaire pour calculer une distance.
- Notation polonaise inverse
3 4 + 2 *: on empile les nombres, et chaque opérateur dépile ses deux opérandes. L'exercice d'évaluation d'expression le plus courant.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.