Kø

Lineær

En FIFO (First In First Out) datastruktur hvor det første element tilføjet er det første der fjernes.

Kompleksitet

Operation	Tidskompleksitet
access	`O(n)`
search	`O(n)`
insertion	`O(1)`
deletion	`O(1)`

Beskrivelse

En kø er en datastruktur der følger First In First Out (FIFO) princippet - det element der først kom ind i køen er det første der kommer ud. Forestil dig en kø i supermarkedet hvor den første kunde i køen bliver betjent først. Køen har to primære operationer: enqueue (tilføj element til enden) og dequeue (fjern element fra fronten). Ligesom stakke findes peek/front (se første element) og isEmpty. Køer kan implementeres med arrays, lænkede lister eller cirkulære buffere. Der findes også varianter som prioritetskøer hvor elementer har prioritet, og Deque (dobbelt-endet kø) hvor man kan tilføje/fjerne fra begge ender. Køer er fundamentale i planlægning, buffering og bredde-først-søgningsalgoritmer. De sikrer fair behandling og ordnet processering af opgaver.

Kode Eksempel

// JavaScript Queue implementation
class Queue {
  constructor() {
    this.items = [];
  }

  // Tilføj element til enden
  enqueue(element) {
    this.items.push(element);
  }

  // Fjern og returner første element
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.shift();
  }

  // Se første element
  front() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[0];
  }

  // Tjek om køen er tom
  isEmpty() {
    return this.items.length === 0;
  }

  // Få størrelsen
  size() {
    return this.items.length;
  }
}

// Eksempel: Opgavekø
class TaskQueue {
  constructor() {
    this.queue = new Queue();
    this.processing = false;
  }

  async addTask(task) {
    this.queue.enqueue(task);
    if (!this.processing) {
      await this.processTasks();
    }
  }

  async processTasks() {
    this.processing = true;
    while (!this.queue.isEmpty()) {
      const task = this.queue.dequeue();
      await task();
    }
    this.processing = false;
  }
}

Anvendelsesområder

-Udskriftsjob-planlægning i printere
-CPU-opgaveplanlægning i styresystemer
-Bredde-først-søgning i grafer og træer
-Beskedkøer i distribuerede systemer
-Forespørgselshåndtering i webservere

Fordele

+Fair FIFO-rækkefølge af elementer
+O(1) tid for enqueue og dequeue
+Simple og intuitive operationer
+Perfekt til sekventiel processering
+Forhindrer kapløbssituationer

Ulemper

-Begrænset adgang (kun front og bagende)
-Array-implementering kan være ineffektiv
-Ingen tilfældig adgang
-Køer med fast størrelse kan overløbe
-Ikke velegnet til prioritering (brug prioritetskø)

Eksempler fra den virkelige verden

-Kø ved McDonalds drive-through
-Udskriftsjob sendt til printer
-Kundeservice call center
-Pakker på samlebånd
-Passagerer der boarder fly

Relaterede strukturer

Priority QueueDequeCircular QueueBlocking Queue