Stack: cos’è e come usarlo in informatica

Aggiornato il: 17-10-2022 23:08
Lo stack è una delle più importanti strutture dati che esistono in informatica, ed il suo funzionamento ha ispirato molti dispositivi, sia lato hardware che lato software. Letteralmente stack significa “pila”, intesa non come batteria bensì come “pila di piatti”, “mucchio ordinato” e via dicendo. Esistono vari livelli interpretativi legati all’uso dello stack e, di fatto, tale termine può assumere più significati leggermente diversi a seconda dei casi. Gran parte delle applicazioni dello stack, per inciso, deriva prettamente dal mondo Linux.





Definizione basica di stack

In informatica uno stack è una struttura dati composta da un numero non specificato di elementi, che può andare da 0 a n; il numero non viene specificato all’inizio per mantenere massima flessibilità. Lo stack o “pila” (intesa come pila di elementi, insieme ordinato di elementi) permette di accumulare dati in ordine di inserimento, e poi prelevarli in ordine inverso. Se in uno stack inserisco 1, poi 2, poi 3, poi 4, andrò a prelevare prima il 4, poi il 3, poi il 2 ed infine l’1 a ritroso.

Come funziona lo stack?

Per fare un esempio pratico si può pensare, a questo punto, ad una pila di piatti: se inseriamo come base quello usato per il primo, poi quello per il secondo ed infine quello della frutta, avremo eseguito esattamente tre operazioni di push. Se facciamo pop per la prima volta, estrarremo per primo il piatto usato per la frutta, poi quello per il secondo, poi quello per il primo (in ordine inverso da quello in cui li abbiamo inseriti).

Politica di gestione dello stack

La gestione di questo tipo viene definita usualmente LIFO (Last In First Out, ovvero: il primo ad entrare è anche l’ultimo ad uscire), e rappresenta una delle politiche di gestione più diffuse in informatica, applicabili a diversi ambiti pratici e teorici. A livello grafico, possiamo visualizzare la situazione mediante la seguente immagine (Credits By Vectorization: OmenBreeze – Own work based on: Lifo stack.png by Maxtremus, CC0, Link).

Nella stessa vediamo, nell’ordine (gli step sono indicati dai numeri in grigio):

  1. Push dell’elemento numerico corrispondente al 2, quando nella struttura dati era presente il solo numero 1;
  2. Push del 3;
  3. Push del 4;
  4. Push del 5;
  5. Push del 6: ad oggi abbiamo nello stack 5 elementi che corrispondono ai numeri da 1 a 5, nell’ordine crescente;
  6. Abbiamo qui un pop, in particolare del numero ultimo ad essere stato inserito ovvero il 6, per cui estraiamo il numero e nello stack restano 5 elementi;
  7. pop del 5
  8. pop del 4
  9. pop del 3
  10. pop del 2, e solo 1 rimane in lista.

Lifo stack.svg

Lo stack nei linguaggi di programmazione

A livello di tipo di dato astratto ovvero di linguaggi di programmazione, lo stack è caratterizzato da una lista o collection di elementi, in cui sono disponibili due operazioni primitive di base:

  • push, che serve per inserire un elemento in pila o, letteralmente, impilarlo;
  • pop, che invece estrae l’ultimo elemento dalla struttura dati.

Questo tipo di funzionamento vale a livello generale, e prescinde dai singoli linguaggi che hanno comunque, ognuno di essi, un proprio modo di gestire le pile o stack. Possiamo vedere questo funzionamento come una struttura dati ordinata in cui l’accesso è consentito soltanto da un lato, e che si presta a funzioni di accumulo dati oppure di ricorsione, dove richiesta.

Lo stack in PHP

In PHP possiamo sfruttare le funzioni primitive array_push() e array_pop(), dall’ovvio significato e presente fin dalla versione PHP numero 4 (e anche nella versione 8, ovviamente). Un esempio di push è il seguente:

$lo_stack = array("anna", "fernanda", "mario", "girolamo");
array_push($lo_stack, "gennaro", "rita");
print_r($stack); --> Stamperà in output: ["anna", "fernanda", "mario", "girolamo", "gennaro", "rita"

Un esempio di pop è invece il seguente:

$stack = array("anna", "fernanda", "mario", "girolamo");
$fruit = array_pop($stack);
print_r($stack); --> Stamperà in output: ["anna", "fernanda", "mario"]

Lo stack in Python

Il linguaggio Python supporta alcune funzioni native specifiche per gestire uno stack in modo efficiente:

  • empty() – verifica se lo stack è vuoto
  • size() – restituisce il numero di elementi dello stack
  • top() / peek() – preleva l’elemento ultimo senza cancellarlo
  • push(a) – Inserisce l’elemento nello stack
  • pop() – preleva l’elemento ultimo, cancellandolo

Ecco un semplice esempio di gestione dello stack in Python.

lo_stack = [] # stack vuoto, all'inizio
# aggiungiamo tre elementi
lo_stack.append('anna')
lo_stack.append('fernanda')
lo_stack.append('mario')
print('Lo stack contiene: ')
print( lo_stack )
# funzione pop per prelevare l'elemento inserito per ultimo
print('\nElementi estratti dalla lista:')
print(lo_stack.pop()) # estrae mario
print(lo_stack.pop()) # ""  "" fernanda
print(lo_stack.pop()) # ""  "" anna
print('\nAdesso nello stack ci sono:')
print(lo_stack) # niente, è un insieme vuoto

Possibili applicazioni dello stack in informatica

Le applicazioni dello stack in informatica sono innumerevoli: lo stack viene usato come struttura di supporto per i meccanismi di ricorsione, quantomeno in una delle sue implementazioni più usate anche in ambito didattico. Per intenderci, se io implemento una funzione fattoriale:

function fattoriale ( n ) {...}

posso implementarla sfruttando la ricorsione:

function fattoriale ( n ) {
if n==1 return 1; //condizione di uscita
else return fattoriale (n-1) * n; //funzione ricorsiva
}

Ogni chiamata della funzione a se stessa non produce un loop infinito, come potrebbe sembrare a prima vista: produce una catena di chiamate consecutive che allocano spazio in memoria, tra loro “collegate” mediante ricorsione, in cui non è difficile immaginare la rappresentazione grafica:

fattoriale (4) // NB il fattoriale di n è dato dal prodotto di tutti gli interi positivo precedenti, quindi ad esempio fattoriale(4) = 4 x 3 x 2 x 1 = 24

[ 4 ]

[ 4 * 3 ]

[ 4 * 3 * 2 ]

[ 4 * 3 * 2 * 1 ]

Lo stack può essere anche utile in circostanze in cui sia richiesta una struttura dati a supporto, che sia in grado di velocizzare e rendere più efficenti le operazioni come accade, ad esempio, in alcuni algoritmi di ordinamento. Lo stack può essere implementato anche a livello hardware, facendo uso di opportune primitive assembly.

Cosa significa stack overflow?!

Stando alla documentazione classica del linguaggio GNU Fortran (ad oggi offline, salvata su Web Archive), si definisce stack overflow il caso in cui il puntatore dello stack, ovvero l’indirizzo di memoria che salva la posizione in cui accedere via push e pop (e che generalmente si raffigura con una freccetta), eccede i limiti di memoria. Per quanto grande sia, infatti, una memoria è sempre limitata, per cui uno stack overflow può accadere per situazioni su questa falsariga: a livello pratico, si verifica tale circostanza che genera un errore – quasi sempre non reversibile e non correggibile in runtime – nel caso in cui un linguaggio provi ad accedere ad aree di memoria non sue, non esistenti o troppo “in là”. Quando un software tenta di utilizzare più spazio di quello disponibile nello stack delle chiamate (superando i limiti consentiti dalla macchina) lo stack overflow genera un crash o un errore irreversibile.

Stack Overflow è anche il nome di una famosa community pubblica (https://stackoverflow.com/) in cui è possibile porre domande e cercare risposte e spunti di risoluzione di problemi di ogni genere: informatica, linguaggi di programmazione, WordPress, ma anche astronomia, matematica, ingegneria, fisica, filosofia e così via.



Questo blog pubblica contenuti ed offre servizi free da 11 anni. – Leggi un altro articolo a caso – Per informazioni contattaci
4/5 (1)

Ti sembra utile o interessante? Vota e fammelo sapere.

Stack: cos’è e come usarlo in informatica
Lifo stack.svg
Torna su