Deque (Double-Ended) - Learning Module

Loading content...

0/276

Deque as a Generalization of Stack and Queue

The Unifying Abstraction

In mathematics and computer science, the most elegant structures are often those that generalize simpler concepts. A square is a special rectangle. A rectangle is a special parallelogram. This hierarchy of specialization reveals deep structural relationships.

The deque stands in exactly this relationship to stacks and queues. It's not merely "yet another data structure"—it's the common generalization that subsumes both. Understanding this relationship transforms how you think about linear data structures and when to deploy each one.

What You Will Learn

By the end of this page, you'll understand how stacks and queues are restricted deques, why this relationship matters for algorithm design, how to implement stacks and queues using deques, and when to use the full deque versus its restrictions.

The Generalization Hierarchy

Let's formalize the relationship between deques, stacks, and queues using the concept of restriction:

Definition: Restriction

A data structure A is a restriction of data structure B if:

A's operations are a subset of B's operations
A can be implemented by using only certain operations of B
A imposes additional constraints that B doesn't require

The Hierarchy:

                    ┌─────────────────┐
                    │      DEQUE      │
                    │  (full access)  │
                    └────────┬────────┘
                             │
              ┌──────────────┴──────────────┐
              │                             │
              ▼                             ▼
    ┌─────────────────┐           ┌─────────────────┐
    │      STACK      │           │      QUEUE      │
    │ (one end only)  │           │ (FIFO: opposite │
    │                 │           │     ends)       │
    └─────────────────┘           └─────────────────┘

How Stacks and Queues Restrict the Deque
Data Structure	Insert Operations Used	Remove Operations Used	Constraint
Full Deque	addFront, addRear	removeFront, removeRear	None
Stack	addRear only (or addFront only)	removeRear only (or removeFront only)	Same end for insert and remove
Queue	addRear only	removeFront only	Opposite ends for insert and remove
Output-Restricted Deque	addFront, addRear	removeFront only	One removal end
Input-Restricted Deque	addRear only	removeFront, removeRear	One insertion end

The Power of Generalization

Once you implement a deque correctly, you get stack and queue implementations for free. You also get the flexibility to morph between behaviors at runtime—something impossible with dedicated stack or queue implementations.

Stack as a Restricted Deque

A stack enforces Last-In, First-Out (LIFO) discipline: the most recently added element is always the first to be removed. This behavior emerges naturally when we restrict a deque to use only one end for both insertion and removal.

Stack = Deque with Single-End Restriction

Stack Operation	Deque Equivalent	Alternative
push(x)	addRear(x)	addFront(x)
pop()	removeRear()	removeFront()
peek()/top()	peekRear()	peekFront()
isEmpty()	isEmpty()	isEmpty()
size()	size()	size()

The key constraint: Both insertion and removal happen at the same end. Whether that's the rear or front is arbitrary—LIFO behavior results either way.

stack_via_deque
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Stack implementation using a Deque as the underlying structure.
 * 
 * This demonstrates that a stack is merely a restricted deque.
 * We choose to use the rear end for all operations, but front
 * would work equally well.
 */
class StackViaDeque<T> {
    private deque: Deque<T>;
 
    constructor() {
        this.deque = new Deque<T>();
    }
 
    /**
     * Push an element onto the stack.
     * Time Complexity: O(1)
     */
    push(element: T): void {
        this.deque.addRear(element);
    }
 
    /**
     * Pop and return the top element.
     * Throws if stack is empty.
     * Time Complexity: O(1)
     */
    pop(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot pop from empty stack");
        }
        return this.deque.removeRear();
    }
 
    /**
     * View the top element without removing it.
     * Throws if stack is empty.
     * Time Complexity: O(1)
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Stack is empty: cannot peek");
        }
        return this.deque.peekRear();
    }
 
    /**
     * Check if the stack is empty.
     * Time Complexity: O(1)
     */
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    /**
     * Return the number of elements in the stack.
     * Time Complexity: O(1)
     */
    size(): number {
        return this.deque.size();
    }
}
 
// Usage example
const stack = new StackViaDeque<string>();
stack.push("first");
stack.push("second");
stack.push("third");
console.log(stack.pop());   // "third"  (LIFO)
console.log(stack.peek());  // "second"
console.log(stack.size());  // 2

