Skip to main content

Deque

A double-ended queue (deque) implementation that efficiently supports insertion and removal of elements at both ends.

Installation​

npm install @msnkr/data-structures

Usage​

import { Deque } from '@msnkr/data-structures';

const deque = new Deque<number>();

API Reference​

Properties​

  • size: number - Number of elements in the deque
  • isEmpty(): boolean - Whether the deque is empty

Methods​

Adding Elements​

// Add to front - O(1)
deque.addFirst(1);

// Add to back - O(1)
deque.addLast(2);
Performance

Add and remove operations at either end are O(1) constant time.

Removing Elements​

// Remove from front - O(1)
const first = deque.removeFirst();

// Remove from back - O(1)
const last = deque.removeLast();

Accessing Elements​

// Peek at front element - O(1)
const first = deque.peekFirst();

// Peek at back element - O(1)
const last = deque.peekLast();

// Check if element exists - O(n)
const exists = deque.contains(1);

Iteration​

// Forward iteration (front to back)
for (const value of deque) {
  console.log(value);
}

// Reverse iteration (back to front)
for (const value of deque.reverseIterator()) {
  console.log(value);
}

Other Operations​

// Remove all elements - O(1)
deque.clear();

// Convert to array - O(n)
const array = deque.toArray();

Examples​

Basic Usage with Both Ends​

const deque = new Deque<number>();

// Add elements at both ends
deque.addFirst(1); // [1]
deque.addLast(2); // [1, 2]
deque.addFirst(0); // [0, 1, 2]

console.log([...deque]); // [0, 1, 2]

Queue Operations (FIFO)​

const queue = new Deque<string>();

// Enqueue
queue.addLast('first');
queue.addLast('second');

// Dequeue
const first = queue.removeFirst(); // "first"
const second = queue.removeFirst(); // "second"

Stack Operations (LIFO)​

const stack = new Deque<number>();

// Push
stack.addFirst(1);
stack.addFirst(2);

// Pop
const top = stack.removeFirst(); // 2

Error Handling​

import { EmptyStructureError } from '@msnkr/data-structures';

try {
  const empty = new Deque<number>();
  empty.removeFirst(); // Throws EmptyStructureError
} catch (error) {
  if (error instanceof EmptyStructureError) {
    console.log('Deque is empty!');
  }
}
Empty Deque

Calling removeFirst(), removeLast(), peekFirst() or peekLast() on an empty deque throws an EmptyStructureError.

Performance Characteristics​

OperationTime ComplexityDescription
addFirst()O(1)Add element to front
addLast()O(1)Add element to back
removeFirst()O(1)Remove element from front
removeLast()O(1)Remove element from back
peekFirst()O(1)View front element
peekLast()O(1)View back element
contains()O(n)Search for element
clear()O(1)Remove all elements
toArray()O(n)Convert to array
Use Cases

Deque is perfect for:

  • Double-ended buffers
  • Implementing both queues and stacks
  • Sliding window algorithms
  • Undo/redo stacks

See Also​

  • Queue - First-In-First-Out (FIFO) queue with O(1) enqueue/dequeue
  • PriorityQueue - Queue with priority-based ordering