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 deque (double-ended queue) is a generalized queue that supports adding and removing elements at both ends.

READY

FRONT

REAR

Deque holds 3 items: front is 10, rear is 30.

Value

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.

Sample Problems

Sliding Window Maximum

Find the max in every window of size k.

Design Circular Deque

Design your own implementation of a circular deque.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Queue

Circular Queue