Deques

Deques

What if you could add and remove from both ends of a queue? Welcome to deques (pronounced "decks") - short for double-ended queues. They're like queues with superpowers - flexible on both sides.

Think of a deque like a train with doors on both ends. Passengers can board or exit from either side, making operations much more flexible than a single-entry queue. No bottlenecks here.

Deques combine the best of both worlds - they can function as stacks when needed, but also support efficient operations at both ends. It's like having a Swiss Army knife for data structures.

Core Operations

Deques support four main operations: addFront, addBack, removeFront, and removeBack. All of these should be O(1) for a good deque implementation. That's the beauty of it - maximum flexibility with no performance penalty.

In JavaScript, you can simulate a deque using an array with push(), pop(), unshift(), and shift(). Each method gives you access to both ends of the data structure. It's surprisingly versatile.

const deque = [];
deque.push("back1");
deque.unshift("front1");
deque.push("back2");
deque.pop();
deque.shift();
console.log(deque);

Types of Deques

There are two main types: input-restricted deques (only remove from both ends, add to one) and output-restricted deques (only add to both ends, remove from one). Regular deques allow all four operations freely.

The restrictions matter when you're designing specific algorithms. Sometimes you only need to add from one end but remove from both, or vice versa. Knowing the types helps you pick the right tool.

class Deque {
  constructor() {
    this.items = [];
  }
  addFront(item) { this.items.unshift(item); }
  addBack(item) { this.items.push(item); }
  removeFront() { return this.items.shift(); }
  removeBack() { return this.items.pop(); }
}

Use Cases

Deques shine in sliding window problems - imagine finding the maximum element in every window of size k. They're also used in palindrome checking, undo/redo systems, and implementing both stacks and queues with the same data structure.

Another cool use is in algorithms like the sliding window maximum. You maintain a deque of indices, and as the window slides, you remove elements that are no longer useful. It's elegant and efficient.