# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/datenstrukturen/README.txt]

STACKS UND QUEUES
=================

Stand: 2026-01-28

ABSTRAKTE DATENTYPEN
--------------------
Stacks und Queues sind eher Verhaltensmuster als Speicherstrukturen. Sie definieren, in welcher REIHENFOLGE Daten verarbeitet werden.

STACK (STAPEL)
--------------
**Prinzip:** LIFO (Last In, First Out).
Wie ein Tellerstapel: Der letzte Teller, den man drauflegt, ist der erste, den man wieder runternimmt.

**Operationen:**
- `push(item)`: Oben drauflegen. O(1).
- `pop()`: Oben wegnehmen. O(1).
- `peek()`: Nur gucken, was oben ist.

**Anwendungen:**
- Rückgängig-Funktion (Undo) in Editoren.
- Call Stack (Funktionsaufrufe in Programmiersprachen).
- Syntax-Parsing (Klammern pruefen `(( ))`).
- Tiefensuche (DFS) in Graphen.

QUEUE (WARTESCHLANGE)
---------------------
**Prinzip:** FIFO (First In, First Out).
Wie eine Schlange im Supermarkt: Wer zuerst kommt, wird zuerst bedient.

**Operationen:**
- `enqueue(item)`: Hinten anstellen. O(1).
- `dequeue()`: Vorne wegnehmen. O(1).

**Anwendungen:**
- Drucker-Warteschlange.
- Task-Scheduling im Betriebssystem.
- Asynchrone Datenverarbeitung (inbox/outbox).
- Breitensuche (BFS) in Graphen.

PYTHON IMPLEMENTIERUNG
----------------------
**Stack:** Einfach eine Liste nutzen.
```python
stack = []
stack.append(1)  # push
item = stack.pop() # pop
```

**Queue:** Liste ist langsam fuer `pop(0)` (O(n)). Nutze `deque`!
```python
from collections import deque
queue = deque()
queue.append(1)    # enqueue
item = queue.popleft() # dequeue O(1)
```

PRIORITY QUEUE
--------------
Eine Sonderform, bei der Elemente nicht nach Zeit, sondern nach Wichtigkeit sortiert werden. (Siehe Heaps).

SIEHE AUCH
----------
wiki/informatik/datenstrukturen/arrays_listen.txt
wiki/informatik/algorithmen/suche.txt
