Pile

Controllare che le parentesi in {[()()]} si accoppino correttamente richiede una pila e 8 push e pop, uno per ogni parentesi.

L'ultimo entrato è il primo a uscire

Pensa a una pila di piatti. Metti un piatto pulito in cima e, quando te ne serve uno, lo prendi dalla cima. Il piatto aggiunto per ultimo è il primo a uscire. Una pila (stack) è una struttura dati con esattamente questa regola, detta last in, first out (LIFO): l'ultimo entrato è il primo a uscire. Offre due operazioni principali: push mette un valore in cima, e pop toglie il valore in cima e lo restituisce. Molte pile offrono anche peek, che guarda la cima senza toglierla.

Negli appunti del corso 6.006 del MIT la pila è un caso particolare dell'interfaccia di sequenza: insert last(x) e delete last(). Questo dice già come costruirne una. Metti i valori in un array dinamico e tratta la fine dell'array come la cima. Nell'unità precedente la fine era l'estremità economica, quindi push e pop costano 1 passo ciascuno (ammortizzato, per via della copia occasionale). La dimensione della pila non conta. Fare pop da una pila di 3 valori o di 3 milioni di valori è lo stesso singolo passo.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, l'ultimo inserito
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Controllare le parentesi

Un uso classico della pila è controllare che le parentesi siano bilanciate, cosa che fanno tutti gli editor di codice e i compilatori. Leggi il testo da sinistra a destra. Ogni parentesi aperta, (, [ o {, viene inserita con push. Ogni parentesi chiusa deve corrispondere a quella aperta in cima alla pila: se corrisponde, togli quella aperta con pop; se la pila è vuota o in cima c'è un tipo diverso, la stringa non è bilanciata. Alla fine la pila deve essere vuota, altrimenti qualche parentesi aperta non è mai stata chiusa.

Prova le stringhe nel laboratorio. {[()()]} richiede 4 push e 4 pop, 8 passi, e finisce con la pila vuota. ([)] fallisce al terzo carattere: la ) arriva mentre in cima c'è [. (() arriva alla fine con una ( avanzata. Perché una pila è adatta a questo lavoro? Le parentesi si annidano, e quella aperta più di recente deve essere la prima a chiudersi. È proprio «l'ultimo entrato è il primo a uscire».

Dove compaiono ancora le pile

• La pila delle chiamate. Quando la funzione a chiama b e b chiama c, il computer fa il push di un record per ogni chiamata. Quando c termina, il suo record viene tolto con pop e b continua da dove si era fermata. Una ricorsione infinita riempie questa pila: è l'errore di «stack overflow».
• Annulla. Un editor fa il push di ogni modifica. Annulla fa il pop della modifica più recente e la ribalta.
• Pulsante Indietro. Un browser fa il push di ogni pagina che lasci; Indietro fa il pop dell'ultima.
• Visita in profondità. Il corso di algoritmi usava una pila per andare il più a fondo possibile in un labirinto prima di tornare indietro.