PYTHON
Efficient Queues and Stacks with Python's collections.deque
Learn to use Python's collections.deque for high-performance additions and removals from both ends, ideal for implementing efficient queues, stacks, or recent item lists.
from collections import deque
# Using deque as a queue (FIFO)
my_queue = deque()
my_queue.append("task1")
my_queue.append("task2")
print(f"Queue after appends: {my_queue}")
first_item = my_queue.popleft()
print(f"Popped from left: {first_item}, Queue remaining: {my_queue}")
# Using deque as a stack (LIFO)
my_stack = deque()
my_stack.append("itemA")
my_stack.append("itemB")
print(f"Stack after appends: {my_stack}")
last_item = my_stack.pop() # pop from right is efficient
print(f"Popped from right: {last_item}, Stack remaining: {my_stack}")
# Limiting deque size (e.g., for recent history)
history = deque(maxlen=3)
history.append("page1")
history.append("page2")
history.append("page3")
print(f"History (full): {history}")
history.append("page4") # page1 is automatically removed
print(f"History (new item added, oldest removed): {history}")
How it works: The collections.deque (double-ended queue) provides an optimized way to add or remove elements from both the left and right sides of a sequence with O(1) complexity. This makes it highly efficient for implementing queues (FIFO - First In, First Out) using append() and popleft(), or stacks (LIFO - Last In, First Out) using append() and pop(). Deques can also be initialized with a maxlen parameter to automatically discard older items when new ones are added, perfect for maintaining a fixed-size history or log.