PYTHON
Implementing Efficient Stacks and Queues with collections.deque
Learn how to use Python's collections.deque for highly efficient, thread-safe append and pop operations, ideal for building stacks and queues with O(1) performance.
from collections import deque
# As a Queue (FIFO - First-In, First-Out)
queue = deque()
queue.append("task1") # Add to the right end
queue.append("task2")
queue.append("task3")
print(f"Queue after appends: {list(queue)}")
print(f"Processing task: {queue.popleft()}") # Remove from the left end
print(f"Processing task: {queue.popleft()}")
print(f"Queue after pops: {list(queue)}")
# As a Stack (LIFO - Last-In, First-Out)
stack = deque()
stack.append("itemA") # Push onto stack (right end)
stack.append("itemB")
stack.append("itemC")
print(f"Stack after pushes: {list(stack)}")
print(f"Popping item: {stack.pop()}") # Pop from stack (right end)
print(f"Popping item: {stack.pop()}")
print(f"Stack after pops: {list(stack)}")
How it works: The `collections.deque` (double-ended queue) is a versatile data structure providing O(1) performance for appending and popping elements from both ends. This makes it ideal for implementing efficient queues (using `append()` and `popleft()`) and stacks (using `append()` and `pop()`). Unlike standard Python lists, `deque` avoids costly memory reallocations and element shifting when modifying elements at either end, offering significant performance benefits.