Data Structures & AlgorithmsDouble-Ended Queue (Deque)

Double-Ended Queue (Deque) — Flexible Two-End Access

LevelIntermediate

Duration55 mins

TopicDouble-Ended Queue (Deque)

2 / 4

Operations — Add and Remove at Both Ends

Mastering the Deque Interface

The power of any data structure lies in its operations—the precise, well-defined actions that transform it from an abstract concept into a practical tool. For the deque, these operations are elegant in their symmetry yet profound in their implications.

In this page, we'll dissect every deque operation with the rigor of a language specification. You'll understand not just what each operation does, but why it's defined the way it is, what happens in edge cases, and how to use these operations effectively in real code.

What You Will Learn

By the end of this page, you will master all eight fundamental deque operations: addFront, addRear, removeFront, removeRear, peekFront, peekRear, isEmpty, and size. You'll understand their precise behavior, time complexity, and how they compose to form powerful algorithms.

The Complete Deque Operation Set

A deque provides eight core operations that fall into three categories:

Mutating Operations (modify the deque):

addFront(element) — Insert at the front
addRear(element) — Insert at the rear
removeFront() — Remove from the front
removeRear() — Remove from the rear

Accessor Operations (inspect without modifying):

peekFront() — View the front element
peekRear() — View the rear element

State Query Operations (check deque state):

isEmpty() — Is the deque empty?
size() — How many elements are present?

Deque Operations at a Glance
Operation	Category	Returns	Modifies Deque?	Typical Complexity
addFront(e)	Mutating	void	Yes	O(1)
addRear(e)	Mutating	void	Yes	O(1)
removeFront()	Mutating	element	Yes	O(1)
removeRear()	Mutating	element	Yes	O(1)
peekFront()	Accessor	element	No	O(1)
peekRear()	Accessor	element	No	O(1)
isEmpty()	State Query	boolean	No	O(1)
size()	State Query	integer	No	O(1)

Naming Conventions Vary

Different languages use different names: addFirst/addLast, push_front/push_back, appendleft/append, etc. The semantics remain the same. Throughout this page, we use generic names that map to any language.

addFront — Inserting at the Front

The addFront operation inserts a new element at the front of the deque. After this operation, the new element becomes the first element, and all previous elements shift conceptually to the right (their logical positions increase by one).

Precise Semantics:

Precondition:  deque is a valid deque (possibly empty)
               element is a valid value of the deque's element type

Postcondition: size(deque) = old_size + 1
               peekFront() returns element
               all previous elements maintain their relative order
               the element previously at front is now at position 1

Operation Trace:

Step	Deque State	Operation	Result
0	`[]`	Initial (empty)	—
1	`[A]`	`addFront(A)`	A is at front and rear
2	`[B, A]`	`addFront(B)`	B is at front, A at rear
3	`[C, B, A]`	`addFront(C)`	C at front, A at rear
4	`[D, C, B, A]`	`addFront(D)`	D at front, A at rear

No Shifting in Efficient Implementations

Although logically elements "shift right," efficient deque implementations (circular arrays, doubly-linked lists) don't actually move data. They update pointers or indices. This is why addFront achieves O(1) time complexity.

addFront_example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Using addFront for priority insertion
class Task {
    constructor(public name: string, public priority: "normal" | "high") {}
}
 
// Deque-based task queue with priority support
function scheduleTask(deque: Deque<Task>, task: Task): void {
    if (task.priority === "high") {
        // High priority: insert at front (will be processed first)
        deque.addFront(task);
    } else {
        // Normal priority: insert at rear (wait in line)
        deque.addRear(task);
    }
}
 
// Usage
const taskQueue = new Deque<Task>();
scheduleTask(taskQueue, new Task("Email", "normal"));  // Goes to rear
scheduleTask(taskQueue, new Task("Bug Fix", "high"));  // Goes to front
// Deque state: [Bug Fix, Email]

Key Use Cases for addFront:

Priority insertion: When a high-priority item must skip ahead
Undo stacks: When the most recent action must be at the front
Prefix building: Constructing sequences from end to beginning
Work-stealing: Adding work at one's own end of a shared deque

addRear — Inserting at the Rear

The addRear operation inserts a new element at the rear of the deque. This is the most common insertion operation and mirrors how queues naturally grow—new elements join at the end.

Precise Semantics:

Precondition:  deque is a valid deque (possibly empty)
               element is a valid value of the deque's element type

Postcondition: size(deque) = old_size + 1
               peekRear() returns element
               all previous elements maintain their positions
               the element previously at rear is now at position (size - 2)

Operation Trace:

Step	Deque State	Operation	Result
0	`[]`	Initial (empty)	—
1	`[A]`	`addRear(A)`	A is at front and rear
2	`[A, B]`	`addRear(B)`	A at front, B at rear
3	`[A, B, C]`	`addRear(C)`	A at front, C at rear
4	`[A, B, C, D]`	`addRear(D)`	A at front, D at rear

