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

Double-Ended Queues

Explore double-ended queues or deques, which allow insertion and deletion at both the front and rear ends with O(1) efficiency. Understand deque operations using Python's collections module, see their use in problems like sliding windows and palindrome checks, and learn how deques provide versatile data structure behavior beyond queues and stacks.

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 3.14.0
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]
print("Front element is:", front_element)
# Peek at rear
rear_element = dq[-1]
print("Rear element is:", rear_element)
# Check if empty
is_empty = len(dq) == 0
print( "Is the queue empty?" , is_empty)
# Get size
size = len(dq)
Implementation of a deque

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 ...