Stack in Python: implementare strutture dati LIFO

Ogni volta che premi Ctrl+Z per annullare un errore, clicchi il tasto indietro del browser o guardi una funzione ricorsiva svolgere i suoi risultati, stai facendo affidamento su uno stack. Poiché sono così profondamente integrati nel software che usi ogni giorno, interagisci spesso con gli stack senza nemmeno rendertene conto.

In questo articolo vedremo cos’è uno stack, la logica di base che lo governa, confronteremo diverse strategie di implementazione usando le librerie standard di Python e le applicheremo per risolvere problemi algoritmici.

Ti consiglio il nostro corso su Writing Efficient Python Code per abbinare la conoscenza delle strutture dati alle buone pratiche prestazionali e di tenere a portata di mano il Python Basics Cheat Sheet come riferimento rapido. 

Cos’è uno stack in Python?

Prima di guardare il codice, è importante capire le basi concettuali che rendono lo stack in Python uno strumento così potente. Vediamo il principio alla base degli stack e come si differenziano da altre strutture dati comuni.

La struttura dati LIFO

Uno stack è una struttura dati lineare che segue il principio Last-In-First-Out (LIFO). Significa che l’elemento aggiunto più di recente è sempre il primo a essere rimosso. Pensalo come una pila di piatti in mensa. Appoggi i nuovi piatti in cima e prendi sempre per primo quello più in alto. Non prendi mai un piatto dal centro o dal fondo. L’accesso è interamente limitato alla cima.

Questo unico vincolo, l’accesso solo dalla cima, dà agli stack la loro prevedibilità ed efficienza. Ogni elemento entra ed esce dallo stesso estremo, mantenendo le operazioni semplici e veloci.

Una cosa da notare fin da subito è che Python non include un tipo primitivo di stack dedicato, come fanno altri linguaggi. Non esiste una parola chiave stack o una classe integrata. Invece, Python offre valide alternative integrate come le list, collections.deque e queue.LifoQueue che possono tutte comportarsi come stack. Vedremo ognuna di queste implementazioni in dettaglio più avanti.

Stack vs altre strutture dati

Capire cos’è uno stack diventa molto più chiaro quando vedi cosa non è. Le due strutture più comunemente confrontate con gli stack sono le queue e le list standard di Python.

Stack vs queue

Una queue segue il principio First-In-First-Out (FIFO), l’opposto di uno stack. In una queue, gli elementi vengono aggiunti in coda e rimossi dal fronte, come una fila di persone in attesa alla biglietteria. Stack e queue sono entrambe lineari e limitano l’accesso agli elementi, ma lo fanno in direzioni opposte. 

Scegliere quella sbagliata può rompere silenziosamente la logica di un algoritmo. Per esempio, sostituire uno stack con una queue in una ricerca in profondità la trasformerebbe in una ricerca in ampiezza, producendo risultati completamente diversi.

Stack vs list

Una list Python standard, invece, offre accesso casuale. Puoi leggere, inserire o cancellare elementi a qualsiasi indice con operazioni come my_list[3] o my_list.insert(2, value). Questa flessibilità è utile in molti contesti, ma significa anche che nulla ti impedisce di accedere o modificare accidentalmente elementi nel mezzo della struttura. 

Quando implementi un algoritmo che dipende da un ordinamento LIFO rigoroso, come backtracking, parsing della sintassi o funzionalità di annulla, la natura non vincolata di una list può introdurre bug sottili.

Ecco perché il pattern di accesso limitato di uno stack è una caratteristica, non una limitazione. Consentendo l’interazione solo con l’elemento in cima, uno stack in Python impone la correttezza per design. Non puoi rimuovere accidentalmente dall’estremità sbagliata o sovrascrivere un elemento sepolto in profondità nella struttura. 

Nell’ingegneria degli algoritmi, vincoli come questi mantengono pulita la logica e prevedibile il codice.

Operazioni fondamentali sugli stack e complessità temporale

Ora che sappiamo cos’è uno stack in Python e come differisce da altre strutture, vediamo le operazioni fondamentali che ogni stack supporta e analizziamo l’efficienza di ciascuna.