The Natural Growth Direction

When building sequences in their natural order (first element first, last element last), use addRear exclusively. This matches how humans typically think about lists and is why addRear is often the default operation in languages (e.g., Python's append, JavaScript's push).

addRear_example
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
// Building a browsing history with addRear
interface HistoryEntry {
    url: string;
    timestamp: Date;
}
 
class BrowsingHistory {
    private history = new Deque<HistoryEntry>();
    private maxSize = 100;  // Limit history size
 
    visit(url: string): void {
        const entry: HistoryEntry = {
            url,
            timestamp: new Date()
        };
        
        // Add to rear (most recent is always at rear)
        this.history.addRear(entry);
        
        // Trim if exceeding max size (remove oldest from front)
        while (this.history.size() > this.maxSize) {
            this.history.removeFront();
        }
    }
 
    getMostRecent(): HistoryEntry | undefined {
        return this.history.isEmpty() ? undefined : this.history.peekRear();
    }
 
    getOldest(): HistoryEntry | undefined {
        return this.history.isEmpty() ? undefined : this.history.peekFront();
    }
}

Key Use Cases for addRear:

Queue-like behavior: Standard enqueue operation (FIFO processing)
History tracking: New events join chronologically at the end
Buffer building: Accumulating data as it arrives
Log management: Appending new log entries

removeFront — Removing from the Front

The removeFront operation removes and returns the element at the front of the deque. After this operation, the element that was second becomes the new front, and the deque's size decreases by one.

Precise Semantics:

Precondition:  deque is non-empty
               (behavior on empty deque is implementation-defined:
                throw exception, return null, undefined behavior, etc.)

Postcondition: size(deque) = old_size - 1
               returns the element that was at position 0
               element at position 1 becomes new position 0
               all remaining elements shift conceptually left

Operation Trace:

Step	Deque State	Operation	Return Value	New State
0	`[A, B, C, D]`	Initial	—	—
1	`[B, C, D]`	`removeFront()`	A	B at front
2	`[C, D]`	`removeFront()`	B	C at front
3	`[D]`	`removeFront()`	C	D at front and rear
4	`[]`	`removeFront()`	D	Empty deque

Empty Deque Behavior

What happens when you call removeFront() on an empty deque? This varies by language: Java throws NoSuchElementException, Python raises IndexError, C++ results in undefined behavior. ALWAYS check isEmpty() before removing, or use try-catch/try-except patterns.

removeFront_example
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
// Processing a task queue with removeFront
interface Task {
    id: string;
    name: string;
    createdAt: Date;
}
 
class TaskProcessor {
    private queue = new Deque<Task>();
 
    enqueue(task: Task): void {
        this.queue.addRear(task);  // Join at the end
    }
 
    processNext(): Task | null {
        if (this.queue.isEmpty()) {
            console.log("No tasks to process");
            return null;
        }
 
        // Remove from front (FIFO: oldest task processed first)
        const task = this.queue.removeFront();
        console.log(`Processing: ${task.name}`);
        return task;
    }
 
    // Peek at next task without removing
    peekNext(): Task | null {
        return this.queue.isEmpty() ? null : this.queue.peekFront();
    }
 
    pendingCount(): number {
        return this.queue.size();
    }
}
 
// Usage
const processor = new TaskProcessor();
processor.enqueue({ id: "1", name: "Task A", createdAt: new Date() });
processor.enqueue({ id: "2", name: "Task B", createdAt: new Date() });
processor.processNext();  // Returns Task A (first in, first out)

Key Use Cases for removeFront:

Queue processing: Standard dequeue operation (FIFO)
Sliding window: Remove elements that fall out of the window
BFS traversal: Remove the next node to visit
Bounded buffers: Remove oldest when buffer is full

removeRear — Removing from the Rear

The removeRear operation removes and returns the element at the rear of the deque. This operation enables stack-like behavior (LIFO) and is crucial for algorithms that need to undo or backtrack from the most recently added element.

Precise Semantics:

Precondition:  deque is non-empty
               (behavior on empty deque is implementation-defined)

Postcondition: size(deque) = old_size - 1
               returns the element that was at position (old_size - 1)
               the element at position (old_size - 2) becomes the new rear
               front remains unchanged (unless it was the only element)

Operation Trace:

Step	Deque State	Operation	Return Value	New State
0	`[A, B, C, D]`	Initial	—	—
1	`[A, B, C]`	`removeRear()`	D	C at rear
2	`[A, B]`	`removeRear()`	C	B at rear
3	`[A]`	`removeRear()`	B	A at front and rear
4	`[]`	`removeRear()`	A	Empty deque

Stack Behavior via Deque

