Formations — 1 037 leçons en français

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 : Deque implémenté par ArrayDeque, avec push, pop, peek. Stack est obsolète (synchronisée, héritant de Vector).

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 while imbriqué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.

Lire l'explication détaillée et faire le quiz →

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.