Double Ended Queue: More Than Just a Queue

Alright, so I was grinding some LeetCode problems (as one does) and in one of a problem I saw this pattern—Double Ended Queue or Deque (pronounced "deck," not "dee-queue," learned that the hard way 😅). At first, I was like, "Why not just use a normal queue or a stack?" But turns out, deques are game changer for certain problems. So, let’s break it down—what it is, how to implement it (in TypeScript, you can use your fav language), and where it uses in DSA.

What’s a Deque?

A Deque is like a queue, but with some more powers. In a normal queue, you can only add to the back (enqueue) and remove from the front (dequeue). But a deque lets you add/remove from both ends. Think of it as a hybrid between a stack (LIFO) and a queue (FIFO).

Operations:

• pushFront(x): Add x to the front.
• pushBack(x): Add x to the back.
• popFront(): Remove from the front.
• popBack(): Remove from the back.
• peekFront(): Get front element.
• peekBack(): Get back element.

Implementing a Deque in TypeScript

class DequeNode<T> {
    value: T;
    next: DequeNode<T> | null;
    prev: DequeNode<T> | null;

    constructor(value: T) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class Deque<T> {
    private front: DequeNode<T> | null;
    private back: DequeNode<T> | null;
    private size: number;

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

    pushFront(value: T): void {
        const newNode = new DequeNode(value);
        if (this.size === 0) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.next = this.front;
            this.front!.prev = newNode;
            this.front = newNode;
        }
        this.size++;
    }

    pushBack(value: T): void {
        const newNode = new DequeNode(value);
        if (this.size === 0) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.prev = this.back;
            this.back!.next = newNode;
            this.back = newNode;
        }
        this.size++;
    }

    popFront(): T | null {
        if (this.size === 0) return null;
        const value = this.front!.value;
        this.front = this.front!.next;
        if (this.front) {
            this.front.prev = null;
        } else {
            this.back = null; // deque is now empty
        }
        this.size--;
        return value;
    }

    popBack(): T | null {
        if (this.size === 0) return null;
        const value = this.back!.value;
        this.back = this.back!.prev;
        if (this.back) {
            this.back.next = null;
        } else {
            this.front = null; // deque is now empty
        }
        this.size--;
        return value;
    }

    peekFront(): T | null {
        return this.front?.value ?? null;
    }

    peekBack(): T | null {
        return this.back?.value ?? null;
    }

    getSize(): number {
        return this.size;
    }

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

Why Not Just Use an Array?

In JS/TS, arrays already support push, pop, shift, and unshift, so you could use an array as a deque. But shift and unshift are O(n) operations because they require reindexing. A proper deque implementation (like above) must does everything in O(1).

Uses in DSA

Lets see the question where I have found this pattern use full.

Sliding Window Maximum (LeetCode 239)

Alright, here’s where deques shine. The problem:

Given an array nums and a window size k, return an array of the maximum in each sliding window.

Brute Force (O(n*k)):

For each window, scan all k elements to find the max. Works, but slow for large n.

Optimal (O(n)):

Use a monotonic deque to keep track of potential max candidates.

How it works:

• The deque stores indices (not values) in decreasing order of their values.
• For each new element, remove indices from the back if their values are ≤ current element (since they’ll never be the max in any future window).
• The front of the deque is always the max of the current window.
• Remove elements from the front if they’re outside the current window.

TypeScript Solution:

function maxSlidingWindow(nums: number[], k: number): number[] {
    const result: number[] = [];
    const deque: number[] = []; // stores indices

    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside the current window
        if (deque.length > 0 && deque[0] === i - k) {
            deque.shift();
        }

        // Remove indices from the back whose values are <= nums[i]
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        // The front is the max for the current window
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

Why This Works:

• The deque maintains elements in decreasing order, so the front is always the max.
• By removing smaller elements before adding new ones, we ensure only relevant candidates remain.
• Each element is added and removed at most once, so O(n) time.

Other Uses of Deque:

• Palindrome Checker: Push front and back, then compare.
• BFS with Level Tracking: Sometimes used in tree traversals.
• Undo/Redo Operations: Deques can manage history stacks.

Final Thoughts

Deques are super versatile and powerful data structure. They’re not just a fancy queue—they’re a powerhouse for sliding window problems and other scenarios where you need O(1) ops at both ends.

Next time you see a problem with sliding windows or max/min in subarrays, think DEQUE! 🚀

Like this breakdown?
👉 Follow for more DSA deep-dives!
👉 Drop a comment if anything you want to share.
👉 Share with your coding buddy who’s stuck on the problem that can be solved using this.