When you pair addRear with removeRear (or addFront with removeFront), the deque behaves exactly like a stack: the most recently added element is always the one removed. This is why deques are often recommended for stack implementations in Python (collections.deque is faster than lists for this purpose).

removeRear_example
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
// Implementing undo/redo with deque and removeRear
interface Command {
    execute(): void;
    undo(): void;
    description: string;
}
 
class UndoableEditor {
    private text = "";
    private undoStack = new Deque<Command>();
    private redoStack = new Deque<Command>();
 
    execute(command: Command): void {
        command.execute();
        this.undoStack.addRear(command);  // Most recent at rear
        
        // Clear redo stack when new command is executed
        while (!this.redoStack.isEmpty()) {
            this.redoStack.removeRear();
        }
    }
 
    undo(): boolean {
        if (this.undoStack.isEmpty()) {
            return false;
        }
 
        // Remove most recent command from rear (LIFO)
        const command = this.undoStack.removeRear();
        command.undo();
        this.redoStack.addRear(command);  // Save for redo
        return true;
    }
 
    redo(): boolean {
        if (this.redoStack.isEmpty()) {
            return false;
        }
 
        // Re-execute most recently undone command
        const command = this.redoStack.removeRear();
        command.execute();
        this.undoStack.addRear(command);  // Back to undo stack
        return true;
    }
}

Key Use Cases for removeRear:

Undo operations: Remove the most recent action to reverse it
Backtracking algorithms: Pop the last decision when hitting a dead end
Monotonic deque maintenance: Remove elements violated by a new addition
Parsing with rollback: Undo token consumption on parse failure

peekFront and peekRear — Inspecting Without Modifying

The peekFront and peekRear operations allow you to inspect the elements at either end of the deque without removing them. These are accessor operations—they read data but don't change the deque's state.

Why Peek Matters:

Many algorithms need to examine an element before deciding what to do with it. Without peek, you'd have to:

Remove the element
Examine it
Decide whether to keep or discard it
If keeping, re-add it to the same position

This is both inefficient and error-prone. Peek simplifies this to a single, non-destructive inspection.

peekFront

•Purpose: View the element at the front
•Returns: The front element
•Side Effects: None
•On Empty Deque: Undefined/exception
•Time Complexity: O(1)
•Synonyms: front(), getFirst(), first()

peekRear

•Purpose: View the element at the rear
•Returns: The rear element
•Side Effects: None
•On Empty Deque: Undefined/exception
•Time Complexity: O(1)
•Synonyms: back(), getLast(), last()

peek_example
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
// Using peek for palindrome checking
function isPalindrome(deque: Deque<string>): boolean {
    while (deque.size() > 1) {
        // Compare front and rear without removing first
        const front = deque.peekFront();
        const rear = deque.peekRear();
 
        if (front !== rear) {
            return false;  // Mismatch found
        }
 
        // Only remove after confirming match
        deque.removeFront();
        deque.removeRear();
    }
 
    // 0 or 1 element remaining means palindrome
    return true;
}
 
// Usage
function checkPalindrome(str: string): boolean {
    const deque = new Deque<string>();
    
    // Add each character to deque
    for (const char of str.toLowerCase().replace(/[^a-z]/g, '')) {
        deque.addRear(char);
    }
    
    return isPalindrome(deque);
}
 
console.log(checkPalindrome("racecar"));  // true
console.log(checkPalindrome("hello"));    // false

Safe Peek Patterns

Always combine peek with isEmpty() checks. Pattern: if (!deque.isEmpty()) { let val = deque.peekFront(); ... }. Alternatively, use languages that provide optional/nullable returns: let val = deque.peekFrontOrNull();

isEmpty and size — Querying Deque State

The isEmpty and size operations provide metadata about the deque's current state. They're essential for safe operation and algorithm control flow.

isEmpty():

Returns true if the deque contains no elements
Returns false if the deque contains one or more elements
Time Complexity: O(1)
Use Case: Guard before removal operations

size():

Returns the current number of elements in the deque
Returns 0 if the deque is empty
Time Complexity: O(1)
Use Case: Capacity checks, loop bounds, progress tracking

The Relationship Between isEmpty and size:

isEmpty() ≡ (size() == 0)
!isEmpty() ≡ (size() > 0)

These are equivalent, but isEmpty() is preferred for readability when checking for emptiness. Some implementations might optimize isEmpty() to be faster than size() == 0, though in practice both should be O(1).

state_query_example
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
// Using isEmpty and size for safe deque operations
class SafeDeque<T> {
    private deque = new Deque<T>();
 