Operazioni standard dello stack

Ogni implementazione di stack si basa su un piccolo set di operazioni standard, indipendentemente dal linguaggio. Questi sono i mattoni che userai ogni volta che lavori con uno stack.

Push aggiunge un elemento in cima allo stack. Se lo stack contiene [A, B] e fai push di C, lo stack diventa [A, B, C], con C ora in cima.

Pop rimuove e restituisce l’elemento attualmente in cima. Continuando l’esempio, fare pop da [A, B, C] restituisce C e lascia lo stack come [A, B].

Peek (a volte chiamato top) ti permette di vedere l’elemento in cima senza rimuoverlo. È utile quando la tua logica deve ispezionare il valore corrente in cima prima di decidere se fare pop, un pattern frequente nel parsing di espressioni e nei problemi di parentesi bilanciate.

Oltre a queste tre operazioni core, due metodi di supporto sono importanti per scrivere codice sugli stack sicuro e privo di errori:

• is_empty() verifica se lo stack contiene elementi. Chiamare pop o peek su uno stack vuoto è una fonte comune di errori a runtime, quindi controllare prima se è vuoto è una buona abitudine di programmazione difensiva.

• size() restituisce il numero corrente di elementi nello stack. È utile quando devi tracciare quanto è profonda una ricorsione o quanti elementi restano da processare.

Infine, vale la pena definire un termine che incontrerai in libri di testo e colloqui: Stack Underflow. È la condizione d’errore che si verifica quando tenti di fare pop o peek da uno stack vuoto. Non c’è nulla da rimuovere o vedere, quindi l’operazione è invalida. 

L’eccezione o il comportamento esatto dipendono dall’implementazione. Vedremo come Python lo gestisce concretamente quando analizzeremo list, deque e LifoQueue nella prossima sezione.

Analisi della complessità

Uno dei motivi principali per cui gli stack sono così diffusi negli algoritmi è la loro efficienza. Scomponiamo la complessità in tempo e spazio di ciascuna operazione.

Push è O(1). In un’implementazione efficiente, aggiungere un elemento in cima è un’operazione a tempo costante. Lo stack non deve spostare o riordinare elementi esistenti. Semplicemente colloca il nuovo elemento in fondo. Questo vale sia per collections.deque sia, in media, per la list integrata di Python.

Pop è O(1). Rimuovere l’elemento in cima è altrettanto rapido. Lo stack accede direttamente all’ultima posizione, restituisce il valore e decrementa il contatore interno di dimensione. Anche qui, nessuno spostamento degli altri elementi è richiesto.

Peek è O(1). Visualizzare l’elemento in cima senza rimuoverlo è un accesso diretto per indice, quindi anch’esso a tempo costante.

Search è O(n). Qui gli stack rivelano il loro compromesso deliberato. Se devi verificare se un certo valore esiste da qualche parte nello stack, non hai scelta: devi scansionare tutti gli n elementi dall’alto verso il basso. 

Gli stack non sono progettati per ricerche arbitrarie. Sacrificano la capacità di ricerca in cambio di push e pop veloci e prevedibili. Se il tuo caso d’uso richiede ricerche frequenti, una struttura diversa, come un set o un dizionario, è più adatta.

La complessità spaziale è O(n). Uno stack che contiene n elementi richiede memoria proporzionale a n. Non c’è overhead nascosto oltre a quello necessario per memorizzare gli elementi, più una piccola costante per la gestione interna della struttura.

Ecco un rapido riepilogo:

La cosa da ricordare è che uno stack in Python è ottimizzato per inserimenti e rimozioni veloci a un’estremità. Finché lo usi per ciò per cui è progettato, ossia gestire accessi ordinati LIFO, offre prestazioni eccellenti. Nel momento in cui ti ritrovi a cercare regolarmente dentro uno stack, è un segnale per riconsiderare la struttura dati scelta.

Implementazioni di stack in Python

Con teoria e analisi della complessità alle spalle, è il momento di scrivere del codice. Python offre tre modi principali per implementare uno stack, ciascuno con i propri punti di forza e compromessi. Vediamoli tutti e vediamo come scegliere quello più adatto al nostro caso d’uso.

