Vad är en stack och vad används den till?

Question

Accepted Answer

En **stack** är en **LIFO**-samling (Last-In, First-Out): det sista element som push:as är det första som pop:as. Du kan bara komma åt **toppen**.

## Operationer

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

## Exempel

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

Alla operationer är **O(1)** när de backas av en dynamisk array eller länkad lista.

| Operation | Tid |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Vanliga användningsområden

- **Funktionsanropsstacken** — spårar aktiva anrop och lokala variabler.
- **Undo/redo** — push:a varje åtgärd; pop:a för att ångra.
- **Uttrycksutvärdering / parsing** — matchande parenteser, omvandling från infix till postfix.
- **Backtracking & DFS** — komma ihåg var man ska återvända.

## Varför det spelar roll

Stacken modellerar "gör det senaste först", vilket förekommer överallt från rekursion till webbläsarens bakåtknapp.

Att genast känna igen ett LIFO-mönster föreslår en stack, och förvandlar ofta ett invecklat problem till några få rena push/pop-rader.