    // Safe remove with explicit empty handling
    removeFrontSafe(): T | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return this.deque.removeFront();
    }
 
    // Process all elements with size-based loop
    processAll(processor: (item: T) => void): number {
        let processed = 0;
        const total = this.deque.size();  // Capture initial size
        
        console.log(`Processing ${total} items...`);
        
        while (!this.deque.isEmpty()) {
            const item = this.deque.removeFront();
            processor(item);
            processed++;
            
            // Progress tracking
            console.log(`Progress: ${processed}/${total}`);
        }
        
        return processed;
    }
 
    // Size-limited addition
    addRearLimited(item: T, maxSize: number): boolean {
        if (this.deque.size() >= maxSize) {
            // At capacity, reject or remove oldest
            return false;  // Option 1: Reject
            // this.deque.removeFront();  // Option 2: Remove oldest
        }
        this.deque.addRear(item);
        return true;
    }
}

Beware of Size in Loops

If you're modifying the deque inside a loop, don't use size() as the loop bound: for (i = 0; i < deque.size(); i++) will give wrong results if size changes. Either capture size once before the loop, or use a while-isEmpty pattern.

Composing Operations — Powerful Patterns

Individual deque operations are building blocks. The real power emerges when you compose them into patterns. Let's explore common operation compositions:

Pattern 1: Queue Discipline (FIFO)

Use only: addRear + removeFront
Result: Standard queue behavior

Pattern 2: Stack Discipline (LIFO)

Use only: addRear + removeRear (or addFront + removeFront)
Result: Standard stack behavior

Pattern 3: Priority Injection

Normal: addRear
High priority: addFront
Processing: removeFront
Result: Queue with priority bypass

Pattern 4: Sliding Window

Add new: addRear
Remove stale: removeFront
Maintain property: peekFront, peekRear, removeRear (for monotonic property)
Result: Efficient sliding window algorithms

sliding_window_max
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
/**
 * Sliding Window Maximum using Deque
 * 
 * Given an array nums and window size k, return an array of maximum
 * values in each sliding window position.
 * 
 * Time Complexity: O(n) - each element added/removed at most once
 * Space Complexity: O(k) - deque holds at most k elements
 */
function slidingWindowMax(nums: number[], k: number): number[] {
    const result: number[] = [];
    const deque = new Deque<number>();  // Stores indices
 
    for (let i = 0; i < nums.length; i++) {
        // 1. Remove indices that are out of the current window (from front)
        while (!deque.isEmpty() && deque.peekFront() <= i - k) {
            deque.removeFront();
        }
 
        // 2. Remove indices of elements smaller than current (from rear)
        //    They can never be the maximum in any future window
        while (!deque.isEmpty() && nums[deque.peekRear()] < nums[i]) {
            deque.removeRear();
        }
 
        // 3. Add current index to rear
        deque.addRear(i);
 
        // 4. Once we have a full window, record the maximum
        if (i >= k - 1) {
            result.push(nums[deque.peekFront()]);
        }
    }
 
    return result;
}
 
// Example usage
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(slidingWindowMax(nums, k));  // [3, 3, 5, 5, 6, 7]

The Monotonic Deque Pattern

The sliding window maximum uses a 'monotonic deque' where elements are maintained in decreasing order. This pattern appears in many optimization problems: next greater element variations, histogram problems, and dynamic programming optimizations.

Edge Cases and Error Handling

Robust deque usage requires careful attention to edge cases. Let's catalog the scenarios that trip up programmers:

Edge Case 1: Empty Deque Operations

removeFront() on empty → Exception or undefined
removeRear() on empty → Exception or undefined
peekFront() on empty → Exception, null, or undefined
peekRear() on empty → Exception, null, or undefined

Edge Case 2: Single-Element Deque

After addFront(x) to empty: peekFront() == peekRear() == x
removeFront() and removeRear() return the same element
Removing makes the deque empty

Edge Case 3: Sequence Matters

addFront(A); addFront(B) → [B, A] (B at front)
addRear(A); addRear(B) → [A, B] (A at front)
Order of operations determines final arrangement

edge_case_handling
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
// Comprehensive edge case handling for deque operations
class RobustDeque<T> {
    private deque = new Deque<T>();
 
    // Safe removal with Optional pattern
    removeFrontOptional(): { value: T } | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return { value: this.deque.removeFront() };
    }
 
    removeRearOptional(): { value: T } | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return { value: this.deque.removeRear() };
    }
 
    // Safe peek with default value
    peekFrontOrDefault(defaultValue: T): T {
        return this.deque.isEmpty() ? defaultValue : this.deque.peekFront();
    }
 
    peekRearOrDefault(defaultValue: T): T {
        return this.deque.isEmpty() ? defaultValue : this.deque.peekRear();
    }
 
    // Batch operations with transaction semantics
    addMultipleFront(items: T[]): void {
        // Add in reverse order so first item ends up at front
        for (let i = items.length - 1; i >= 0; i--) {
            this.deque.addFront(items[i]);
        }
    }
 
    addMultipleRear(items: T[]): void {
        for (const item of items) {
            this.deque.addRear(item);
        }
    }
 
    // Drain all elements (clear with return)
    drainAll(): T[] {
        const result: T[] = [];
        while (!this.deque.isEmpty()) {
            result.push(this.deque.removeFront());
        }
        return result;
    }
}

