Queue

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 Queue 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. Queue har to primære operationer: enqueue (tilføj element til enden) og dequeue (fjern element fra fronten). Ligesom stack findes peek/front (se første element) og isEmpty. Queues kan implementeres med arrays, linked lists eller circular buffers. Der findes også varianter som Priority Queue hvor elementer har prioritet, og Deque (double-ended queue) hvor man kan tilføje/fjerne fra begge ender. Queues er fundamentale i scheduling, buffering og breadth-first search algoritmer. 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];
  }

  // Check om queue er tom
  isEmpty() {
    return this.items.length === 0;
  }

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

// Eksempel: Task Queue
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

•Print job scheduling i printere
•CPU task scheduling i operating systems
•Breadth-first search i graphs og trees
•Message queues i distributed systems
•Request handling i web servers

Fordele

✓Fair FIFO ordering af elementer
✓O(1) tid for enqueue og dequeue
✓Simple og intuitive operationer
✓Perfekt til sequential processing
✓Forhindrer race conditions

Ulemper

✗Begrænset adgang (kun front og rear)
✗Array implementation kan være ineffektiv
✗Ingen random access
✗Fixed size queues kan overflow
✗Ikke velegnet til prioritering (brug priority queue)

Eksempler fra den virkelige verden

•Kø ved McDonalds drive-through
•Print jobs sendt til printer
•Kundeservice call center
•Pakker på samlebånd
•Passagerer boarding på fly

Relaterede strukturer

Priority QueueDequeCircular QueueBlocking Queue