PYTHON
Implementing an Efficient Queue or Stack with Deque
Learn how to use Python's `collections.deque` for highly efficient queue and stack implementations, offering 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') # Enqueue
my_queue.append('task2')
print(f"Queue after appends: {list(my_queue)}") # Convert to list for display
popped_item = my_queue.popleft() # Dequeue
print(f"Popped from queue: {popped_item}, Queue remaining: {list(my_queue)}")
# As a stack (LIFO - Last In, First Out)
my_stack = deque()
my_stack.append('itemA') # Push
my_stack.append('itemB')
print(f"Stack after appends: {list(my_stack)}")
popped_item = my_stack.pop() # Pop
print(f"Popped from stack: {popped_item}, Stack remaining: {list(my_stack)}")
# Add to front (stack-like behaviour at the front)
my_deque = deque([1, 2, 3])
my_deque.appendleft(0)
print(f"Deque after appendleft: {list(my_deque)}")
How it works: The `collections.deque` (double-ended queue) is ideal for implementing queues and stacks because it allows O(1) (constant time) appends and pops from both ends. This is significantly more efficient than a standard Python list, which incurs O(n) complexity for `pop(0)` or `insert(0, item)` operations due to element shifting. It's perfect for scenarios like breadth-first searches or managing recent history.