Never Assume Non-Empty

The most common deque bug is calling remove or peek without checking isEmpty(). Even if you 'know' the deque has elements, defensive programming saves debugging time. Make empty checks a habit.

Summary: Mastering Deque Operations

You've now mastered all fundamental deque operations. Let's consolidate:

Key Takeaways

•Eight core operations: addFront, addRear, removeFront, removeRear, peekFront, peekRear, isEmpty, size
•All operations are O(1) in properly implemented deques
•Mutating vs Accessor: Know which operations change the deque and which don't
•Stack and Queue patterns: addRear+removeRear = stack; addRear+removeFront = queue
•Peek before remove: Use peek to inspect without modifying
•Always check isEmpty(): Before removeFront/removeRear/peekFront/peekRear
•Composition creates algorithms: Sliding window max, palindrome check, priority queues all use composed operations
•Language variations exist: Know your language's specific method names and behaviors

What's Next:

With operations mastered, we'll explore how the deque generalizes both stacks and queues in the next page. Understanding this relationship deepens your intuition for when to use each structure.

Page Complete

You now command all eight deque operations with precision. You understand their semantics, edge cases, and how they compose into powerful algorithms. Next, we explore the deque's role as a generalization of stacks and queues.

2 / 4

Loading learning content...

Data Structures & AlgorithmsDouble-Ended Queue (Deque)

Double-Ended Queue (Deque) — Flexible Two-End Access

LevelIntermediate

Duration55 mins

TopicDouble-Ended Queue (Deque)

2 / 4

Operations — Add and Remove at Both Ends

Mastering the Deque Interface

What You Will Learn

The Complete Deque Operation Set

A deque provides eight core operations that fall into three categories:

Mutating Operations (modify the deque):

addFront(element) — Insert at the front
addRear(element) — Insert at the rear
removeFront() — Remove from the front
removeRear() — Remove from the rear

Accessor Operations (inspect without modifying):

peekFront() — View the front element
peekRear() — View the rear element

State Query Operations (check deque state):

isEmpty() — Is the deque empty?
size() — How many elements are present?

Deque Operations at a Glance
Operation	Category	Returns	Modifies Deque?	Typical Complexity
addFront(e)	Mutating	void	Yes	O(1)
addRear(e)	Mutating	void	Yes	O(1)
removeFront()	Mutating	element	Yes	O(1)
removeRear()	Mutating	element	Yes	O(1)
peekFront()	Accessor	element	No	O(1)
peekRear()	Accessor	element	No	O(1)
isEmpty()	State Query	boolean	No	O(1)
size()	State Query	integer	No	O(1)

Naming Conventions Vary

addFront — Inserting at the Front

Precise Semantics:

Precondition:  deque is a valid deque (possibly empty)
               element is a valid value of the deque's element type

Postcondition: size(deque) = old_size + 1
               peekFront() returns element
               all previous elements maintain their relative order
               the element previously at front is now at position 1

Operation Trace:

Step	Deque State	Operation	Result
0	`[]`	Initial (empty)	—
1	`[A]`	`addFront(A)`	A is at front and rear
2	`[B, A]`	`addFront(B)`	B is at front, A at rear
3	`[C, B, A]`	`addFront(C)`	C at front, A at rear
4	`[D, C, B, A]`	`addFront(D)`	D at front, A at rear

No Shifting in Efficient Implementations

addFront_example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Using addFront for priority insertion
class Task {
    constructor(public name: string, public priority: "normal" | "high") {}
}
 
// Deque-based task queue with priority support
function scheduleTask(deque: Deque<Task>, task: Task): void {
    if (task.priority === "high") {
        // High priority: insert at front (will be processed first)
        deque.addFront(task);
    } else {
        // Normal priority: insert at rear (wait in line)
        deque.addRear(task);
    }
}
 
// Usage
const taskQueue = new Deque<Task>();
scheduleTask(taskQueue, new Task("Email", "normal"));  // Goes to rear
scheduleTask(taskQueue, new Task("Bug Fix", "high"));  // Goes to front
// Deque state: [Bug Fix, Email]

Key Use Cases for addFront:

Priority insertion: When a high-priority item must skip ahead
Undo stacks: When the most recent action must be at the front
Prefix building: Constructing sequences from end to beginning
Work-stealing: Adding work at one's own end of a shared deque

addRear — Inserting at the Rear

The addRear operation inserts a new element at the rear of the deque. This is the most common insertion operation and mirrors how queues naturally grow—new elements join at the end.

Precise Semantics:

Precondition:  deque is a valid deque (possibly empty)
               element is a valid value of the deque's element type