Stack in Python usando la list integrata

Il modo più semplice per creare uno stack in Python è con la list integrata. Poiché le list sono array dinamici che supportano aggiunta e rimozione dalla fine, si mappano naturalmente al comportamento di uno stack. 

Il metodo .append() funge da push e .pop() senza argomenti rimuove e restituisce l’ultimo elemento. Vediamolo con un esempio di codice:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

Funziona bene, ma devi gestire con attenzione il caso di stack vuoto. In Python, sia .pop() che stack[-1] sollevano un’IndexError quando la list è vuota. È così che Python segnala la condizione di Stack Underflow definita prima. 

La best practice è racchiudere queste chiamate in un try/except o controllare se è vuoto prima di accedere alla cima, come nel seguente esempio:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

C’è una sottigliezza prestazionale da capire. Le list di Python sono basate su array dinamici. Quando chiami .append(), l’operazione è di solito istantanea O(1). Tuttavia, quando l’array interno esaurisce lo spazio pre-allocato, Python deve allocare un nuovo blocco di memoria più grande e copiare tutti gli elementi esistenti. 

Questa riallocazione occasionale rende .append() un’operazione O(1) ammortizzata piuttosto che strettamente O(1). In pratica, il ritardo è raro e breve, ma in applicazioni sensibili alla latenza o real-time, questa imprevedibilità può contare.

Nonostante questa avvertenza, .append() e .pop() su una list sono l’approccio preferito per la maggior parte dei compiti semplici con gli stack. Il fatto di non dover importare nulla, la sintassi familiare e la diffusa familiarità degli sviluppatori lo rendono una buona scelta predefinita, soprattutto per scripting, prototipazione e problemi da colloquio dove la semplicità conta.

Stack in Python usando collections.deque

Se ti serve una prestazione O(1) costante senza i ritardi occasionali di riallocazione, collections.deque è l’upgrade consigliato. Il nome sta per "double-ended queue", ma funziona perfettamente come stack Python ad alte prestazioni. Il nostro esempio precedente con la sintassi deque appare così:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

Nota che l’interfaccia è identica all’approccio basato su list. .append(), .pop() e [-1] funzionano nello stesso modo. Anche il comportamento di IndexError sull’accesso a vuoto è invariato, quindi il tuo codice di gestione errori non richiede modifiche:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

La differenza cruciale è sotto il cofano. Una deque è implementata come una lista doppiamente collegata di blocchi a dimensione fissa invece che come un singolo array. Questo significa che non deve mai riallocare e copiare l’intera struttura quando cresce. 

Ogni .append() e .pop() è una vera O(1) garantita, non ammortizzata ma costante. Per lavori pesanti sugli algoritmi dove esegui push e pop migliaia o milioni di volte, questa consistenza fa la differenza.

Stack in Python usando queue.LifoQueue

La libreria standard di Python include anche queue.LifoQueue, un’implementazione di stack progettata specificamente per programmi multi-thread. La "LIFO" nel nome conferma l’ordinamento Last-In-First-Out, ma l’interfaccia e il comportamento sono piuttosto diversi dai due approcci precedenti. Vediamolo con un esempio:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

La prima cosa da notare è il cambio di sintassi. Push diventa .put() e pop diventa .get(). Questa nomenclatura deriva dal pattern produttore-consumatore del modulo queue, dove un thread "mette" elementi e un altro li "preleva".

Ci sono due differenze comportamentali importanti di cui essere consapevoli. 

Primo, LifoQueue non ha un metodo di peek sicuro. Non c’è un modo integrato per vedere l’elemento in cima senza rimuoverlo. Potresti accedere ad attributi interni, ma farlo in un contesto multi-thread vanifica lo scopo di usare una classe thread-safe e rischia condizioni di race.

