Che cos'è uno stack e a cosa serve?

Question

Accepted Answer

Uno **stack** è una collezione **LIFO** (Last-In, First-Out): l'ultimo elemento inserito è il primo a essere rimosso. Tocchi sempre e solo il **top**.

## Operazioni

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## Esempio

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

Tutte le operazioni sono **O(1)** quando supportate da un array dinamico o da una linked list.

| Operazione | Tempo |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Usi comuni

- **Function call stack** — traccia le chiamate attive e le variabili locali.
- **Undo/redo** — inserisci ogni azione; estrai per annullare.
- **Valutazione / parsing di espressioni** — corrispondenza di parentesi, conversione da infix a postfix.
- **Backtracking e DFS** — ricorda dove tornare.

## Perché è importante

Lo stack modella "fai prima la cosa più recente", che appare ovunque da ricorsione a pulsanti back del browser.

Riconoscere un pattern LIFO suggerisce istantaneamente uno stack, trasformando spesso un problema complicato in poche righe pulite di push/pop.