La struttura dati pila (stack) in Python
In questa lezione userai una lista Python per implementare le operazioni di base di una pila: inserire (push), estrarre (pop) e guardare l'elemento in cima (peek).
Introduzione
Il problema
I pulsanti annulla, il pulsante indietro del browser e il controllo delle parentesi devono tutti ricordare degli elementi e riprendere per primo il più recente. Una pila è la struttura dati costruita esattamente per questo.
Immaginalo così
Una pila è come una pila di piatti in mensa. Metti i piatti nuovi in cima e prendi i piatti dalla cima. L'ultimo piatto aggiunto è il primo usato, e non puoi tirare fuori un piatto dal mezzo.
stack.append("third")🍽️ Metti un piatto in cimastack.pop()⬆️ Togli il piatto in cimastack[-1]👀 Guarda il piatto in cima senza prenderlostack📚 I piatti ancora sulla pilaUna pila è una collezione last-in, first-out (LIFO): gli elementi si aggiungono e si tolgono solo in cima.
Punti chiave
stack.append(...)mette un elemento in cima, cioè in fondo alla lista.stack.pop()toglie e restituisce l'elemento in cima, qui"third".stack[-1]legge l'elemento in cima senza toglierlo.- Sia
appendsiapoplavorano in fondo alla lista, quindi sono veloci.
Quando si usa?
- Cronologie di annulla e ripeti.
- Controllare le parentesi e analizzare espressioni.
- Ricerca in profondità e backtracking senza ricorsione.
Quando non serve
- Gli elementi devono uscire nell'ordine in cui sono arrivati: quella è una coda.
- Ti servono elementi dal mezzo o per posizione: va meglio una lista normale o un'altra struttura.
Guarda come funziona
Fai push e pop per vedere che l'ultimo elemento entrato è sempre il primo a uscire.
Codice di esempio
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Risultato dell'esecuzione
popped: third
top: second
stack: ['first', 'second']
Spiegazione del codice
Il metodo append() mette un elemento in cima alla pila, e pop() rimuove e restituisce l'elemento in cima, per questo "third" esce per primo. stack[-1] permette di guardare l'elemento in cima senza rimuoverlo. Le operazioni append() e pop() in fondo alla lista hanno complessità media O(1).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Fare pop su una pila vuota
pop() su una lista vuota solleva IndexError.
item = stack.pop()
if stack:
item = stack.pop()
Usare l'inizio della lista come cima
insert(0, x) e pop(0) spostano ogni elemento, il che è lento.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Media
- Mini Stack-Language Interpreter Evaluate a small stack language. Difficile