Stack & Queue • Data Structures

Deque (Double Ended Queue)

A specialized, highly flexible queue where insertion and deletion can occur at BOTH ends. It combines the capabilities of both Stacks and Queues.

The "Swiss Army Knife"

Because you can `push_front`, `push_back`, `pop_front`, and `pop_back`, a Deque can emulate a Stack (using only push_back/pop_back) OR emulate a Queue (using push_back/pop_front).

Implementation

Typically implemented via a doubly-linked list or a circular array. Modern language standard libraries (like C++ `std::deque` or Python `collections.deque`) highly optimize this structure for O(1) operations on both ends.

Common Use Cases

Sliding Window Maximum problem (Monotonic Deque)
Palindrome checking (comparing front and back)
A-Steal Job Scheduling (processors can steal jobs from the back of another's queue)

Loading Lab...

Stack & Queue • Data Structures

Deque (Double Ended Queue)

A specialized, highly flexible queue where insertion and deletion can occur at BOTH ends. It combines the capabilities of both Stacks and Queues.

The "Swiss Army Knife"

Because you can `push_front`, `push_back`, `pop_front`, and `pop_back`, a Deque can emulate a Stack (using only push_back/pop_back) OR emulate a Queue (using push_back/pop_front).

Implementation

Common Use Cases

Sliding Window Maximum problem (Monotonic Deque)
Palindrome checking (comparing front and back)
A-Steal Job Scheduling (processors can steal jobs from the back of another's queue)

Deque Basics

Deque Basics

Deque (Double Ended Queue)

The "Swiss Army Knife"

Implementation

Common Use Cases

Deque (Double Ended Queue)

The "Swiss Army Knife"

Implementation

Common Use Cases