Ciao a tutti e benvenuti in questa guida dove vi verrà introdotto il concetto di una delle strutture dati più importanti nell'informatica: La pila (o Stack in inglese). In più vedremo come implementare una di queste pile usando il linguaggio di programmazione Java, (applicabile anche ad altri linguaggi) e discuteremo quali sono i casi quando conviene usare la Pila nei propri algoritmi.
Che cos'è una Pila
La pila o stack è una struttura dati che ci permette di organizzare una serie di oggetti in una maniera LIFO (Last In First Out). Questo significa che il primo oggetto che viene posto nella pila sarà l'ultimo ad uscirne e l'ultimo oggetto posto sulla pila sarà il primo ad uscirne.
La classica metafora usata per spiegare una pila è una pila di piatti. Immaginate di lavorare in una cucina dove vengono portati vari piatti sporchi che hanno bisogno di essere lavati. Un modo per gestire questa situazione sarebbe creare appunto una pila di piatti ed ogni volta che vi viene consegnato un nuovo piatto da lavare posizionate il piatto in cima alla pila. Quando siete pronti per lavare un piatto potete prendere il piatto più in alto nella pila, lavarlo e metterlo nell'armadio.
La pila è dotata di due metodi principali: Push e Pop. Il metodo Push semplicemente aggiunge un oggetto in cima alla pila ed il metodo Pop prende l'oggetto più in alto nella pile e lo rimuove.
FOTO stack
Un'altro esempio che a me piace di più è quello di un genitore che deve badare ai propri figli.
Immaginate di essere un genitore di n figli (per questo esempio usiamo n=2). La vostra strategia per badare ai bambini è (una strategia terribile in vita reale) è dare la propria attenzione al bambino più piccolo. Immaginiamo che in partenza abbiamo n=0 figli. Poi arriva il figlio numero 1, lo prendiamo e lo posizioniamo in cima allo stack (pila). Questo indica che il prossimo bambino a cui daremo la nostra attenzione è il bambino 1. Prima che avete l'opportunità di iniziare a badare al bambino 1, nasce un'altro bambino (bambino 2). Quindi prendete il bambino due e lo posizionate in cima alla pila (Stack).
Che cosa succede al bambino 1? Questo bambino diventa l'ultimo bambino nella pila e quindi perde priorità. Questo significa che quando siamo pronti a badare ad un bambino cominceremo dal bambino 2 e passeremo al bambino 1 solo quando abbiamo finito con il bambino 2. La foto in basso vi mostra questo esempio.
Quando usare una pila
La pila è molto utile appunto quando si vuole eseguire istruzioni o operazioni nella maniera LIFO. Un esempio molto comune per l'utilizzo di una Pila è per iterare i nodi di un grafo.