In questa lezione studieremo lo stack (o pila), cioè un elenco di dati avente la caratteristica di permettere l’inserimento di nuovi elementi e l’estrazione degli elementi introdotti ma solo da un’unica estremità.
Un elemento nella pila è inserito con una funzione detta Push, mentre un elemento si estrae con la funzione Pop.
La regola è questa: l’ultimo elemento inserito con Push è il primo ad essere estratto con Pop.
Quindi per questo motivo si parla di struttura LIFO (Last in First Out) ovvero l’ultimo elemento ad entrare è anche il primo ad uscire.
La gestione dello stack si può realizzare o con le linked list o appoggiandosi ad un array visto in “verticale” dove l’inserimento e l’estrazione avvengono sempre dallo stesso lato.
La pila inoltre richiede un indice, che contrassegna la prima casella libera del vettore a partire dalla posizione iniziale.
Questo indice lo chiamiamo testa e quando la pila è vuota il suo valore è zero. Nella posizione indicata dall’indice testa dunque estrarremo o inseriremo i dati con le funzioni Pop e Push.
Rappresentazione in figura
Nella figura ecco un esempio di stack con l’indice testa che indica la prima casella libera e dopo l’inserimento, del numero 5, l’indice testa si sposta di 1.
Altre possibili operazioni sono:
Top che restituisce l’elemento superiore dello stack.
isEmpty che restituisce true se lo stack è vuoto, altrimenti false.
isFull che restituisce true se lo stack è pieno, altrimenti vero.
Le operazioni push(), pop(), isEmpty() e top() richiedono tutti tempo O(1), infatti non eseguiamo cicli in nessuna di queste operazioni.
Un tipico esempio di applicazione dello stack si ha nelle Torre di Hanoi, nell’attraversamento degli alberi e in tanti altri algoritmi.
Questa è solo una piccola introduzione sull’uso dello stack, nelle prossime lezioni faremo altri esempi.
Alcuni link utili
Allocazione dinamica della memoria con malloc
Realizzare un menù di scelta in C
Come sommare gli elementi della cornice esterna
Ricerca elementi in una matrice
molto rico questo sito, veramente grazie mille alla persona e uttttto le staff