Lister, stakke (LIFO), køer (FIFO)

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Grundlæggende datastrukturer

Liste (Array): ordnet samling, adgang via index O(1), men søgning O(n).

Stak (Stack) — LIFO (Last In, First Out): sidst tilføjede fjernes først. Som en stabel tallerkener.

```python

stak = []

stak.append(1) # push

stak.append(2)

stak.pop() # 2 (øverste)

```

Bruges til: undo-funktioner, kaldsstak (call stack), HTML-parsing.

Kø (Queue) — FIFO (First In, First Out): først tilføjede fjernes først. Som en kassebutiksrække.

```python

from collections import deque

kø = deque()

kø.append(1) # enqueue

kø.append(2)

kø.popleft() # 1 (forreste)

```

Bruges til: opgavekøer, printerkøer, BFS-algoritmer.

Deque (double-ended queue): kan tilføje/fjerne fra begge ender — O(1).

Læringsmål

• Implementere stak og kø fra bunden og med Python-biblioteker
• Identificere hvornår LIFO vs. FIFO passer til et problem
• Bruge deque til effektiv kø-implementering
• Analysere tids-kompleksiteten for stak/kø-operationer

Sådan kan du arbejde med emnet

• Implementer en stak med push og pop og forklar hvorfor den er LIFO
• Giv et hverdagseksempel på en kø (FIFO) og forklar hvordan enqueue og dequeue fungerer
• Brug en stak til at kontrollere om parenteser i et udtryk er korrekt parret

Træningsforslag

• Implementér en simpel kalkulator med stak til parenteser
• Byg en opgave-processor (task queue) med deque
• Løs LeetCode #20 (Valid Parentheses) med stak