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

Double-Ended Queues

Explore how double-ended queues (deques) provide flexible insertion and deletion from both ends, offering a versatile data structure. Learn their core operations, Python's collections.deque implementation, and applications in algorithms like sliding window maximum and undo/redo functionality. Understand how deques differ from stacks and queues and why they are essential for efficient problem-solving.

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.

Python implementation

Python's standard library provides a built-in deque through the collections module, so there is no need to build one from scratch. Here's how to use it:

Python
from collections import deque
# Create an empty deque
dq = deque()
# Insert at rear
dq.append(10)
dq.append(20)
dq.append(30)
# Insert at front
dq.appendleft(5)
# Delete from rear
dq.pop()
# Delete from front
dq.popleft()
# Peek at front
front_element = dq[0]
# Peek at rear
rear_element = dq[-1]
# Check if empty
is_empty = len(dq) == 0
# Get size
size = len(dq)

Explanation

To understand the above code, consider the following breakdown of how each function operates in the deque class:

  • Lines 1–4 (Importing and creating a deque): We import the deque class from Python's collections module and create an empty deque using deque(). This built-in implementation is optimized for fast operations at both ends.

  • Lines 7–9 (Inserting at the rear): The append() method adds elements to the rear (right end) of the deque. Each call is an ...