Les piles

Vérifier que les parenthèses de {[()()]} s'associent correctement demande une pile et 8 empilements et dépilements, un par parenthèse.

Dernier entré, premier sorti

Pense à une pile d'assiettes. Tu poses une assiette propre sur le dessus, et quand tu en as besoin, tu la prends sur le dessus. L'assiette ajoutée en dernier est la première à sortir. Une pile est une structure de données qui suit exactement cette règle, appelée dernier entré, premier sorti (LIFO en anglais). Elle offre deux opérations principales : empiler (push) pose une valeur au sommet, et dépiler (pop) retire la valeur du sommet et la renvoie. Beaucoup de piles proposent aussi consulter (peek), qui regarde le sommet sans le retirer.

Dans les notes du cours 6.006 du MIT, la pile est un cas particulier de l'interface de séquence : insert last(x) et delete last(). Cela indique déjà comment en construire une. On range les valeurs dans un tableau dynamique et on traite la fin du tableau comme le sommet. Dans l'unité précédente, la fin était le côté bon marché : empiler et dépiler coûtent donc chacun 1 étape (amortie, à cause de la copie occasionnelle). La taille de la pile ne change rien. Dépiler une pile de 3 valeurs ou de 3 millions de valeurs, c'est la même étape unique.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, le dernier empilé
console.log(stack[stack.length - 1]); // consulter : 8
console.log(stack.length);          // affiche 2

Vérifier des parenthèses

Un usage classique de la pile consiste à vérifier que les parenthèses sont équilibrées, ce que font tous les éditeurs de code et tous les compilateurs. On lit le texte de gauche à droite. Chaque parenthèse ouvrante, (, [ ou {, est empilée. Chaque parenthèse fermante doit correspondre à l'ouvrante au sommet de la pile : si c'est le cas, on dépile cette ouvrante ; si la pile est vide ou que le sommet est d'une autre sorte, la suite n'est pas équilibrée. À la fin, la pile doit être vide, sinon une ouvrante n'a jamais été fermée.

Essaie les suites du labo. {[()()]} demande 4 empilements et 4 dépilements, 8 étapes, et se termine avec une pile vide. ([)] échoue au troisième caractère : le ) arrive alors que [ est au sommet. (() est lu jusqu'au bout avec un ( en trop. Pourquoi une pile convient-elle à ce travail ? Les parenthèses s'imbriquent, et la dernière ouverte doit être la première fermée. C'est le principe dernier entré, premier sorti.

Où l'on retrouve aussi des piles

• La pile d'appels. Quand la fonction a appelle b et que b appelle c, l'ordinateur empile un enregistrement pour chaque appel. Quand c se termine, son enregistrement est dépilé et b reprend là où il s'était arrêté. Une récursion infinie remplit cette pile : c'est l'erreur de « débordement de pile » (stack overflow).
• Annuler. Un éditeur empile chaque modification. Annuler dépile la modification la plus récente et la défait.
• Le bouton Retour. Un navigateur empile chaque page que tu quittes ; Retour dépile la dernière.
• Le parcours en profondeur. Le cours d'algorithmique utilisait une pile pour aller aussi loin que possible dans un labyrinthe avant de revenir en arrière.