Czym jest stos i do czego się go używa?

Question

Accepted Answer

**Stos** to kolekcja **LIFO** (Last-In, First-Out): ostatni wciśnięty element jest pierwszym usunięty. Dotykasz tylko **wierzchołka**.

## Operacje

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

## Przykład

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

Wszystkie operacje to **O(1)** jeśli stos jest wspierany przez dynamiczną tablicę lub listę wiązaną.

| Operacja | Czas |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Powszechne zastosowania

- **Function call stack** — śledzi aktywne wywołania i zmienne lokalne.
- **Undo/redo** — push każdej akcji; pop do cofnięcia.
- **Expression evaluation / parsing** — dopasowywanie nawiasów, konwersja z notacji infiksowej na postfiksową.
- **Backtracking & DFS** — pamiętanie, gdzie powrócić.

## Dlaczego to ważne

Stos modeluje "zrób ostatnią rzecz jako pierwszą", co pojawia się wszędzie od rekurencji do przycisku wstecz przeglądarki.

Natychmiastowe rozpoznanie wzorca LIFO sugeruje stos, zamieniając zawiły problem w kilka czystych linii push/pop.