Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Double-Ended Queues

Explore the concept of double-ended queues, or deques, which allow insertion and deletion at both the front and rear. Understand their JavaScript implementation and key operations, such as append, pop, and peek, all with constant time complexity. Learn how deques differ from stacks and queues, and discover their practical uses in algorithms like sliding window maximum and undo/redo functionality.

We'll cover the following...

A deque stands for a double-ended queue. It is a more flexible version of a queue that allows insertion and deletion from both the front and the rear.

In a normal queue, insertion happens only at the rear and deletion happens only at the front. In a deque, both ends are fully active.

Visualization of a deque
Visualization of a deque

This makes the deque a generalization that can behave like a queue, a stack, or something in between, depending on how it is used.

A deque is useful when a problem needs controlled access to both ends of the structure. It appears in sliding window problems, palindrome checking, scheduling, and caching systems.

Example

To understand how a deque works, consider the following example. If a deque currently contains:

A deque with 3 elements
A deque with 3 elements

After inserting 88 at the front, the deque becomes:

Inserting an element at the front of a deque
Inserting an element at the front of a deque

After inserting 91 at the rear, the deque becomes:

Inserting an element at the rear of a deque
Inserting an element at the rear of a deque

After removing 88 from the front, the deque becomes:

Removing an element from the front of a deque
Removing an element from the front of a deque

After removing 91 from the rear, the deque becomes:

Removing an element from the rear of a deque
Removing an element from the rear of a deque

This two-sided behavior is what makes the deque more versatile than a regular queue.

JavaScript implementation

Below is the JavaScript implementation of the deque. Here's how to use it:

Javascript (babel-node)
class Deque {
    constructor() {
        this.items = [];
    }
    // Insert at rear
    append(value) {
        this.items.push(value);
    }
    // Insert at front
    appendLeft(value) {
        this.items.unshift(value);
    }
    // Delete from rear
    pop() {
        return this.items.pop();
    }
    // Delete from front
    popLeft() {
        return this.items.shift();
    }
    // Peek at front
    front() {
        return this.items[0];
    }
    // Peek at rear
    rear() {
        return this.items[this.items.length - 1];
    }
    // Check if empty
    isEmpty() {
        return this.items.length === 0;
    }
    // Get size
    size() {
        return this.items.length;
    }
}
// Create an empty deque
const dq = new Deque();
// Insert at rear
dq.append(10);
dq.append(20);
dq.append(30);
// Insert at front
dq.appendLeft(5);
// Delete from rear
dq.pop();
// Delete from front
dq.popLeft();
// Peek at front
const frontElement = dq.front();
// Peek at rear
const rearElement = dq.rear();
// Check if empty
const isEmpty = dq.isEmpty();
// Get size
const size = dq.size();
console.log("Deque:", dq.items);
console.log("Front element:", frontElement);
console.log("Rear element:", rearElement);
console.log("Is empty:", isEmpty);
console.log("Size:", size);
Implementation of a deque

Explanation

To understand the above code, consider the following breakdown of how each function operates in the deque class:

  • Lines 7–9 (Inserting at the rear): The append() method adds elements to the rear (right end) of the deque. Each call is an O(1)O(1) ...