Kø (datastruktur) — definition, operationer og prioritetskø

Kø (datastruktur): lær definitionen, nøgleoperationer (enqueue, dequeue, peek), begrænsninger og prioritetskøens principper med klare eksempler og anvendelser.

Inden for datalogi er en kø en datastruktur, der bruges til at opbevare elementer i den rækkefølge, de ankommer, indtil de skal behandles. Køer følger normalt princippet FIFO (First In, First Out): det element, der kommer ind først, bliver også behandlet først.

• Enqueue (eller push): tilføj et element bagest i køen.
• Dequeue (eller pop): fjern og returnér elementet, der står forrest i køen.
• Peek (eller front): se på elementet forrest i køen uden at fjerne det.
• isEmpty / size: tjek om køen er tom eller returnér antallet af elementer.

Som udgangspunkt er elementer, der befinder sig mellem det første og det sidste element i køen, ikke direkte tilgængelige uden at fjerne de foranstående elementer.

Typiske implementeringer

• Bundet array (cirkulær buffer): bruger en fast størrelse buffer med to indekser (front og rear). En dequeue/enqueue kan udføres i O(1). Begrænsningen er fast kapacitet, med mindre man vælger at udvide bufferen dynamisk.
• Dynamisk array: man kan bruge et array og en startindeks for at undgå at flytte elementer. Enkelt implementeret er det ofte amortiseret O(1) for enqueue, O(1) for peek/dequeue hvis man håndterer cirkulær indekslogik korrekt; ellers kan naive skift være O(n).
• Singly linked list med head/tail-pointere: både enqueue og dequeue er O(1), man tilføjer bagtil og fjerner forrest uden at flytte andre elementer.
• Persistent/funktionelle køer: i rent funktionelle sprog bruges ofte to lister (forrest og bagest) for at opnå amortiseret O(1) uden mutation.

Prioritetskø

En prioritetskø er en specialisering af køen, hvor hvert element har en tilknyttet prioritet (vægt). Fjernelse sker normalt ikke efter ankomstrækkefølge, men efter prioritet — typisk fjernes elementet med højst (eller lavest) prioritet først.

• Implementeringer: binære heaps (binær-heap) er almindelige og giver O(log n) for insert (enqueue) og O(log n) for remove-min/remove-max (dequeue). Andre strukturer som binomial heaps, Fibonacci heaps eller pairing heaps kan give bedre amortiserede eller specifikke operationstider (fx hurtigere decrease-key).
• Stabilitet: standard heaps bevarer ikke nødvendigvis FIFO-orden for elementer med samme prioritet. Hvis stabilitet er ønsket (at elementer med samme prioritet behandles i den rækkefølge, de ankom), kan man gemme et ekstra tidsstempel eller sekvensnummer sammen med hvert element.

Varianter og egenskaber

• Dobbelt-ended queue (deque): tillader indsættelse og fjernelse i begge ender (front og back).
• Begrænsede vs. ubegrænsede køer: begrænsede køer har en fast kapacitet (bruges i realtids- eller indlejrede systemer); ubegrænsede køer vokser dynamisk efter behov.
• Blokerende køer (concurrent/producer–consumer): i samtidige miljøer findes synkroniserede eller trådsikre køer, som kan blokere producenten, når køen er fuld, eller blokere forbrugeren, når køen er tom (f.eks. "blocking queue").
• Cirkulær kø: implementering hvor bufferplads genbruges ved at lade indeks "wrappe rundt", hvilket undgår unødvendig kopiering.

Tids- og pladscomplexitet (typiske tilfælde)

• Enqueue: O(1) (amortiseret eller konstant afhængigt af implementering).
• Dequeue: O(1).
• Peek: O(1).
• Prioritetskø (heap): insert og remove: O(log n).
• Plads: O(n) for at holde n elementer.

Anvendelser

• Opgavestyring og jobkøer (fx printkøer, baggrundsjob).
• Scheduling i operativsystemer (task scheduling, CPU-køer, I/O køer).
• Bredde-først-søgning (BFS) i grafer.
• Netværkspakker og køstyring i routere.
• Event- og beskedbehandling i distribuerede systemer (message queues).
• Prioriterede opgaver via prioritetskøer (fx Dijkstras algoritme bruger en prioritetskø).

Fejlhåndtering og kanttilfælde

• Dequeue på en tom kø bør enten kaste en fejl/undtagelse eller returnere en særlig værdi/null afhængigt af API-designet.
• Kapacitetsgrænser: ved begrænsede køer skal enqueue fejle eller blokere, når køen er fuld.
• Samtidighed: ved flertrådede systemer er korrekt synkronisering nødvendig for at undgå race-conditions eller tabte elementer.

Samlet set er køer simple men centrale datastrukturer i programmering og systemdesign. Valget af implementering afhænger af krav til ydeevne, hukommelse, stabilitet og samtidighed.

Søg efter bogstav