Deque

A deque is a double-ended queue implementation in Python’s collections module. It provides a versatile data structure that generalizes a stack and a queue by allowing efficient append and pop operations from both ends of the sequence. Unlike regular lists which have O(n) time complexity for inserting or removing elements at the beginning, deques provide O(1) time complexity for these operations on both ends.

Deques are particularly useful in scenarios requiring fast access to both ends of a sequence, such as implementing queues, stacks, sliding window algorithms, and tracking recent history with a limited size buffer. They are thread-safe for append and pop operations from different threads, making them valuable for concurrent programming applications.

Syntax

from collections import deque

d = deque([iterable[, maxlen]])

Parameters:

• iterable (Optional): A parameter providing initial data for the deque. If not provided, an empty deque is created.
• maxlen (Optional): An integer specifying the maximum number of items allowed in the deque. When this limit is reached, adding new items causes items from the opposite end to be removed.

Return value:

A deque object returns a new deque object containing elements from the iterable in the same order (if provided), with an optional maximum length constraint.

Example 1: Creating and Using a Basic Deque

This example demonstrates basic deque operations including append(), appendleft(), pop(), popleft(), and index access:

from collections import deque

# Create a deque
numbers = deque([1, 2, 3, 4, 5])
print(f"Initial deque: {numbers}")

# Add elements to both ends
numbers.append(6)         # Add to the right end
numbers.appendleft(0)     # Add to the left end
print(f"After adding elements: {numbers}")

# Access elements
print(f"First element: {numbers[0]}")
print(f"Last element: {numbers[-1]}")

# Remove elements from both ends
right_element = numbers.pop()      # Remove from the right end
left_element = numbers.popleft()   # Remove from the left end
print(f"Popped from right: {right_element}")
print(f"Popped from left: {left_element}")
print(f"Final deque: {numbers}")

to clipboard
Copy to clipboard

This example results in the following output:

Initial deque: deque([1, 2, 3, 4, 5])
After adding elements: deque([0, 1, 2, 3, 4, 5, 6])
First element: 0
Last element: 6
Popped from right: 6
Popped from left: 0
Final deque: deque([1, 2, 3, 4, 5])

to clipboard
Copy to clipboard

Example 2: How to Append and Pop Items from Both Ends of a Deque

This example compares the performance of deque operations with list operations to demonstrate why deques are more efficient for certain tasks:

from collections import deque
import time

def measure_performance(operation, times=10000):
  """Measure the execution time of an operation."""
  start_time = time.perf_counter()
  operation(times)
  end_time = time.perf_counter()
  return end_time - start_time

def list_append_left(n):
  """Add elements to the beginning of a list."""
  lst = []
  for i in range(n):
    lst.insert(0, i)  # Insert at the beginning (expensive for lists)
  return lst

def deque_append_left(n):
  """Add elements to the beginning of a deque."""
  d = deque()
  for i in range(n):
    d.appendleft(i)   # Append to the left (efficient for deques)
  return d

# Compare performance for left-side operations
list_time = measure_performance(list_append_left)
deque_time = measure_performance(deque_append_left)

print(f"Time to insert 10,000 items at the beginning:")
print(f"List insert(0, item): {list_time:.6f} seconds")
print(f"Deque appendleft(): {deque_time:.6f} seconds")
print(f"Deque is approximately {list_time/deque_time:.1f}x faster")

# Demonstrate bidirectional functionality
d = deque([1, 2, 3])
print("\nBidirectional operations demonstration:")
print(f"Initial deque: {d}")

# Append operations
d.append(4)       # Add to right
d.appendleft(0)   # Add to left
print(f"After appends: {d}")

# Pop operations
right = d.pop()           # Remove from right
left = d.popleft()        # Remove from left
print(f"Popped from right: {right}")
print(f"Popped from left: {left}")
print(f"Final deque: {d}")

to clipboard
Copy to clipboard

This example results in the following output (timing results may vary):

Time to insert 10,000 items at the beginning:
List insert(0, item): 0.020001 seconds
Deque appendleft(): 0.000671 seconds
Deque is approximately 29.8x faster

Bidirectional operations demonstration:
Initial deque: deque([1, 2, 3])
After appends: deque([0, 1, 2, 3, 4])
Popped from right: 4
Popped from left: 0
Final deque: deque([1, 2, 3])

to clipboard
Copy to clipboard

Codebyte Example: How to Use Deque to Build Efficient Queues and Stacks

This example demonstrates how to implement both a queue and a stack using a deque:

from collections import deque

# Implementing a queue (FIFO) with deque
queue = deque()
print("Queue Operations (FIFO):")
# Enqueue operations
queue.append('apple')
queue.append('banana')
queue.append('cherry')
print(f"Queue after enqueuing: {queue}")

# Dequeue operations
first_item = queue.popleft()  # FIFO: first in, first out
print(f"Dequeued first item: {first_item}")
print(f"Queue after dequeuing: {queue}")

# Implementing a stack (LIFO) with deque
stack = deque()
print("\nStack Operations (LIFO):")
# Push operations
stack.append(1)
stack.append(2)
stack.append(3)
print(f"Stack after pushing items: {stack}")

# Pop operations
last_item = stack.pop()  # LIFO: last in, first out
print(f"Popped last item: {last_item}")
print(f"Stack after popping: {stack}")

# Bounded history example with maxlen
history = deque(maxlen=3)
actions = ["open file", "edit content", "save file", "close file"]
for action in actions:
  history.append(action)
print(f"\nLimited history (latest 3 actions): {history}")

to clipboard
Copy to clipboard

Frequently Asked Questions