PYTHON
Implementing Stacks and Queues with collections.deque
Learn to efficiently implement both LIFO (stack) and FIFO (queue) data structures in Python using the high-performance `collections.deque`.
from collections import deque
# --- Implementing a Stack (LIFO: Last In, First Out) ---
# deque supports efficient append and pop from the right end, perfect for a stack
stack = deque()
# Push elements onto the stack
stack.append('Task 1')
stack.append('Task 2')
stack.append('Task 3')
print(f"Stack after pushes: {stack}") # deque(['Task 1', 'Task 2', 'Task 3'])
# Pop elements from the stack
popped_item = stack.pop()
print(f"Popped from stack: {popped_item}") # Task 3
print(f"Stack after pop: {stack}") # deque(['Task 1', 'Task 2'])
popped_item = stack.pop()
print(f"Popped from stack: {popped_item}") # Task 2
# --- Implementing a Queue (FIFO: First In, First Out) ---
# deque supports efficient append from the right and pop from the left
queue = deque()
# Enqueue elements into the queue
queue.append('User A')
queue.append('User B')
queue.append('User C')
print(f"Queue after enqueues: {queue}") # deque(['User A', 'User B', 'User C'])
# Dequeue elements from the queue
dequeued_item = queue.popleft()
print(f"Dequeued from queue: {dequeued_item}") # User A
print(f"Queue after dequeue: {queue}") # deque(['User B', 'User C'])
dequeued_item = queue.popleft()
print(f"Dequeued from queue: {dequeued_item}") # User B
How it works: The `collections.deque` (double-ended queue) is a highly efficient data structure in Python, ideal for implementing both stacks and queues. For stacks (Last In, First Out), `deque.append()` adds elements to one end, and `deque.pop()` removes them from the same end. For queues (First In, First Out), `deque.append()` adds elements to the right, while `deque.popleft()` efficiently removes elements from the left. Its O(1) performance for adding and removing elements from either end makes it superior to standard Python lists for these use cases.