Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Double-Ended Queues

Explore how double-ended queues, or deques, provide versatile data handling by supporting efficient insertion and deletion from both ends. Learn their implementation in C++, core operations with O(1) time complexity, variations like input/output restricted deques, and practical applications such as sliding window problems and undo/redo functionality.

We'll cover the following...

A deque stands for a double-ended queue. It is a more flexible version of a queue that allows insertion and deletion from both the front and the rear.

In a normal queue, insertion happens only at the rear and deletion happens only at the front. In a deque, both ends are fully active.

Visualization of a deque
Visualization of a deque

This makes the deque a generalization that can behave like a queue, a stack, or something in between, depending on how it is used.

A deque is useful when a problem needs controlled access to both ends of the structure. It appears in sliding window problems, palindrome checking, scheduling, and caching systems.

Example

To understand how a deque works, consider the following example. If a deque currently contains:

A deque with 3 elements
A deque with 3 elements

After inserting 88 at the front, the deque becomes:

Inserting an element at the front of a deque
Inserting an element at the front of a deque

After inserting 91 at the rear, the deque becomes:

Inserting an element at the rear of a deque
Inserting an element at the rear of a deque

After removing 88 from the front, the deque becomes:

Removing an element from the front of a deque
Removing an element from the front of a deque

After removing 91 from the rear, the deque becomes:

Removing an element from the rear of a deque
Removing an element from the rear of a deque

This two-sided behavior is what makes the deque more versatile than a regular queue.

C++ implementation

C++ provides std::deque (double-ended queue) in the <deque> header. Unlike some other languages that have a separate deque class, C++'s std::deque ...