What is Deque: Definition, Usage, and Examples

A deque (double-ended queue) is a data structure that allows adding and removing items from both the front and the back efficiently. It combines features of stacks and queues, making it flexible for many programming tasks.

How It Works

A deque works like a line of people where you can join or leave from either the front or the back. Imagine a queue at a coffee shop where customers can enter or exit from both ends instead of just one. This makes it very flexible compared to a regular queue where you can only add at the back and remove from the front.

Internally, a deque is often implemented using a linked list or a dynamic array that supports fast insertions and deletions at both ends. This means operations like adding or removing items from either side happen quickly without shifting many elements.

Example

This example shows how to use a deque in Python to add and remove elements from both ends.

python

from collections import deque

# Create a deque
my_deque = deque()

# Add elements to the right (back)
my_deque.append('apple')
my_deque.append('banana')

# Add elements to the left (front)
my_deque.appendleft('cherry')

# Remove element from the right (back)
right_item = my_deque.pop()

# Remove element from the left (front)
left_item = my_deque.popleft()

print('Deque after operations:', list(my_deque))
print('Removed from right:', right_item)
print('Removed from left:', left_item)

Output

Deque after operations: ['apple']
Removed from right: banana
Removed from left: cherry

When to Use

Use a deque when you need a flexible data structure that can add or remove items quickly from both ends. It is useful in scenarios like:

• Implementing undo/redo features where you add and remove actions from both ends.
• Sliding window problems where you keep track of elements in a moving range.
• Breadth-first search (BFS) algorithms where nodes are added and removed from the front and back.
• Any situation where you want the speed of a queue but also need to access or modify the front and back efficiently.

Key Points

• A deque allows adding/removing from both front and back.
• It combines features of stacks and queues.
• Operations at both ends are fast and efficient.
• Commonly used in algorithms and real-time data processing.

Key Takeaways

A deque lets you add or remove items from both ends quickly.

It is more flexible than a regular queue or stack.

Use it for tasks needing fast front and back access.

Common in algorithms like BFS and sliding window problems.