Algoritmi Python

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).

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalla pila di piatti al codice
stack.append("third")🍽️ Metti un piatto in cima
stack.pop()⬆️ Togli il piatto in cima
stack[-1]👀 Guarda il piatto in cima senza prenderlo
stack📚 I piatti ancora sulla pila
L'ultimo che entra è il primo che esce: si raggiunge solo la cima.
In una frase

Una pila è una collezione last-in, first-out (LIFO): gli elementi si aggiungono e si tolgono solo in cima.

Punti chiave

  1. stack.append(...) mette un elemento in cima, cioè in fondo alla lista.
  2. stack.pop() toglie e restituisce l'elemento in cima, qui "third".
  3. stack[-1] legge l'elemento in cima senza toglierlo.
  4. Sia append sia pop lavorano 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

Esegui codice →
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")

print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Fare pop su una pila vuota

pop() su una lista vuota solleva IndexError.

Problema
item = stack.pop()
Correzione
if stack:
    item = stack.pop()

Usare l'inizio della lista come cima

insert(0, x) e pop(0) spostano ogni elemento, il che è lento.

Problema
stack.insert(0, item)
stack.pop(0)
Correzione
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.

Tutte le sfide