Secondo, LifoQueue non solleva IndexError quando provi a prendere da uno stack vuoto. Per impostazione predefinita, .get() è bloccante. Mette in pausa il thread chiamante e attende indefinitamente finché un altro thread non inserisce un elemento nello stack. Se vuoi un comportamento non bloccante, puoi passare block=False, che solleva un’eccezione queue.Empty. Vediamolo con un esempio:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

A causa del meccanismo di locking interno che rende LifoQueue thread-safe, le sue operazioni hanno più overhead rispetto a list o deque. Questo lo rende una scelta scarsa per codice single-thread. Usa LifoQueue solo quando hai più thread che producono e consumano dati in parallelo e scegli deque o list in tutti gli altri casi.

Scegliere la giusta implementazione di stack in Python

Con tre opzioni disponibili, ecco un confronto affiancato per guidare la tua scelta:

Ecco il mio schema decisionale per scegliere la migliore implementazione:

• Usa list quando ti serve uno stack rapido senza import, come in script, notebook e lavagne ai colloqui. 

• Usa collections.deque quando scrivi codice algoritmico, processi grandi dataset o costruisci qualcosa dove le prestazioni contano. 

• Usa queue.LifoQueue solo quando hai un naturale scenario multi-thread con accesso concorrente.

Potresti imbatterti anche in tutorial che implementano uno stack Python da zero usando una lista collegata personalizzata, dove ogni nodo contiene un valore e un puntatore al nodo sottostante. A mio avviso, è sicuramente un esercizio didattico prezioso che può approfondire la comprensione di come funzionano internamente gli stack e di come i riferimenti in memoria si concatenano. 

Tuttavia, nel codice Python di produzione, uno stack con lista collegata è quasi sempre più lento di una deque a causa dell’overhead di creazione dei singoli oggetti nodo. Per il lavoro reale in Python, collections.deque offre la migliore combinazione di velocità, chiarezza e affidabilità.

Applicazioni degli stack in Python

Capire come implementare uno stack in Python è solo metà del quadro. Il vero valore degli stack emerge quando li vedi risolvere problemi che senza l’ordinamento LIFO sarebbero molto più complessi. Vediamo tre applicazioni classiche che ricorrono costantemente in colloqui, sistemi software e progettazione di algoritmi.

Verifica delle parentesi bilanciate

Il problema delle parentesi bilanciate è una delle domande sugli stack più frequenti nei colloqui tecnici. Data una stringa che contiene parentesi come (), [] e {}, devi determinare se ogni parentesi aperta ha la corrispondente parentesi chiusa nel giusto ordine.

La logica si mappa perfettamente su uno stack. Scorrendo la stringa da sinistra a destra, fai push di ogni parentesi aperta nello stack. Quando incontri una parentesi chiusa, fai pop dalla cima dello stack e verifica se corrisponde.

Se lo stack è vuoto quando provi a fare pop, o se la parentesi estratta non corrisponde, la stringa non è bilanciata. Dopo aver processato l’intera stringa, lo stack dovrebbe essere vuoto. Eventuali parentesi aperte rimanenti significano che qualcosa non è stato chiuso. Vediamolo in azione:

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

Seguiamo "{[()]}" passo dopo passo per vedere lo stack in azione:

Lo stack è vuoto alla fine, quindi l’espressione è bilanciata.

Questa stessa logica va ben oltre i problemi da colloquio. Compilatori e interpreter la usano per validare la sintassi, assicurandosi che ogni tag, parentesi o delimitatore aperto nel codice sorgente abbia una corretta corrispondenza. 

Se hai mai visto un messaggio SyntaxError: unexpected EOF in Python, hai visto una forma di questo controllo in azione. Validator HTML, parser JSON e persino linter per file di configurazione si basano su varianti di questo approccio basato su stack.

Implementare la depth-first search (DFS)

Depth-first search è uno degli algoritmi fondamentali per attraversare grafi, e uno stack è la struttura dati che la alimenta. L’idea è semplice. Parti da un nodo, esplora il più possibile lungo un ramo prima di tornare indietro per provare il successivo. La natura LIFO di uno stack in Python è ciò che rende questo comportamento "vai in profondità prima" naturale.

