Hvad er en stack, og hvad bruges den til?

Question

Accepted Answer

En **stack** er en **LIFO**-samling (Last-In, First-Out): det sidst indsatte element er det første, der fjernes. Du arbejder kun med elementet øverst på **toppen**.

## Operationer

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

## Eksempel

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

Alle operationer er **O(1)**, når de understøttes af et dynamisk array eller en linket liste.

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

## Almindelige anvendelser

- **Funktionskaldsstakken** — sporer aktive kald og lokale variabler.
- **Undo/redo** — push hver handling; pop for at fortryde.
- **Udtryksevaluering / parsing** — matching af parenteser, konvertering fra infix til postfix.
- **Backtracking og DFS** — huske hvor man skal vende tilbage.

## Hvorfor det er vigtigt

Stacken modellerer "gør det seneste først", som optræder overalt fra rekursion til browserens tilbage-knapper.

At genkende et LIFO-mønster øjeblikkeligt foreslår en stack, og det omdanner ofte et rodekompileret problem til nogle få rene push/pop-linjer.