Why Use Deque Instead of List for Stacks?

In Python, lists can act as stacks (append/pop), but they're not optimal. List's pop(0) is O(n) and even pop() can trigger array resizing. collections.deque guarantees O(1) for both ends, making it the preferred stack implementation for performance-critical code.

Queue as a Restricted Deque

A queue enforces First-In, First-Out (FIFO) discipline: the earliest added element is always the first to be removed. This behavior emerges when we restrict a deque to insert at one end and remove from the other.

Queue = Deque with Opposite-End Restriction

Queue Operation	Deque Equivalent
enqueue(x)	addRear(x)
dequeue()	removeFront()
front()/peek()	peekFront()
isEmpty()	isEmpty()
size()	size()

The key constraint: Insertion happens at the rear, removal happens at the front. This creates the "line" behavior—first to enter is first to exit.

queue_via_deque
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Queue implementation using a Deque as the underlying structure.
 * 
 * This demonstrates that a queue is merely a restricted deque.
 * Insert at rear, remove from front = FIFO.
 */
class QueueViaDeque<T> {
    private deque: Deque<T>;
 
    constructor() {
        this.deque = new Deque<T>();
    }
 
    /**
     * Add an element to the rear of the queue.
     * Time Complexity: O(1)
     */
    enqueue(element: T): void {
        this.deque.addRear(element);
    }
 
    /**
     * Remove and return the front element.
     * Throws if queue is empty.
     * Time Complexity: O(1)
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue underflow: cannot dequeue from empty queue");
        }
        return this.deque.removeFront();
    }
 
    /**
     * View the front element without removing it.
     * Throws if queue is empty.
     * Time Complexity: O(1)
     */
    front(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty: cannot peek front");
        }
        return this.deque.peekFront();
    }
 
    /**
     * Optional: View the rear element (last in line).
     * This extension is possible because we're backed by a deque!
     */
    rear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty: cannot peek rear");
        }
        return this.deque.peekRear();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
// Usage example
const queue = new QueueViaDeque<string>();
queue.enqueue("first");
queue.enqueue("second");
queue.enqueue("third");
console.log(queue.dequeue());  // "first"  (FIFO)
console.log(queue.front());    // "second"
console.log(queue.rear());     // "third" (deque bonus!)

The List Trap for Queues

Never use a Python list as a queue (list.pop(0)). This looks correct but is O(n) because all elements shift. A deque.popleft() is O(1). This difference can mean seconds vs milliseconds for large queues.

The Behavioral Equivalence Proof

Let's prove formally that a restricted deque behaves identically to the data structure it emulates:

Theorem 1: Stack Equivalence

For any sequence of stack operations S = [op₁, op₂, ..., opₙ], executing S on:

A dedicated stack implementation, or
A deque restricted to rear-only operations

...produces identical observable results (return values and final state).

Proof Sketch:

Let's trace operations and compare states:

Operation       | Stack State | Deque (rear-only) State
----------------|-------------|------------------------
Initial         | []          | []
push(A)         | [A]         | [A]
push(B)         | [A, B]      | [A, B]
push(C)         | [A, B, C]   | [A, B, C]
pop() → C       | [A, B]      | [A, B]
peek() → B      | [A, B]      | [A, B]
pop() → B       | [A]         | [A]

The states are identical at every step. The restriction (rear-only) preserves LIFO semantics. □

Theorem 2: Queue Equivalence

For any sequence of queue operations Q = [op₁, op₂, ..., opₙ], executing Q on:

A dedicated queue implementation, or
A deque restricted to addRear and removeFront operations

...produces identical observable results.

Proof Sketch:

Operation         | Queue State | Deque (rear-add, front-remove)
------------------|-------------|--------------------------------
Initial           | []          | []
enqueue(A)        | [A]         | [A]
enqueue(B)        | [A, B]      | [A, B]
enqueue(C)        | [A, B, C]   | [A, B, C]
dequeue() → A     | [B, C]      | [B, C]
front() → B       | [B, C]      | [B, C]
dequeue() → B     | [C]         | [C]

The states are identical at every step. FIFO semantics are preserved. □

Implication:

These proofs matter because they mean you can:

