Deque in Python

A deque (short for double-ended queue) is a data structure that allows inserting and removing elements from both ends efficiently. Python provides a built-in collections.deque class that is optimized for fast appends and pops from both ends.

1. Why Use a Deque Instead of a List?

Python lists (list) support adding and removing elements from both ends, but operations on the left side (beginning) can be slow because lists are implemented as dynamic arrays.

Time Complexity Comparison

Operation	list (Time Complexity)	deque (Time Complexity)
Append to right (append())	O(1)O(1)O(1)	O(1)O(1)O(1)
Pop from right (pop())	O(1)O(1)O(1)	O(1)O(1)O(1)
Insert at left (insert(0, x))	O(n)O(n)O(n)	O(1)O(1)O(1)
Pop from left (pop(0))	O(n)O(n)O(n)	O(1)O(1)O(1)

• If you frequently need to add or remove elements from both ends, use collections.deque instead of a list.

2. Creating a Deque

You must import deque from the collections module before using it.

from collections import deque

# Creating an empty deque
d = deque()

# Creating a deque with initial elements
d = deque([1, 2, 3, 4, 5])

print(d)

Output:

deque([1, 2, 3, 4, 5])

3. Basic Operations on Deque

3.1. Adding Elements

Method	Description
append(x)	Add x to the right (end)
appendleft(x)	Add x to the left (beginning)
extend(iterable)	Add multiple elements to the right
extendleft(iterable)	Add multiple elements to the left (added in reverse order)

Example

d = deque([2, 3, 4])

# Append to right
d.append(5)
print(d)

# Append to left
d.appendleft(1)
print(d)

# Extend right
d.extend([6, 7])
print(d)

# Extend left
d.extendleft([0, -1])
print(d)

Output:

deque([2, 3, 4, 5])
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4, 5, 6, 7])
deque([-1, 0, 1, 2, 3, 4, 5, 6, 7])

Note: extendleft(iterable) adds elements in reverse order.

3.2. Removing Elements

Method	Description
pop()	Remove and return the rightmost element
popleft()	Remove and return the leftmost element
remove(x)	Remove first occurrence of x
clear()	Remove all elements

Example:

d = deque([10, 20, 30, 40, 50])

# Pop from right
d.pop()
print(d)

# Pop from left
d.popleft()
print(d)

# Remove specific element
d.remove(30)
print(d)

# Clear the deque
d.clear()
print(d)

Output:

deque([10, 20, 30, 40])
deque([20, 30, 40])
deque([20, 40])
deque([])

3.3. Accessing Elements

Deque supports indexing like lists.

d = deque([10, 20, 30, 40, 50])

print(d[0])   # First element
print(d[-1])  # Last element

Output:

10
50

However, slicing (e.g., d[1:3]) is not supported. You must convert it to a list first: list(d)[1:3].

4. Rotating the Deque

Method	Description
rotate(n)	Rotate n places to the right. If n is negative, rotate left.

Example

d = deque([1, 2, 3, 4, 5])

# Rotate right by 2 positions
d.rotate(2)
print(d)

# Rotate left by 1 position
d.rotate(-1)
print(d)

Output:

deque([4, 5, 1, 2, 3])
deque([5, 1, 2, 3, 4])

5. Maximum Length (Bounded Deques)

A deque can have a maximum size (maxlen). When it exceeds this limit, the oldest element is automatically removed.

Example

d = deque(maxlen=3)

d.append(1)
d.append(2)
d.append(3)
print(d)

d.append(4)  # Oldest element (1) is removed
print(d)

Output:

deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)

Useful for implementing caches, logs, or sliding windows.

6. Deque as a Stack (LIFO)

Stack Operation	Deque Method
Push (add to top)	append(x)
Pop (remove from top)	pop()

Example

stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)

print(stack)

# Pop elements (LIFO)
print(stack.pop())
print(stack.pop())

Output:

deque([10, 20, 30])
30
20

7. Deque as a Queue (FIFO)

Queue Operation	Deque Method
Enqueue (add to rear)	append(x)
Dequeue (remove from front)	popleft()

Example

queue = deque()

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print(queue)

# Dequeue elements (FIFO)
print(queue.popleft())
print(queue.popleft())

Output:

deque([10, 20, 30])
10
20

8. Thread-Safe Deques

deque is thread-safe for append/pop operations from both ends without needing locks. However, for complex operations, threading.Lock is recommended.

Conclusion

• deque is faster than lists for appending/removing at both ends.
• It can function as stack, queue, or circular buffer.
• Supports rotations, bounded size, and efficient memory usage.