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.
- Inizializzazione della pila (eventuale allocazione di memoria e azzeramento dell'indice testa).
- Push: inserimento di un valore nella pila.
- Pop: estrazione dell'ultimo elemento inserito.
- Top: lettura dell'ultimo elemento inserito senza estrazione.
- Drop: eliminazione dell'elemento in cima alla pila senza leggerlo.
- Controllo se la pila è vuota, nel qual caso non ci sono elementi da estrarre. Se la pila è realizzata
come descritto sopra, essa è vuota se testa è nullo.
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.