Deque (Double-Ended Queue)

Lineær

En dobbelt-ended kø der tillader insertion og deletion af elementer fra både front og back i O(1) tid.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(n) for arbitrary, O(1) for ends`
Search	`O(n)`
Insertion	`O(1) at both ends`
Deletion	`O(1) at both ends`

Beskrivelse

Deque (udtales 'deck', kort for Double-Ended Queue) er en generalisering af både stack og queue datastrukturerne. Den tillader effektiv insertion og deletion fra både front og back, hvilket gør den ekstremt alsidig. Du kan bruge en deque som en stack (push/pop fra samme ende), en queue (push til back, 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 doubly linked list (simpel men pointer overhead), circular array (cache-friendly men kan kræve resize), eller hybrid approaches. I praksis bruger de fleste standard libraries en chunk-based implementation hvor data gemmes i fixed-size chunks linket sammen, hvilket kombinerer fordelene ved arrays og linked lists. Python's collections.deque bruger denne approach. Deques er nyttige i mange algoritmer: sliding window problems, palindrome checking, browser history (back/forward), undo/redo functionality, og task scheduling.

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;
  }

  // Add to 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++;
  }

  // Add to back
  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++;
  }

  // Remove from 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;
  }

  // Remove from back
  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;
  }

  // Peek at front
  peekFront() {
    return this.front ? this.front.value : undefined;
  }

  // Peek at back
  peekBack() {
    return this.back ? this.back.value : undefined;
  }

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

  getSize() {
    return this.size;
  }

  // Convert to array for display
  toArray() {
    const result = [];
    let current = this.front;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }

  // Clear deque
  clear() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }
}

// Array-based Deque (more memory efficient)
class ArrayDeque {
  constructor(capacity = 16) {
    this.buffer = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.back = 0;
    this.size = 0;
  }

  pushFront(value) {
    if (this.size === this.capacity) {
      this.resize();
    }
    
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.buffer[this.front] = value;
    this.size++;
  }

  pushBack(value) {
    if (this.size === this.capacity) {
      this.resize();
    }
    
    this.buffer[this.back] = value;
    this.back = (this.back + 1) % this.capacity;
    this.size++;
  }

  popFront() {
    if (this.isEmpty()) return undefined;
    
    const value = this.buffer[this.front];
    this.buffer[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return value;
  }

  popBack() {
    if (this.isEmpty()) return undefined;
    
    this.back = (this.back - 1 + this.capacity) % this.capacity;
    const value = this.buffer[this.back];
    this.buffer[this.back] = undefined;
    this.size--;
    return value;
  }

  peekFront() {
    return this.isEmpty() ? undefined : this.buffer[this.front];
  }

  peekBack() {
    const index = (this.back - 1 + this.capacity) % this.capacity;
    return this.isEmpty() ? undefined : this.buffer[index];
  }

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

  resize() {
    const newCapacity = this.capacity * 2;
    const newBuffer = new Array(newCapacity);
    
    for (let i = 0; i < this.size; i++) {
      newBuffer[i] = this.buffer[(this.front + i) % this.capacity];
    }
    
    this.buffer = newBuffer;
    this.capacity = newCapacity;
    this.front = 0;
    this.back = this.size;
  }
}

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

// Add to both ends
deque.pushBack(1);
deque.pushBack(2);
deque.pushFront(0);
console.log('Deque:', deque.toArray()); // [0, 1, 2]

// Remove from both ends
console.log('Pop front:', deque.popFront()); // 0
console.log('Pop back:', deque.popBack()); // 2
console.log('Deque:', deque.toArray()); // [1]

// Sliding window maximum example
function slidingWindowMax(arr, k) {
  const deque = new ArrayDeque();
  const result = [];
  
  for (let i = 0; i < arr.length; i++) {
    // Remove elements outside window
    while (!deque.isEmpty() && deque.peekFront() <= i - k) {
      deque.popFront();
    }
    
    // Remove smaller elements from back
    while (!deque.isEmpty() && arr[deque.peekBack()] < arr[i]) {
      deque.popBack();
    }
    
    deque.pushBack(i);
    
    if (i >= k - 1) {
      result.push(arr[deque.peekFront()]);
    }
  }
  
  return result;
}

console.log('Sliding window max:', slidingWindowMax([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

Anvendelsesområder

•Sliding window algorithms
•Browser history (back/forward navigation)
•Undo/redo functionality
•Task scheduling med prioriteter
•Palindrome checking

Fordele

✓O(1) insertion/deletion på begge ender
✓Kan bruges som både stack og queue
✓Fleksibel til mange algoritmer
✓Memory efficient med array-based implementation
✓God cache locality med circular array

Ulemper

✗Langsom random access O(n) med linked list
✗Mere kompleks end simple stack/queue
✗Array-based version kan waste memory
✗Pointer overhead med doubly linked list
✗Ikke optimal til middle insertions/deletions

Eksempler fra den virkelige verden

•Browser back/forward history navigation
•Text editor undo/redo stacks
•Print spooler (kan prioritere fra begge ender)
•Work stealing i thread pools
•Task schedulers med priority insertion

Relaterede strukturer

QueueStackCircular BufferDoubly Linked List