La maggior parte dei corsi introduttivi insegna la DFS usando la ricorsione, dove lo stack delle chiamate gestisce implicitamente l’ordine di attraversamento. Tuttavia, l’approccio ricorsivo ha un limite pratico. Il limite di ricorsione predefinito di Python è 1.000 frame. 

Per grafi grandi o profondamente annidati, questo porta a un RecursionError. La versione iterativa, che usa uno stack esplicito, evita questo problema e ti dà pieno controllo sull’attraversamento.

Vediamo un esempio di codice. Eseguiremo una DFS sul seguente grafo:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

Tracciamo l’esecuzione per vedere come lo stack governa l’attraversamento:

Nota come l’ordinamento LIFO costringa l’algoritmo a esplorare completamente i rami A → B → D e A → B → E → F prima di tornare indietro per visitare C. È proprio questo che distingue la depth-first search dalla breadth-first search, che usa una queue ed esplora tutti i vicini alla profondità corrente prima di andare più a fondo. 

Il pattern DFS iterativo mostrato qui funziona per alberi, grafi diretti e non diretti. È anche la base per algoritmi più avanzati come ordinamento topologico, rilevamento di cicli e risoluzione di labirinti e puzzle.

Gestire le operazioni di annulla/ripristina

Se hai mai usato un editor di testo, un’app di disegno o un foglio di calcolo, hai sfruttato annulla e ripristina senza pensare a come funzionano sotto il cofano. Il meccanismo è elegante e si basa esattamente su due stack.

Uno stack di annulla memorizza ogni azione o stato man mano che l’utente apporta modifiche. Quando l’utente attiva annulla, lo stato corrente viene estratto dallo stack di annulla e inserito in uno stack di ripristina.

Se poi l’utente attiva ripristina, lo stato viene estratto dallo stack di ripristina e reinserito nello stack di annulla. Se l’utente effettua una nuova modifica dopo un annulla, lo stack di ripristina viene svuotato. Non puoi ripristinare qualcosa che è stato sovrascritto da una nuova azione. Vediamolo con un esempio di codice:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

Il flusso degli stati tra i due stack segue uno schema chiaro:

Questo pattern a due stack non è limitato agli editor di testo. Compare ovunque gli utenti abbiano bisogno della possibilità di tornare indietro e avanti in una sequenza di cambiamenti (praticamente ovunque):

• Software di fotoritocco
• Rollback di transazioni nei database
• Gestione dello stato nei videogiochi

Il principio di base è sempre lo stesso. Uno stack Python traccia la cronologia, l’altro il futuro, e l’ordinamento LIFO assicura che tu torni sempre allo stato più recente per primo.

Concetti avanzati sugli stack in Python

Gli stack giocano anche un ruolo importante sotto la superficie di ogni programma Python che esegui e alimentano tecniche di ottimizzazione che possono ridurre drasticamente la complessità temporale di alcuni problemi. Vediamo entrambe queste dimensioni avanzate.

Capire lo stack delle chiamate

Ogni volta che chiami una funzione in Python, accade qualcosa dietro le quinte che non controlli direttamente. Python inserisce un nuovo frame in una struttura dati interna nota come call stack. Questo frame contiene le variabili locali della funzione, i suoi parametri e un puntatore alla riga di codice che ha avviato la chiamata. 

Quando la funzione termina, il suo frame viene rimosso dallo stack delle chiamate e il controllo ritorna al chiamante.

Puoi in realtà ispezionare questo comportamento con un semplice esempio:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

Quando function_c viene eseguita, lo stack delle chiamate ha quattro frame impilati uno sopra l’altro. Man mano che ogni funzione completa, il suo frame viene rimosso in ordine LIFO. Finisce prima function_c, poi function_b, poi function_a e infine l’ambito del modulo principale.

Questo è esattamente il meccanismo che rende possibile la ricorsione. Ogni chiamata ricorsiva inserisce un nuovo frame con le proprie variabili locali e i risultati si svolgono man mano che i frame vengono rimossi. Vediamolo con un esempio:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