Postcondition: size(deque) = old_size + 1
               peekRear() returns element
               all previous elements maintain their positions
               the element previously at rear is now at position (size - 2)

Operation Trace:

Step	Deque State	Operation	Result
0	`[]`	Initial (empty)	—
1	`[A]`	`addRear(A)`	A is at front and rear
2	`[A, B]`	`addRear(B)`	A at front, B at rear
3	`[A, B, C]`	`addRear(C)`	A at front, C at rear
4	`[A, B, C, D]`	`addRear(D)`	A at front, D at rear

The Natural Growth Direction

addRear_example
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
// Building a browsing history with addRear
interface HistoryEntry {
    url: string;
    timestamp: Date;
}
 
class BrowsingHistory {
    private history = new Deque<HistoryEntry>();
    private maxSize = 100;  // Limit history size
 
    visit(url: string): void {
        const entry: HistoryEntry = {
            url,
            timestamp: new Date()
        };
        
        // Add to rear (most recent is always at rear)
        this.history.addRear(entry);
        
        // Trim if exceeding max size (remove oldest from front)
        while (this.history.size() > this.maxSize) {
            this.history.removeFront();
        }
    }
 
    getMostRecent(): HistoryEntry | undefined {
        return this.history.isEmpty() ? undefined : this.history.peekRear();
    }
 
    getOldest(): HistoryEntry | undefined {
        return this.history.isEmpty() ? undefined : this.history.peekFront();
    }
}

Key Use Cases for addRear:

Queue-like behavior: Standard enqueue operation (FIFO processing)
History tracking: New events join chronologically at the end
Buffer building: Accumulating data as it arrives
Log management: Appending new log entries

removeFront — Removing from the Front

The removeFront operation removes and returns the element at the front of the deque. After this operation, the element that was second becomes the new front, and the deque's size decreases by one.

Precise Semantics:

Precondition:  deque is non-empty
               (behavior on empty deque is implementation-defined:
                throw exception, return null, undefined behavior, etc.)

Postcondition: size(deque) = old_size - 1
               returns the element that was at position 0
               element at position 1 becomes new position 0
               all remaining elements shift conceptually left

Operation Trace:

Step	Deque State	Operation	Return Value	New State
0	`[A, B, C, D]`	Initial	—	—
1	`[B, C, D]`	`removeFront()`	A	B at front
2	`[C, D]`	`removeFront()`	B	C at front
3	`[D]`	`removeFront()`	C	D at front and rear
4	`[]`	`removeFront()`	D	Empty deque

Empty Deque Behavior

removeFront_example
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
// Processing a task queue with removeFront
interface Task {
    id: string;
    name: string;
    createdAt: Date;
}
 
class TaskProcessor {
    private queue = new Deque<Task>();
 
    enqueue(task: Task): void {
        this.queue.addRear(task);  // Join at the end
    }
 
    processNext(): Task | null {
        if (this.queue.isEmpty()) {
            console.log("No tasks to process");
            return null;
        }
 
        // Remove from front (FIFO: oldest task processed first)
        const task = this.queue.removeFront();
        console.log(`Processing: ${task.name}`);
        return task;
    }
 
    // Peek at next task without removing
    peekNext(): Task | null {
        return this.queue.isEmpty() ? null : this.queue.peekFront();
    }
 
    pendingCount(): number {
        return this.queue.size();
    }
}
 
// Usage
const processor = new TaskProcessor();
processor.enqueue({ id: "1", name: "Task A", createdAt: new Date() });
processor.enqueue({ id: "2", name: "Task B", createdAt: new Date() });
processor.processNext();  // Returns Task A (first in, first out)

Key Use Cases for removeFront:

Queue processing: Standard dequeue operation (FIFO)
Sliding window: Remove elements that fall out of the window
BFS traversal: Remove the next node to visit
Bounded buffers: Remove oldest when buffer is full

removeRear — Removing from the Rear

Precise Semantics:

Precondition:  deque is non-empty
               (behavior on empty deque is implementation-defined)

Postcondition: size(deque) = old_size - 1
               returns the element that was at position (old_size - 1)
               the element at position (old_size - 2) becomes the new rear
               front remains unchanged (unless it was the only element)

Operation Trace:

Step	Deque State	Operation	Return Value	New State
0	`[A, B, C, D]`	Initial	—	—
1	`[A, B, C]`	`removeRear()`	D	C at rear
2	`[A, B]`	`removeRear()`	C	B at rear
3	`[A]`	`removeRear()`	B	A at front and rear
4	`[]`	`removeRear()`	A	Empty deque

Stack Behavior via Deque

removeRear_example
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
// Implementing undo/redo with deque and removeRear
interface Command {
    execute(): void;
    undo(): void;
    description: string;
}
 
class UndoableEditor {
    private text = "";
    private undoStack = new Deque<Command>();
    private redoStack = new Deque<Command>();
 
