A Deque (Double-Ended Queue) is a data structure that allows insertion and deletion of elements from both the front and the rear.

A Deque is a linear data structure; its stability depends on the specific implementation, but it preserves temporal order of insertions.

Deque vs Stack vs Queue?

A Deque is more versatile than both; it can function as a Stack (LIFO) or a Queue (FIFO) by restricting operations to specific ends.

Deque (Double-Ended Queue)

A generalized queue that supports adding and removing elements from both ends.

Deque is Empty

Ready

Speed

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

A Deque (pronounced 'deck') is like a deck of cards or a physical line where you can join or leave from either the front or the back. Unlike a standard Queue (FIFO) or Stack (LIFO), a Deque does not enforce a single direction of flow. It gives you maximum flexibility.

Think of it as a hybrid between a Stack and a Queue. It is the underlying data structure for advanced sliding window algorithms.

Concept

Deque stands for Double-Ended Queue. It allows four primary operations:

Push Front: Add an element to the head.
Push Back: Add an element to the tail.
Pop Front: Remove an element from the head.
Pop Back: Remove an element from the tail.

How it Works

Internally, a Deque is often implemented using a Doubly Linked List or a Circular Array.

In a Doubly Linked List, each node points to both prev and next, allowing O(1) insertions/deletions at both ends.
In a Circular Array, two pointers (front and rear) wrap around the array size, efficiently managing space.

Step-by-Step Breakdown

Initialize: Start with an empty collection.
Insert Front: Place value at the current front index and decrement the index (wrapping if needed).
Insert Rear: Place value at the current rear index and increment the index.
Delete: Remove value from the specified end and adjust the pointer accordingly.

When to Use

Sliding Window Maximum: Finding the max value in a moving window size 'k'.
Palindrome Checking: Checking characters from both ends simultaneously.
Deque-based BFS: aka 0-1 BFS for finding shortest paths in weighted graphs (0 or 1 weights).
Undo/Redo Operations: When history needs to be accessible from both ends.

When NOT to Use

When you only strictly need LIFO (Stack) or FIFO (Queue) behavior, simpler structures are preferred.
When random access by index is frequent (use an Array/Vector).

How to Identify

Look for problems involving sliding windows where you need to access both the newest and oldest elements efficiently, or problems explicitly mentioning 'sliding maximum' or processing a range of elements.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep