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

It A · STX · A-niveau · Datastrukturer og algoritmer

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

Lineære datastrukturer gemmer elementer i sekvens.

Liste (Array/Dynamic Array): tilfældig adgang O(1), indsæt/slet i slutning O(1) amortiseret, midten O(n). Python's list er dynamisk array.

Stakk (Stack, LIFO): Last In, First Out. Operationer: push (tilføj øverst), pop (fjern øverst), peek (vis øverste). Implementeret med liste: stack = []; stack.append(x); stack.pop(). Anvendelser: undo-funktionalitet, funktionskaldsstakken, DFS-søgning, parentesvalidering.

Kø (Queue, FIFO): First In, First Out. Operationer: enqueue (tilføj bagpå), dequeue (fjern forfra). Python's collections.deque er optimalt (O(1) begge ender). queue.Queue til trådsikker kø. Anvendelser: BFS-søgning, opgavekø (task queue), printerprint-kø, message queue (Kafka, RabbitMQ).

Dobbelt-linket liste (Doubly Linked List): hvert node har next OG prev pointer. O(1) indsæt/slet ved kendte positioner. O(n) søgning. Implementeret manuelt med Node-klasser.

Prioritetskø (Priority Queue/Heap): elementer serviceres efter prioritet, ikke indkomst-rækkefølge. Python: heapq. Min-heap: mindste element rykkes til top.

Læringsmål

• Redegøre for opbygningen af lister, stakke og køer
• Forklare LIFO- og FIFO-princippet
• Implementere en stak eller kø i et programmeringssprog

Sådan kan du arbejde med emnet

• Implementér en stak og en kø i Python uden brug af specialbiblioteker og vis push/pop og enqueue/dequeue
• Beskriv et real-world eksempel, hvor en stak bruges (fx call stack, undo-funktionalitet)
• Forklar, hvad der er tidskompleksiteten (Big-O) for indsættelse og sletning i en stak og en kø

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.