libri-javascript-python

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.

pila
pila in c

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

Indice argomenti linguaggio C

La funzione fopen

La funzione fclose

Funzione fprintf

Funzione fscanf

Allocazione dinamica della memoria con malloc

Realizzare un menù di scelta in C

Strutture complesse in C

Come sommare gli elementi della cornice esterna

Come sommare due matrici

Matrice trasposta

Prodotto tra matrici

Ricerca elementi in una matrice

Merge sort in C

Insertion Sort in C