Stack

Lo stack (in italiano spesso chiamato “pila”) è una delle strutture dati più comuni negli algoritmi. Quando si utilizza uno stack, gli elementi inseriti per ultimi saranno i primi a essere rimossi. È come impilare dei piatti: il piatto in cima è l’unico che si possa prendere, finché non si rimuovono tutti quelli sopra di esso.

Uno stack può essere impiegato in molte situazioni reali. Ad esempio, quando si consultano dei siti web in un browser, facendo clic sul pulsante Indietro si torna alla pagina precedente. La cronologia delle pagine potrebbe essere memorizzata in uno stack: non appena si preme Indietro si passa all’elemento in cima allo stack. Se si preme nuovamente Indietro, la pagina in cima viene rimossa e si passa a quella sottostante.

1. Utilizzando list - l’elemento in cima allo stack sarà l’ultimo della lista. Possiamo aggiungere con append, rimuovere con pop e ottenere l’elemento in cima con [-1].

2. Utilizzando deque da collections - supporta l’aggiunta e la rimozione di elementi sia all’inizio sia alla fine.

3. LifoQueue da queue - coda Last-In-First-Out, che rappresenta esattamente il comportamento di uno stack.

from queue import LifoQueue
stack = LifoQueue()

# push
stack.put(1)
stack.put(2)
stack.put(3)

# pop
print(stack.get())      # stampa 3
print(stack.get())      # stampa 2

# peek
print(stack.queue[-1])  # stampa 1
print(stack.empty())    # controlla se è vuoto -> stampa False

# Utilizzando una semplice list
stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
print(stack.pop())      # stampa 3
print(stack.pop())      # stampa 2

# peek
print(stack[-1])        # stampa 1
print(len(stack) == 0)  # controlla se è vuoto -> stampa False

Challenge: Check if the sequence of brackets is valid

Input

Output

Esempi