Hva er en stack og hva brukes den til?

Question

Accepted Answer

En **stack** er en **LIFO** (Last-In, First-Out) samling: det sist innlagte elementet blir det første som fjernes. Du berører bare **toppen**.

## Operasjoner

```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 operasjoner er **O(1)** når de støttes av en dynamisk array eller linked list.

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

## Vanlige bruksområder

- **Function call stack** — sporer aktive anrop og lokale variabler.
- **Undo/redo** — push hver handling; pop for å angre.
- **Expression evaluation / parsing** — matchende parenteser, konvertering fra infix til postfix.
- **Backtracking & DFS** — husk hvor du skal returnere.

## Hvorfor det betyr noe

Stacken modellerer "gjør det mest nylige først", noe som dukker opp overalt fra rekursjon til browserens tilbake-knapp.

Å gjenkjenne et LIFO-mønster med en gang foreslår en stack, og gjør ofte et rotete problem til noen få rene push/pop-linjer.