Strutture dati astratte: la pila

Mauro Brunato


Argomenti correlati: [ Strutture dati astratte ] [ Valutazione di espressioni aritmetiche ]
Un'altra struttura largamente utilizzata in tutti i campi dell'informatica è la pila (stack in inglese). Come la coda, anche questa struttura ammette due operazioni (inserimento ed estrazione di un dato), ma il dato da estrarre è sempre l'ultimo che è stato inserito. Si tratta di una struttura di tipo LIFO (Last In, First Out).

Il nome pila fa riferimento proprio a questa caratteristica: gli elementi vengono "impilati" l'uno sull'altro, cosicché il primo ad essere disponibile è quello inserito più di recente.

Realizzazione tramite vettori

A differenza della coda, la pila richiede - oltre al vettore - un solo indice, che contrassegna la prima casella libera del vettore a partire dalla posizione iniziale. Chiameremo testa questo indice, che inizialmente deve assumere valore 0.

Supponendo di aver inserito successivamente i valori 4, 8, 7 e 5 nella pila, la struttura si presenterà come segue:

Ad ogni inserimento, il valore da inserire viene assegnato alla casella del vettore correntemente indicizzata da testa, dopodiché l'indice viene incrementato. Ad esempio, l'introduzione del valore 2 porta alla seguente configurazione:

Grazie all'esistenza degli operatori di incremento del C++, l'introduzione dell'elemento 2 può avvenire in un'unica istruzione:

v[testa++] = 2;

l'estrazione richiede il decremento dell'indice, seguito dalla lettura del valore. Ad esempio, per assegnare alla variabile x il valore estratto dalla pila l'operazione è la seguente:

x = v[--testa];

È chiaro che il decremento dell'indice fa sì che la casella contenente l'ultimo valore venga considerata libera.

Operazioni eseguibili su una pila

Seguono le operazioni che di norma sono realizzate su una pila; i nomi che precedono alcune righe sono quelli tradizionalmente associati a queste operazioni.

Codice

Valgono molte delle considerazioni fatte per la coda, salvo il problema dell'esaurimento del vettore in seguito all'avanzamento degli indici. Il fatto che lo svuotamento avvenga nella direzione opposta al riempimento fa sì che la struttura possa essere usata a piacimento senza bisogni di operazioni di modulo.

Ecco il file header, il file cpp e un abbozzo del programma principale per una coda dinamica.

Diverse convenzioni

Mentre la realizzazione descritta sopra prevede che la pila sia realizzata in un vettore a partire dall'elemento di indice 0 e crescendo "verso l'alto", le realizzazioni a basso livello (ad esempio la pila dei ritorni del processore) prevedono che la memoria dedicata alla pila sia riempita dalla posizione di indirizzo più elevato e in crescita "verso il basso". Spesso, l'indice della posizione libera, da noi chiamato testa, è detto "fondo" ("bottom" in inglese).

Entrambe le convenzioni sono ragionevoli e motivate, e nell'analizzare un programma scritto da altri è necessario valutare caso per caso.


Un esempio di applicazione della pila è la valutazione di espressioni aritmetiche.