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