Deque (Dobbelt-endet kø)

Lineær

En dobbelt-endet kø der tillader indsættelse og sletning af elementer fra både front og bagende i O(1) tid.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(n) for vilkårlig, O(1) for ender`
Search	`O(n)`
Insertion	`O(1) i begge ender`
Deletion	`O(1) i begge ender`

Beskrivelse

Deque (udtales 'deck', kort for Double-Ended Queue) er en generalisering af både stak- og kødatastrukturerne. Den tillader effektiv indsættelse og sletning fra både front og bagende, hvilket gør den ekstremt alsidig. Du kan bruge en deque som en stak (push/pop fra samme ende), en kø (push til bagende, pop fra front), eller drage fordel af dens fulde funktionalitet ved at operere på begge ender. Deques kan implementeres på flere måder: med en dobbeltlænket liste (simpel men pointer-overhead), cirkulært array (cache-venlig men kan kræve størrelsesændring), eller hybride tilgange. I praksis bruger de fleste standardbiblioteker en chunk-baseret implementering hvor data gemmes i blokke af fast størrelse linket sammen, hvilket kombinerer fordelene ved arrays og lænkede lister. Pythons collections.deque bruger denne tilgang. Deques er nyttige i mange algoritmer: glidende vindue-problemer, palindromtjek, browserhistorik (frem/tilbage), fortryd/gentag-funktionalitet og opgaveplanlægning.

Kode Eksempel

// JavaScript Deque Implementation
class DequeNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  // Tilføj til front
  pushFront(value) {
    const newNode = new DequeNode(value);
    
    if (this.isEmpty()) {
      this.front = this.back = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
    
    this.size++;
  }

  // Tilføj til bagende
  pushBack(value) {
    const newNode = new DequeNode(value);
    
    if (this.isEmpty()) {
      this.front = this.back = newNode;
    } else {
      newNode.prev = this.back;
      this.back.next = newNode;
      this.back = newNode;
    }
    
    this.size++;
  }

  // Fjern fra front
  popFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    
    const value = this.front.value;
    this.front = this.front.next;
    
    if (this.front) {
      this.front.prev = null;
    } else {
      this.back = null;
    }
    
    this.size--;
    return value;
  }

  // Fjern fra bagende
  popBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    
    const value = this.back.value;
    this.back = this.back.prev;
    
    if (this.back) {
      this.back.next = null;
    } else {
      this.front = null;
    }
    
    this.size--;
    return value;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }
}

// Brug eksempler
const deque = new Deque();

// Tilføj til begge ender
deque.pushBack(1);
deque.pushBack(2);
deque.pushFront(0);
console.log('Deque:', deque.toArray()); // [0, 1, 2]

// Fjern fra begge ender
console.log('Pop front:', deque.popFront()); // 0
console.log('Pop back:', deque.popBack()); // 2

Anvendelsesområder

•Glidende vindue-algoritmer
•Browserhistorik (frem/tilbage-navigation)
•Fortryd/gentag-funktionalitet
•Opgaveplanlægning med prioriteter
•Palindromtjek

Fordele

✓O(1) indsættelse/sletning i begge ender
✓Kan bruges som både stak og kø
✓Fleksibel til mange algoritmer
✓Hukommelseseffektiv med array-baseret implementering
✓God cache-lokalitet med cirkulært array

Ulemper

✗Langsom tilfældig adgang O(n) med lænket liste
✗Mere kompleks end simple stakke/køer
✗Array-baseret version kan spilde hukommelse
✗Pointer-overhead med dobbeltlænket liste
✗Ikke optimal til indsættelse/sletning i midten

Eksempler fra den virkelige verden

•Browser frem/tilbage-historiknavigation
•Teksteditor fortryd/gentag-stakke
•Printerkø (kan prioritere fra begge ender)
•Work stealing i trådpuljer
•Opgaveplanlæggere med prioritetsindsættelse

Relaterede strukturer

QueueStackCircular BufferDoubly Linked List