Use a single deque implementation for stacks, queues, or full deques
Trust that the behavioral contracts are met
Test a deque implementation and get stack/queue correctness for free

Implementation Tip

In production code, even if using a deque internally, expose only the narrower interface (Stack or Queue) to callers. This prevents misuse and documents intent. The Adapter Pattern is useful here: wrap the deque, expose only relevant methods.

Practical Benefits of the Unification

Understanding that deques unify stacks and queues offers several practical advantages:

Benefit 1: Single Implementation

Instead of implementing, testing, and maintaining three data structures, implement one well-tested deque. Derive stack and queue through restriction. This reduces code, bugs, and cognitive load.

Benefit 2: Runtime Flexibility

Some algorithms need to switch between stack-like and queue-like behavior dynamically. A deque allows this naturally:

// Algorithm that sometimes needs LIFO, sometimes FIFO
function processWithHybridDiscipline<T>(deque: Deque<T>) {
    if (needsLIFO()) {
        process(deque.removeRear());   // Stack-like
    } else {
        process(deque.removeFront());  // Queue-like
    }
}

Benefit 3: Algorithm Evolution

When prototyping algorithms, you often don't know which discipline you need. Starting with a deque lets you experiment:

Begin with FIFO processing (queue behavior)
Discover that priority elements need front insertion → use addFront
Realize some cleanup needs rear removal → use removeRear
You've organically discovered you need a full deque!

Benefit 4: Library Design

Language designers recognized this relationship:

Python's collections.deque explicitly recommends using it for stacks and queues
C++'s std::deque underpins std::stack and std::queue adapters
Java's Deque interface is implemented by ArrayDeque and LinkedList, both usable as stacks or queues

Standard Library Design

Most modern standard libraries provide deque as a first-class citizen, with stack/queue as interfaces or adapters. This reflects the understanding that deque is the generalizing structure. When learning a new language, check if its queue/stack use deque internally—they often do.

When Full Deque Power Is Needed

Not every algorithm needs the full power of a deque. But some algorithms require it—they cannot be efficiently solved with stacks or queues alone. Let's examine these scenarios:

Algorithms Requiring Full Deque Power

•Sliding Window Maximum/Minimum — Requires adding at rear, removing from front (expired elements) AND removing from rear (dominated elements). Neither stack nor queue suffices.
•Palindrome Verification — Efficiently compare front and rear, removing matched pairs from both ends. A stack or queue would require O(n) extra space to reverse.
•Work-Stealing Schedulers — Owners add/remove at one end, thieves steal from the opposite end. Pure stack or queue semantics don't support concurrent access optimization.
•Deque-Based BFS Variants — Algorithms like 0-1 BFS add zero-cost edges to front, positive-cost edges to rear. This mixed insertion is impossible with standard queues.
•Undo with Capacity Limit — New actions add to rear (stack-like), oldest actions removed from front when over capacity (queue-like trim). Need both ends for different purposes.

