Kö (datastruktur): definition, FIFO, enqueue/dequeue och prioriterad kö

Lär dig kö-datastruktur: definition, FIFO-principen, enqueue/dequeue-operationer och prioriterade köer — tydliga exempel, användningsområden och praktiska tips för utvecklare.

Inom datavetenskap är en kö en datastruktur som används för att lagra objekt i väntan på att bli behandlade. Den grundläggande principen är att objekt behandlas i den ordning de kom in — först in, först ut (FIFO). Följande grundoperationer förekommer vanligen:

• Enqueue (eller push): lägger till ett objekt längst bak i kön.
• Dequeue (eller pop): tar bort och returnerar objektet längst fram i kön.
• Peek (eller front): tittar på objektet längst fram utan att ta bort det.

Poster som befinner sig mellan det första och sista elementet i kön är normalt inte direkt åtkomliga utan att först ta bort de föregående elementen.

Flera varianter och egenskaper

• FIFO: Standardkön följer FIFO-ordning — det första elementet som läggs in är det första som tas ut.
• Begränsade (bounded) vs obegränsade (unbounded) köer: En begränsad kö har en maximal kapacitet och kan bli full (översvämning), medan en obegränsad kö växer dynamiskt tills minnet tar slut.
• Dubbeländad kö (deque): tillåter insättning och borttagning i båda ändar (front och back).
• Trådsäkerhet: i flertrådade miljöer används ofta synkroniserade eller låsfria (lock-free) köer och blocking queues som väntar när kön är tom eller full.

Implementeringar

Vanliga sätt att implementera en kö är:

• Array (cirkulär buffert): en fast storlek med två index för front och rear. Ger O(1) för både enqueue och dequeue om man använder cirkulär logik (ingen förskjutning av element behövs).
• Länkad lista: håller pekare till både första och sista noden. Enqueue och dequeue kan utföras i O(1). Lämplig för dynamisk storlek.
• Standardbibliotek: de flesta språk har färdiga kötyper (t.ex. Queue i Java, collections.deque i Python) som hanterar detaljer som synkronisering och minneshantering.

Komplexitet

• Enkel kö (cirkulär buffert eller länkad lista): enqueue och dequeue i O(1) tid.
• Array utan cirkulär logik kan ge O(n) för dequeue om alla element måste förskjutas.

Prioriterad kö

En prioriterad kö skiljer sig från en vanlig FIFO-kö genom att varje objekt har en associerad prioritet (eller vikt). Vid uttag (dequeue) tas det element ut som har högst (eller lägst, beroende på implementation) prioritet, inte nödvändigtvis det som kom in först. Prioriterade köer är inte strikt FIFO.

Vanliga implementationer av prioriterade köer:

• Binärt heap: vanlig implementation med O(log n) för insertion och O(log n) för att ta bort högsta prioritets-element.
• Fibonacci-heap: erbjuder amortiserade förbättringar för vissa operationer (t.ex. decrease-key) men används mer sällan i praktiska bibliotek.
• Ordning och stabilitet: vissa prioriterade köer kan vara stabila (bevarar insättningsordningen för element med lika prioritet), andra inte.

Användningsområden

• Schemaläggning av jobb och processer (t.ex. i operativsystem eller batchsystem).
• Bredetssökning (BFS) i grafer.
• Buffring av data i nätverk och I/O (köer mellan producent och konsument).
• Prioriterade köer används för händelsehantering, Dijkstras algoritm och andra algoritmer som behöver snabb åtkomst till det bästa elementet.

Trådsäkerhet och blockering

I flertrådade system används ofta specialiserade kötyper:

• Blocking queue: en tråd som försöker dequeue från en tom kö väntar (blockeras) tills ett element finns; motsvarande kan en tråd som försöker enqueue i en full begränsad kö blockeras tills utrymme finns.
• Non-blocking / lock-free köer: avancerade implementationer som använder atomiska operationer för att undvika lås och minska lås-relaterade problem.

Exempel (pseudokod)

En enkel kö med länkad lista — pseudokod:

• Enqueue(value): skapa ny nod; tail.next = nod; tail = nod; om queue.empty: head = tail.
• Dequeue(): om queue.empty returnera null; value = head.value; head = head.next; om head == null: tail = null; returnera value.

Praktiska tips

• Använd cirkulär buffert eller språkets inbyggda kö för bästa prestanda när enkel FIFO-behavior krävs.
• Välj prioriterad kö (heap) när åtkomst till högst prioritet är viktigare än insättningsordningen.
• I samtidiga program, använd väl testade biblioteksklasser (t.ex. thread-safe queues) istället för att implementera egen synkronisering om möjligt.

Sammanfattningsvis är kön en enkel men mycket användbar datastruktur med många varianter — från enkla FIFO-köer till komplexa prioriterade och trådsäkra köer — som används i allt från algoritmer till systemprogrammering.

Sök med bokstav