    execute(command: Command): void {
        command.execute();
        this.undoStack.addRear(command);  // Most recent at rear
        
        // Clear redo stack when new command is executed
        while (!this.redoStack.isEmpty()) {
            this.redoStack.removeRear();
        }
    }
 
    undo(): boolean {
        if (this.undoStack.isEmpty()) {
            return false;
        }
 
        // Remove most recent command from rear (LIFO)
        const command = this.undoStack.removeRear();
        command.undo();
        this.redoStack.addRear(command);  // Save for redo
        return true;
    }
 
    redo(): boolean {
        if (this.redoStack.isEmpty()) {
            return false;
        }
 
        // Re-execute most recently undone command
        const command = this.redoStack.removeRear();
        command.execute();
        this.undoStack.addRear(command);  // Back to undo stack
        return true;
    }
}

Key Use Cases for removeRear:

Undo operations: Remove the most recent action to reverse it
Backtracking algorithms: Pop the last decision when hitting a dead end
Monotonic deque maintenance: Remove elements violated by a new addition
Parsing with rollback: Undo token consumption on parse failure

peekFront and peekRear — Inspecting Without Modifying

Why Peek Matters:

Many algorithms need to examine an element before deciding what to do with it. Without peek, you'd have to:

Remove the element
Examine it
Decide whether to keep or discard it
If keeping, re-add it to the same position

This is both inefficient and error-prone. Peek simplifies this to a single, non-destructive inspection.

peekFront

•Purpose: View the element at the front
•Returns: The front element
•Side Effects: None
•On Empty Deque: Undefined/exception
•Time Complexity: O(1)
•Synonyms: front(), getFirst(), first()

peekRear

•Purpose: View the element at the rear
•Returns: The rear element
•Side Effects: None
•On Empty Deque: Undefined/exception
•Time Complexity: O(1)
•Synonyms: back(), getLast(), last()

peek_example
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
// Using peek for palindrome checking
function isPalindrome(deque: Deque<string>): boolean {
    while (deque.size() > 1) {
        // Compare front and rear without removing first
        const front = deque.peekFront();
        const rear = deque.peekRear();
 
        if (front !== rear) {
            return false;  // Mismatch found
        }
 
        // Only remove after confirming match
        deque.removeFront();
        deque.removeRear();
    }
 
    // 0 or 1 element remaining means palindrome
    return true;
}
 
// Usage
function checkPalindrome(str: string): boolean {
    const deque = new Deque<string>();
    
    // Add each character to deque
    for (const char of str.toLowerCase().replace(/[^a-z]/g, '')) {
        deque.addRear(char);
    }
    
    return isPalindrome(deque);
}
 
console.log(checkPalindrome("racecar"));  // true
console.log(checkPalindrome("hello"));    // false

Safe Peek Patterns

isEmpty and size — Querying Deque State

The isEmpty and size operations provide metadata about the deque's current state. They're essential for safe operation and algorithm control flow.

isEmpty():

Returns true if the deque contains no elements
Returns false if the deque contains one or more elements
Time Complexity: O(1)
Use Case: Guard before removal operations

size():

Returns the current number of elements in the deque
Returns 0 if the deque is empty
Time Complexity: O(1)
Use Case: Capacity checks, loop bounds, progress tracking

The Relationship Between isEmpty and size:

isEmpty() ≡ (size() == 0)
!isEmpty() ≡ (size() > 0)

state_query_example
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
// Using isEmpty and size for safe deque operations
class SafeDeque<T> {
    private deque = new Deque<T>();
 
    // Safe remove with explicit empty handling
    removeFrontSafe(): T | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return this.deque.removeFront();
    }
 
    // Process all elements with size-based loop
    processAll(processor: (item: T) => void): number {
        let processed = 0;
        const total = this.deque.size();  // Capture initial size
        
        console.log(`Processing ${total} items...`);
        
        while (!this.deque.isEmpty()) {
            const item = this.deque.removeFront();
            processor(item);
            processed++;
            
            // Progress tracking
            console.log(`Progress: ${processed}/${total}`);
        }
        
        return processed;
    }
 
    // Size-limited addition
    addRearLimited(item: T, maxSize: number): boolean {
        if (this.deque.size() >= maxSize) {
            // At capacity, reject or remove oldest
            return false;  // Option 1: Reject
            // this.deque.removeFront();  // Option 2: Remove oldest
        }
        this.deque.addRear(item);
        return true;
    }
}

Beware of Size in Loops

Composing Operations — Powerful Patterns

Individual deque operations are building blocks. The real power emerges when you compose them into patterns. Let's explore common operation compositions:

Pattern 1: Queue Discipline (FIFO)

Use only: addRear + removeFront
Result: Standard queue behavior

Pattern 2: Stack Discipline (LIFO)