zero_one_bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 0-1 BFS: Shortest path when all edge weights are 0 or 1.
 * 
 * This algorithm REQUIRES a deque—neither stack nor queue works:
 * - 0-weight edges: add to FRONT (highest priority, like Dijkstra's 0 cost)
 * - 1-weight edges: add to REAR (lower priority, delayed processing)
 * 
 * Time Complexity: O(V + E) — better than O((V+E)logV) for Dijkstra!
 */
interface Edge {
    to: number;
    weight: 0 | 1;
}
 
function zeroOneBFS(graph: Edge[][], start: number): number[] {
    const n = graph.length;
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
 
    const deque = new Deque<number>();
    deque.addRear(start);
 
    while (!deque.isEmpty()) {
        const u = deque.removeFront();
 
        for (const edge of graph[u]) {
            const { to: v, weight: w } = edge;
            const newDist = dist[u] + w;
 
            if (newDist < dist[v]) {
                dist[v] = newDist;
 
                // THIS IS THE KEY: different ends based on weight!
                if (w === 0) {
                    deque.addFront(v);  // 0-weight: high priority
                } else {
                    deque.addRear(v);   // 1-weight: normal priority
                }
            }
        }
    }
 
    return dist;
}
 
// Example: Grid with some free moves (0) and paid moves (1)
// This pattern appears in shortest path problems with limited free moves

Recognize the Pattern

Whenever you find yourself needing 'priority insertion' (some elements jump to front) OR 'stale removal' (remove from opposite end than insertion), you likely need a deque. Neither pure stack nor pure queue handles both.

Choosing Between Stack, Queue, and Deque

Given that a deque can do everything stacks and queues can do, why not always use a deque? The answer lies in communicating intent and enforcing constraints:

Principle: Use the Most Restrictive Structure That Works

This principle has several benefits:

Documentation: Using a Stack tells readers "this code only needs LIFO behavior"
Error Prevention: A Stack interface can't accidentally call addFront
Optimization Opportunity: Some implementations optimize for restricted patterns
Cognitive Load: Simpler interfaces are easier to reason about

Decision Guide: When to Use Each Structure
Scenario	Best Choice	Why
Processing in arrival order	Queue	FIFO is exactly what you need; stack would reverse order
Undo/redo operations	Stack	LIFO is exactly what you need; most recent first
Function call management	Stack	Call stack is inherently LIFO
BFS traversal	Queue	Level-by-level requires FIFO
Sliding window optimization	Deque	Need both ends for maintenance
Priority insertion + FIFO processing	Deque	Front insertion + front removal
Uncertain requirements	Deque (initially)	Flex as needs clarify, then restrict
Work-stealing parallelism	Deque	Different ends for different threads

Do This

Start with the simplest structure (stack or queue). Upgrade to deque only when you hit limitations. This progressive approach reveals actual requirements rather than anticipating imaginary ones.

Avoid This

Don't use deque everywhere 'just in case.' This obscures intent, makes code harder to understand, and can mask bugs where the wrong operation is called. Be intentional about your data structure choice.

The Adapter Pattern for Type Safety

In production code, you often want to use a deque internally for its performance while exposing a restricted interface externally. The Adapter Pattern achieves this:

Pattern: Internal Deque, External Stack/Queue Interface

┌─────────────────────────────────────────────────┐
│                  Client Code                    │
│    Uses Stack<T> or Queue<T> interface only     │
└───────────────────────┬─────────────────────────┘
                        │ (restricted interface)
                        ▼
┌─────────────────────────────────────────────────┐
│             StackAdapter / QueueAdapter         │
│    Wraps Deque<T>, exposes only subset ops      │
└───────────────────────┬─────────────────────────┘
                        │ (uses internally)
                        ▼
┌─────────────────────────────────────────────────┐
│                    Deque<T>                     │
│     Full power, but hidden from clients         │
└─────────────────────────────────────────────────┘

adapter_pattern
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Type-safe interfaces that prevent misuse
 
interface IStack<T> {
    push(element: T): void;
    pop(): T;
    peek(): T;
    isEmpty(): boolean;
    size(): number;
}
 
interface IQueue<T> {
    enqueue(element: T): void;
    dequeue(): T;
    front(): T;
    isEmpty(): boolean;
    size(): number;
}
 
/**
 * Stack adapter: provides only stack operations,
 * backed by a performant deque.
 */
class Stack<T> implements IStack<T> {
    private readonly deque = new Deque<T>();
 
    push(element: T): void {
        this.deque.addRear(element);
    }
 
    pop(): T {
        if (this.isEmpty()) throw new Error("Stack underflow");
        return this.deque.removeRear();
    }
 
    peek(): T {
        if (this.isEmpty()) throw new Error("Stack is empty");
        return this.deque.peekRear();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
/**
 * Queue adapter: provides only queue operations,
 * backed by a performant deque.
 */
class Queue<T> implements IQueue<T> {
    private readonly deque = new Deque<T>();
 
    enqueue(element: T): void {
        this.deque.addRear(element);
    }
 
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Queue underflow");
        return this.deque.removeFront();
    }
 
    front(): T {
        if (this.isEmpty()) throw new Error("Queue is empty");
        return this.deque.peekFront();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
// Client code gets compile-time safety:
const stack: IStack<number> = new Stack();
stack.push(1);
// stack.removeFront();  // Compile error! Not in IStack interface
 
const queue: IQueue<number> = new Queue();
queue.enqueue(1);
// queue.pop();  // Compile error! Not in IQueue interface

Best of Both Worlds

The adapter pattern gives you O(1) performance from deque internals AND compile-time/runtime safety from a restricted interface. This is the production-grade approach used in many standard libraries.

Summary: The Generalization Relationship

Let's consolidate our understanding of how deques, stacks, and queues relate:

Key Takeaways

•Deque generalizes stack and queue — Both are restricted deques with specific operation subsets
•Stack = same-end restriction — addRear+removeRear or addFront+removeFront gives LIFO
•Queue = opposite-end restriction — addRear+removeFront gives FIFO
•One implementation, three behaviors — A correct deque implementation yields correct stacks and queues
•Use the most restrictive structure — Communicate intent and prevent errors by exposing only needed operations
•Some algorithms require full deque — Sliding window, 0-1 BFS, palindrome checking need both ends
•Adapter pattern for production — Internal deque, external restricted interface
•Standard libraries reflect this — Python, C++, Java all provide deque as the foundational container

What's Next:

With the theoretical relationship clear, we'll explore the practical aspects of implementing deques. The next page covers implementation considerations—array-based vs linked-list implementations, trade-offs, and real-world performance characteristics.

Page Complete

You now understand the deep relationship between deques, stacks, and queues. This insight unifies your mental model of linear data structures and informs better design decisions. Next, we explore how to implement deques efficiently.

Deque as a Generalization of Stack and Queue

The Unifying Abstraction

What You Will Learn

The Generalization Hierarchy

Let's formalize the relationship between deques, stacks, and queues using the concept of restriction:

Definition: Restriction

A data structure A is a restriction of data structure B if:

A's operations are a subset of B's operations
A can be implemented by using only certain operations of B
A imposes additional constraints that B doesn't require

The Hierarchy:

                    ┌─────────────────┐
                    │      DEQUE      │
                    │  (full access)  │
                    └────────┬────────┘
                             │
              ┌──────────────┴──────────────┐
              │                             │
              ▼                             ▼
    ┌─────────────────┐           ┌─────────────────┐
    │      STACK      │           │      QUEUE      │
    │ (one end only)  │           │ (FIFO: opposite │
    │                 │           │     ends)       │
    └─────────────────┘           └─────────────────┘

How Stacks and Queues Restrict the Deque
Data Structure	Insert Operations Used	Remove Operations Used	Constraint
Full Deque	addFront, addRear	removeFront, removeRear	None
Stack	addRear only (or addFront only)	removeRear only (or removeFront only)	Same end for insert and remove
Queue	addRear only	removeFront only	Opposite ends for insert and remove
Output-Restricted Deque	addFront, addRear	removeFront only	One removal end
Input-Restricted Deque	addRear only	removeFront, removeRear	One insertion end

The Power of Generalization

Stack as a Restricted Deque

Stack = Deque with Single-End Restriction

Stack Operation	Deque Equivalent	Alternative
push(x)	addRear(x)	addFront(x)
pop()	removeRear()	removeFront()
peek()/top()	peekRear()	peekFront()
isEmpty()	isEmpty()	isEmpty()
size()	size()	size()

The key constraint: Both insertion and removal happen at the same end. Whether that's the rear or front is arbitrary—LIFO behavior results either way.

stack_via_deque
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Stack implementation using a Deque as the underlying structure.
 * 
 * This demonstrates that a stack is merely a restricted deque.
 * We choose to use the rear end for all operations, but front
 * would work equally well.
 */
class StackViaDeque<T> {
    private deque: Deque<T>;
 
    constructor() {
        this.deque = new Deque<T>();
    }
 
    /**
     * Push an element onto the stack.
     * Time Complexity: O(1)
     */
    push(element: T): void {
        this.deque.addRear(element);
    }
 
    /**
     * Pop and return the top element.
     * Throws if stack is empty.
     * Time Complexity: O(1)
     */
    pop(): T {
        if (this.isEmpty()) {
            throw new Error("Stack underflow: cannot pop from empty stack");
        }
        return this.deque.removeRear();
    }
 
    /**
     * View the top element without removing it.
     * Throws if stack is empty.
     * Time Complexity: O(1)
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Stack is empty: cannot peek");
        }
        return this.deque.peekRear();
    }
 
    /**
     * Check if the stack is empty.
     * Time Complexity: O(1)
     */
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    /**
     * Return the number of elements in the stack.
     * Time Complexity: O(1)
     */
    size(): number {
        return this.deque.size();
    }
}
 
// Usage example
const stack = new StackViaDeque<string>();
stack.push("first");
stack.push("second");
stack.push("third");
console.log(stack.pop());   // "third"  (LIFO)
console.log(stack.peek());  // "second"
console.log(stack.size());  // 2

Why Use Deque Instead of List for Stacks?

Queue as a Restricted Deque

Queue = Deque with Opposite-End Restriction

Queue Operation	Deque Equivalent
enqueue(x)	addRear(x)
dequeue()	removeFront()
front()/peek()	peekFront()
isEmpty()	isEmpty()
size()	size()

The key constraint: Insertion happens at the rear, removal happens at the front. This creates the "line" behavior—first to enter is first to exit.

queue_via_deque
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Queue implementation using a Deque as the underlying structure.
 * 
 * This demonstrates that a queue is merely a restricted deque.
 * Insert at rear, remove from front = FIFO.
 */
class QueueViaDeque<T> {
    private deque: Deque<T>;
 
    constructor() {
        this.deque = new Deque<T>();
    }
 
    /**
     * Add an element to the rear of the queue.
     * Time Complexity: O(1)
     */
    enqueue(element: T): void {
        this.deque.addRear(element);
    }
 
    /**
     * Remove and return the front element.
     * Throws if queue is empty.
     * Time Complexity: O(1)
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue underflow: cannot dequeue from empty queue");
        }
        return this.deque.removeFront();
    }
 
    /**
     * View the front element without removing it.
     * Throws if queue is empty.
     * Time Complexity: O(1)
     */
    front(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty: cannot peek front");
        }
        return this.deque.peekFront();
    }
 
    /**
     * Optional: View the rear element (last in line).
     * This extension is possible because we're backed by a deque!
     */
    rear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty: cannot peek rear");
        }
        return this.deque.peekRear();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
// Usage example
const queue = new QueueViaDeque<string>();
queue.enqueue("first");
queue.enqueue("second");
queue.enqueue("third");
console.log(queue.dequeue());  // "first"  (FIFO)
console.log(queue.front());    // "second"
console.log(queue.rear());     // "third" (deque bonus!)

The List Trap for Queues

The Behavioral Equivalence Proof

Let's prove formally that a restricted deque behaves identically to the data structure it emulates:

Theorem 1: Stack Equivalence

For any sequence of stack operations S = [op₁, op₂, ..., opₙ], executing S on:

A dedicated stack implementation, or
A deque restricted to rear-only operations

...produces identical observable results (return values and final state).

Proof Sketch:

Let's trace operations and compare states:

Operation       | Stack State | Deque (rear-only) State
----------------|-------------|------------------------
Initial         | []          | []
push(A)         | [A]         | [A]
push(B)         | [A, B]      | [A, B]
push(C)         | [A, B, C]   | [A, B, C]
pop() → C       | [A, B]      | [A, B]
peek() → B      | [A, B]      | [A, B]
pop() → B       | [A]         | [A]

The states are identical at every step. The restriction (rear-only) preserves LIFO semantics. □

Theorem 2: Queue Equivalence

For any sequence of queue operations Q = [op₁, op₂, ..., opₙ], executing Q on:

A dedicated queue implementation, or
A deque restricted to addRear and removeFront operations

...produces identical observable results.

Proof Sketch:

Operation         | Queue State | Deque (rear-add, front-remove)
------------------|-------------|--------------------------------
Initial           | []          | []
enqueue(A)        | [A]         | [A]
enqueue(B)        | [A, B]      | [A, B]
enqueue(C)        | [A, B, C]   | [A, B, C]
dequeue() → A     | [B, C]      | [B, C]
front() → B       | [B, C]      | [B, C]
dequeue() → B     | [C]         | [C]

The states are identical at every step. FIFO semantics are preserved. □

Implication:

These proofs matter because they mean you can:

Use a single deque implementation for stacks, queues, or full deques
Trust that the behavioral contracts are met
Test a deque implementation and get stack/queue correctness for free

Implementation Tip

Practical Benefits of the Unification

Understanding that deques unify stacks and queues offers several practical advantages:

Benefit 1: Single Implementation

Instead of implementing, testing, and maintaining three data structures, implement one well-tested deque. Derive stack and queue through restriction. This reduces code, bugs, and cognitive load.

Benefit 2: Runtime Flexibility

Some algorithms need to switch between stack-like and queue-like behavior dynamically. A deque allows this naturally:

// Algorithm that sometimes needs LIFO, sometimes FIFO
function processWithHybridDiscipline<T>(deque: Deque<T>) {
    if (needsLIFO()) {
        process(deque.removeRear());   // Stack-like
    } else {
        process(deque.removeFront());  // Queue-like
    }
}

Benefit 3: Algorithm Evolution

When prototyping algorithms, you often don't know which discipline you need. Starting with a deque lets you experiment:

Begin with FIFO processing (queue behavior)
Discover that priority elements need front insertion → use addFront
Realize some cleanup needs rear removal → use removeRear
You've organically discovered you need a full deque!

Benefit 4: Library Design

Language designers recognized this relationship:

Python's collections.deque explicitly recommends using it for stacks and queues
C++'s std::deque underpins std::stack and std::queue adapters
Java's Deque interface is implemented by ArrayDeque and LinkedList, both usable as stacks or queues

Standard Library Design

When Full Deque Power Is Needed

Not every algorithm needs the full power of a deque. But some algorithms require it—they cannot be efficiently solved with stacks or queues alone. Let's examine these scenarios:

Algorithms Requiring Full Deque Power

•Sliding Window Maximum/Minimum — Requires adding at rear, removing from front (expired elements) AND removing from rear (dominated elements). Neither stack nor queue suffices.
•Palindrome Verification — Efficiently compare front and rear, removing matched pairs from both ends. A stack or queue would require O(n) extra space to reverse.
•Work-Stealing Schedulers — Owners add/remove at one end, thieves steal from the opposite end. Pure stack or queue semantics don't support concurrent access optimization.
•Deque-Based BFS Variants — Algorithms like 0-1 BFS add zero-cost edges to front, positive-cost edges to rear. This mixed insertion is impossible with standard queues.
•Undo with Capacity Limit — New actions add to rear (stack-like), oldest actions removed from front when over capacity (queue-like trim). Need both ends for different purposes.

zero_one_bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 0-1 BFS: Shortest path when all edge weights are 0 or 1.
 * 
 * This algorithm REQUIRES a deque—neither stack nor queue works:
 * - 0-weight edges: add to FRONT (highest priority, like Dijkstra's 0 cost)
 * - 1-weight edges: add to REAR (lower priority, delayed processing)
 * 
 * Time Complexity: O(V + E) — better than O((V+E)logV) for Dijkstra!
 */
interface Edge {
    to: number;
    weight: 0 | 1;
}
 
function zeroOneBFS(graph: Edge[][], start: number): number[] {
    const n = graph.length;
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
 
    const deque = new Deque<number>();
    deque.addRear(start);
 
    while (!deque.isEmpty()) {
        const u = deque.removeFront();
 
        for (const edge of graph[u]) {
            const { to: v, weight: w } = edge;
            const newDist = dist[u] + w;
 
            if (newDist < dist[v]) {
                dist[v] = newDist;
 
                // THIS IS THE KEY: different ends based on weight!
                if (w === 0) {
                    deque.addFront(v);  // 0-weight: high priority
                } else {
                    deque.addRear(v);   // 1-weight: normal priority
                }
            }
        }
    }
 
    return dist;
}
 
// Example: Grid with some free moves (0) and paid moves (1)
// This pattern appears in shortest path problems with limited free moves

Recognize the Pattern

Choosing Between Stack, Queue, and Deque

Given that a deque can do everything stacks and queues can do, why not always use a deque? The answer lies in communicating intent and enforcing constraints:

Principle: Use the Most Restrictive Structure That Works

This principle has several benefits:

Documentation: Using a Stack tells readers "this code only needs LIFO behavior"
Error Prevention: A Stack interface can't accidentally call addFront
Optimization Opportunity: Some implementations optimize for restricted patterns
Cognitive Load: Simpler interfaces are easier to reason about

Decision Guide: When to Use Each Structure
Scenario	Best Choice	Why
Processing in arrival order	Queue	FIFO is exactly what you need; stack would reverse order
Undo/redo operations	Stack	LIFO is exactly what you need; most recent first
Function call management	Stack	Call stack is inherently LIFO
BFS traversal	Queue	Level-by-level requires FIFO
Sliding window optimization	Deque	Need both ends for maintenance
Priority insertion + FIFO processing	Deque	Front insertion + front removal
Uncertain requirements	Deque (initially)	Flex as needs clarify, then restrict
Work-stealing parallelism	Deque	Different ends for different threads

Do This

Start with the simplest structure (stack or queue). Upgrade to deque only when you hit limitations. This progressive approach reveals actual requirements rather than anticipating imaginary ones.

Avoid This

The Adapter Pattern for Type Safety

In production code, you often want to use a deque internally for its performance while exposing a restricted interface externally. The Adapter Pattern achieves this:

Pattern: Internal Deque, External Stack/Queue Interface

┌─────────────────────────────────────────────────┐
│                  Client Code                    │
│    Uses Stack<T> or Queue<T> interface only     │
└───────────────────────┬─────────────────────────┘
                        │ (restricted interface)
                        ▼
┌─────────────────────────────────────────────────┐
│             StackAdapter / QueueAdapter         │
│    Wraps Deque<T>, exposes only subset ops      │
└───────────────────────┬─────────────────────────┘
                        │ (uses internally)
                        ▼
┌─────────────────────────────────────────────────┐
│                    Deque<T>                     │
│     Full power, but hidden from clients         │
└─────────────────────────────────────────────────┘

adapter_pattern
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Type-safe interfaces that prevent misuse
 
interface IStack<T> {
    push(element: T): void;
    pop(): T;
    peek(): T;
    isEmpty(): boolean;
    size(): number;
}
 
interface IQueue<T> {
    enqueue(element: T): void;
    dequeue(): T;
    front(): T;
    isEmpty(): boolean;
    size(): number;
}
 
/**
 * Stack adapter: provides only stack operations,
 * backed by a performant deque.
 */
class Stack<T> implements IStack<T> {
    private readonly deque = new Deque<T>();
 
    push(element: T): void {
        this.deque.addRear(element);
    }
 
    pop(): T {
        if (this.isEmpty()) throw new Error("Stack underflow");
        return this.deque.removeRear();
    }
 
    peek(): T {
        if (this.isEmpty()) throw new Error("Stack is empty");
        return this.deque.peekRear();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
/**
 * Queue adapter: provides only queue operations,
 * backed by a performant deque.
 */
class Queue<T> implements IQueue<T> {
    private readonly deque = new Deque<T>();
 
    enqueue(element: T): void {
        this.deque.addRear(element);
    }
 
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Queue underflow");
        return this.deque.removeFront();
    }
 
    front(): T {
        if (this.isEmpty()) throw new Error("Queue is empty");
        return this.deque.peekFront();
    }
 
    isEmpty(): boolean {
        return this.deque.isEmpty();
    }
 
    size(): number {
        return this.deque.size();
    }
}
 
// Client code gets compile-time safety:
const stack: IStack<number> = new Stack();
stack.push(1);
// stack.removeFront();  // Compile error! Not in IStack interface
 
const queue: IQueue<number> = new Queue();
queue.enqueue(1);
// queue.pop();  // Compile error! Not in IQueue interface

Best of Both Worlds

The adapter pattern gives you O(1) performance from deque internals AND compile-time/runtime safety from a restricted interface. This is the production-grade approach used in many standard libraries.

Summary: The Generalization Relationship

Let's consolidate our understanding of how deques, stacks, and queues relate:

Key Takeaways

•Deque generalizes stack and queue — Both are restricted deques with specific operation subsets
•Stack = same-end restriction — addRear+removeRear or addFront+removeFront gives LIFO
•Queue = opposite-end restriction — addRear+removeFront gives FIFO
•One implementation, three behaviors — A correct deque implementation yields correct stacks and queues
•Use the most restrictive structure — Communicate intent and prevent errors by exposing only needed operations
•Some algorithms require full deque — Sliding window, 0-1 BFS, palindrome checking need both ends
•Adapter pattern for production — Internal deque, external restricted interface
•Standard libraries reflect this — Python, C++, Java all provide deque as the foundational container

What's Next:

Page Complete