Il problema nasce quando la ricorsione va troppo in profondità. Python imposta un limite di ricorsione predefinito di 1.000 frame per evitare che lo stack delle chiamate consumi tutta la memoria disponibile. Se la tua funzione ricorsiva supera questo limite, Python solleva un RecursionError. Vediamolo con un esempio:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

Puoi controllare e modificare questo limite usando il modulo sys, anche se aumentarlo va fatto con cautela:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

La distinzione importante da tenere a mente è che lo stack delle chiamate è una struttura a livello di sistema gestita dall’interprete Python stesso. Non puoi inserire o rimuovere direttamente da esso. Gli stack list, deque e LifoQueue che abbiamo costruito nelle sezioni precedenti sono strutture dati definite dall’utente che vivono nell’heap del tuo programma. Servono a scopi diversi, ma seguono lo stesso principio LIFO.

Uso degli stack monotoni

Uno stack monotono è una variante specializzata in cui gli elementi vengono mantenuti in ordine non decrescente o non crescente (o a volte strettamente crescente/decrescente, a seconda del problema). Ogni volta che inserisci un nuovo elemento, prima rimuovi tutti quelli che violerebbero il vincolo d’ordine. È la chiave per risolvere un’intera classe di problemi di ottimizzazione in tempo lineare.

L’esempio classico è il problema del Next Greater Element: dato un array di interi, trova per ciascun elemento il primo elemento a destra che sia maggiore. Un approccio brute force con cicli annidati è O(n²). Per ogni elemento, scandisci tutto ciò che c’è alla sua destra. Uno stack monotono lo risolve in O(n).

L’intuizione è che attraversi l’array da destra a sinistra, mantenendo uno stack decrescente. Per ogni elemento, rimuovi dallo stack tutto ciò che è minore o uguale ad esso. Quei valori non potranno mai essere il "prossimo maggiore" per alcun elemento futuro a sinistra. 

Ciò che rimane in cima allo stack dopo le rimozioni è la risposta per l’elemento corrente. Poi inserisci l’elemento corrente nello stack. Vediamolo con un esempio di codice. Nota che -1 in questo caso significa che non c’è un numero più grande a destra di quel valore:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

Tracciamo l’esecuzione per vedere come si mantiene la proprietà monotona:

Nota che ogni elemento viene inserito nello stack esattamente una volta e rimosso al massimo una volta nell’intero attraversamento. È per questo che la complessità temporale totale è O(n) nonostante il ciclo while interno. Il numero cumulativo di operazioni di push e pop su tutte le iterazioni non supera mai 2n.

Come accennato, ci sono molti problemi simili che il pattern dello stack monotono accelera da O(n²) a O(n). Tra questi:

• Stock span problem: per ogni prezzo giornaliero, trova quanti giorni consecutivi precedenti hanno avuto un prezzo minore o uguale.
• Rettangolo più grande in un istogramma: trova l’area rettangolare massima che si adatta sotto un grafico a barre (un classico problema da colloquio livello difficile).
• Temperature giornaliere: data una serie di temperature giornaliere, trova dopo quanti giorni avrai una giornata più calda.
• Trapping rainwater: calcola quanta acqua piovana è intrappolata tra barre di altezze diverse.

In ogni caso, l’idea centrale è la stessa: il vincolo monotono ti permette di scartare elementi che non possono più influenzare i risultati futuri, riducendo di fatto lo spazio di ricerca da quadratico a lineare.

Conclusione

Lo stack è una delle prime strutture dati che ogni programmatore impara e una delle ultime di cui smette di trovare nuovi usi, il che ironicamente è l’opposto della sua natura Last-In-First-Out. 

In questo articolo, abbiamo visto come questo vincolo LIFO possa essere utile in molti scenari diversi, dalla validazione di parentesi annidate e la guida delle traversate DFS alla gestione dello stato di annulla/ripristina e all’ottimizzazione di problemi su array con stack monotoni. 

Se c’è un consiglio da portare a casa, è questo: usa collections.deque come implementazione di riferimento per gli stack in Python, a meno che tu non abbia un motivo specifico per non farlo. 

Come passo successivo, ti consiglio il nostro corso su Data Structures and Algorithms in Python.