PYTHON
Implementing Efficient Queues and Stacks with collections.deque
Learn how to use Python's collections.deque for high-performance queue and stack implementations, enabling O(1) time complexity for appends and pops from both ends.
from collections import deque
# As a Queue (FIFO - First In, First Out)
my_queue = deque()
my_queue.append('task1') # Add to the right
my_queue.append('task2')
print(f"Queue after appends: {my_queue}")
first_item = my_queue.popleft() # Remove from the left
print(f"Popped from queue: {first_item}, Queue remaining: {my_queue}")
# As a Stack (LIFO - Last In, First Out)
my_stack = deque()
my_stack.append('itemA') # Push to the right
my_stack.append('itemB')
print(f"Stack after appends: {my_stack}")
last_item = my_stack.pop() # Pop from the right
print(f"Popped from stack: {last_item}, Stack remaining: {my_stack}")
# Add items to the left
my_deque = deque([1, 2, 3])
my_deque.appendleft(0)
print(f"Deque after appendleft: {my_deque}")
How it works: The collections.deque (double-ended queue) is a list-like container offering O(1) performance for appending and popping elements from either end. It's ideal for implementing efficient queues (using append() and popleft()) and stacks (using append() and pop()), outperforming standard lists for these specific operations due to its underlying linked-list like structure, which avoids costly memory reallocations.