Use only: addRear + removeRear (or addFront + removeFront)
Result: Standard stack behavior

Pattern 3: Priority Injection

Normal: addRear
High priority: addFront
Processing: removeFront
Result: Queue with priority bypass

Pattern 4: Sliding Window

Add new: addRear
Remove stale: removeFront
Maintain property: peekFront, peekRear, removeRear (for monotonic property)
Result: Efficient sliding window algorithms

sliding_window_max
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
/**
 * Sliding Window Maximum using Deque
 * 
 * Given an array nums and window size k, return an array of maximum
 * values in each sliding window position.
 * 
 * Time Complexity: O(n) - each element added/removed at most once
 * Space Complexity: O(k) - deque holds at most k elements
 */
function slidingWindowMax(nums: number[], k: number): number[] {
    const result: number[] = [];
    const deque = new Deque<number>();  // Stores indices
 
    for (let i = 0; i < nums.length; i++) {
        // 1. Remove indices that are out of the current window (from front)
        while (!deque.isEmpty() && deque.peekFront() <= i - k) {
            deque.removeFront();
        }
 
        // 2. Remove indices of elements smaller than current (from rear)
        //    They can never be the maximum in any future window
        while (!deque.isEmpty() && nums[deque.peekRear()] < nums[i]) {
            deque.removeRear();
        }
 
        // 3. Add current index to rear
        deque.addRear(i);
 
        // 4. Once we have a full window, record the maximum
        if (i >= k - 1) {
            result.push(nums[deque.peekFront()]);
        }
    }
 
    return result;
}
 
// Example usage
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(slidingWindowMax(nums, k));  // [3, 3, 5, 5, 6, 7]

The Monotonic Deque Pattern

Edge Cases and Error Handling

Robust deque usage requires careful attention to edge cases. Let's catalog the scenarios that trip up programmers:

Edge Case 1: Empty Deque Operations

removeFront() on empty → Exception or undefined
removeRear() on empty → Exception or undefined
peekFront() on empty → Exception, null, or undefined
peekRear() on empty → Exception, null, or undefined

Edge Case 2: Single-Element Deque

After addFront(x) to empty: peekFront() == peekRear() == x
removeFront() and removeRear() return the same element
Removing makes the deque empty

Edge Case 3: Sequence Matters

addFront(A); addFront(B) → [B, A] (B at front)
addRear(A); addRear(B) → [A, B] (A at front)
Order of operations determines final arrangement

edge_case_handling
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
// Comprehensive edge case handling for deque operations
class RobustDeque<T> {
    private deque = new Deque<T>();
 
    // Safe removal with Optional pattern
    removeFrontOptional(): { value: T } | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return { value: this.deque.removeFront() };
    }
 
    removeRearOptional(): { value: T } | null {
        if (this.deque.isEmpty()) {
            return null;
        }
        return { value: this.deque.removeRear() };
    }
 
    // Safe peek with default value
    peekFrontOrDefault(defaultValue: T): T {
        return this.deque.isEmpty() ? defaultValue : this.deque.peekFront();
    }
 
    peekRearOrDefault(defaultValue: T): T {
        return this.deque.isEmpty() ? defaultValue : this.deque.peekRear();
    }
 
    // Batch operations with transaction semantics
    addMultipleFront(items: T[]): void {
        // Add in reverse order so first item ends up at front
        for (let i = items.length - 1; i >= 0; i--) {
            this.deque.addFront(items[i]);
        }
    }
 
    addMultipleRear(items: T[]): void {
        for (const item of items) {
            this.deque.addRear(item);
        }
    }
 
    // Drain all elements (clear with return)
    drainAll(): T[] {
        const result: T[] = [];
        while (!this.deque.isEmpty()) {
            result.push(this.deque.removeFront());
        }
        return result;
    }
}

Never Assume Non-Empty

The most common deque bug is calling remove or peek without checking isEmpty(). Even if you 'know' the deque has elements, defensive programming saves debugging time. Make empty checks a habit.

Summary: Mastering Deque Operations

You've now mastered all fundamental deque operations. Let's consolidate:

Key Takeaways

•Eight core operations: addFront, addRear, removeFront, removeRear, peekFront, peekRear, isEmpty, size
•All operations are O(1) in properly implemented deques
•Mutating vs Accessor: Know which operations change the deque and which don't
•Stack and Queue patterns: addRear+removeRear = stack; addRear+removeFront = queue
•Peek before remove: Use peek to inspect without modifying
•Always check isEmpty(): Before removeFront/removeRear/peekFront/peekRear
•Composition creates algorithms: Sliding window max, palindrome check, priority queues all use composed operations
•Language variations exist: Know your language's specific method names and behaviors

What's Next:

With operations mastered, we'll explore how the deque generalizes both stacks and queues in the next page. Understanding this relationship deepens your intuition for when to use each structure.

Page Complete

2 / 4