Was ist ein Stack und wofür wird er verwendet?

Question

Accepted Answer

Ein **Stack** ist eine **LIFO**-Kollektion (Last-In, First-Out): Das zuletzt hinzugefügte Element ist das erste, das entfernt wird. Du arbeitest immer nur mit dem Element an der **Spitze**.

## Operationen

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

## Beispiel

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

Alle Operationen sind **O(1)**, wenn sie durch ein dynamisches Array oder eine verlinkte Liste unterstützt werden.

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

## Häufige Verwendungen

- **Funktionsaufrufe-Stack** — verfolgt aktive Aufrufe und lokale Variablen.
- **Undo/Redo** — jede Aktion pushen; poppen zum Rückgängigmachen.
- **Ausdrucksauswertung / Parsing** — Klammerpaare abgleichen, Infix in Postfix umwandeln.
- **Backtracking und DFS** — merken, wohin zurückgekehrt werden soll.

## Warum es wichtig ist

Der Stack modelliert das Prinzip "mache das Neueste zuerst", das überall von Rekursion bis zu Browser-Zurück-Tasten auftaucht.

Das sofortige Erkennen eines LIFO-Musters deutet auf einen Stack hin und vereinfacht oft ein verworrenes Problem zu wenigen sauberen Push/Pop-Zeilen.