Tutorial →
Appunti scolastici → Appunti sparsi →
Lo stack
Stack letteralmente significa pila, catasta, mucchio, ammasso. Questo
termine viene usato in ambito tecnico in una miriade di significati
diversi... In questa pagina verrà descritto in modo intuitivo il concetto di
struttura dati di tipo LIFO: Last In, First Out.
Si consideri l'analogia di una catasta di piatti, tutti uguali tra di
loro. Sono possibili due sole operazioni:
- Aggiungere un piatto (sottointeso: al di sopra della catasta)
- Togliere un piatto (sottointeso: dalla cima della catasta)
A meno di essere davvero abili (e complicarsi la vita...) non sono
possibili altre operazioni: togliere due piatti alla volta, togliere un
piatto centrale, mettere un piatto alla base della pila... Una cosa invece
facile da fare è mettere "troppi" piatti e far crollare l'intera pila. Nel
mondo reale ci sono anche cose impossibili: togliere più piatti di quanti se
ne sono.
Analogamente in una struttura dati a stack sono possibili solo due
operazioni:
- PUSH: aggiungere un dato in cima allo stack
- POP: togliere l'ultimo dato aggiunto dalla cima dello stack
Qualche avvertenza:
- la manipolazione dei dati dello stack (per esempio togliere dati dal
centro anziché dalla cima) è in genere classificata tra le tecniche
avanzate di programmazione. Se avete letto questa pagina, meglio
che lasciate perdere
- il controllo del superamento della massima capacità dello stack (stack
overflow) è spesso lasciato alla diretta responsabilità del
programmatore.
- è compito diretto del programmatore evitare l''estrazione di un dato
da uno stack vuoto (stack underflow)
- se l'ordine dei dati ha una qualche importanza, è compito del
programmatore la sue gestione. Per esempio se inserisco A, B e C e poi
voglio rimettere le cose dove stavano, occorre prima estrarre C, poi B e
per ultimo A, al contrario
Una struttura a stack può essere realizzata in varia modo:
- In hardware, attraverso registri a scorrimento. Un esempio è lo
stack hardware del PIC18 (return address stack),
costituito da 31 celle da 21 bit ciascuna, accessibili solo attraverso
alcune istruzioni (call,
return, retie e poche altre) o
attraverso l'invocazione hardware di un
interrupt e solo nella cella più alta (Top-of-Stack)
- Usando la memoria RAM di un processore e l'assistenza di appositi
registri dedicati (stack pointer dei processori x86 e Z80,
FSR e INDF
del PIC18)
- Usando matrici ed opportuni puntatori/indici (tutti i linguaggi di
programmazione ad alto livello)
Data di creazione di questa pagina: 29 marzo 2016
Ultima modifica: 13 aprile 2017
