PYTHON
Implement Stack (LIFO) or Queue (FIFO) with collections.deque
Leverage Python's collections.deque for efficient implementation of both LIFO stacks and FIFO queues. Ideal for scenarios requiring fast appends and pops from both ends.
from collections import deque
# --- Implementing a Stack (LIFO - Last-In, First-Out) ---
stack = deque()
print(f"Initial stack: {list(stack)}")
stack.append('A') # Push item 'A'
stack.append('B') # Push item 'B'
stack.append('C') # Push item 'C'
print(f"Stack after pushes: {list(stack)}")
popped_item = stack.pop() # Pop item 'C'
print(f"Popped: {popped_item}, Stack: {list(stack)}")
popped_item = stack.pop() # Pop item 'B'
print(f"Popped: {popped_item}, Stack: {list(stack)}")
# --- Implementing a Queue (FIFO - First-In, First-Out) ---
queue = deque()
print(f"
Initial queue: {list(queue)}")
queue.append('X') # Enqueue item 'X'
queue.append('Y') # Enqueue item 'Y'
queue.append('Z') # Enqueue item 'Z'
print(f"Queue after enqueues: {list(queue)}")
dequeued_item = queue.popleft() # Dequeue item 'X'
print(f"Dequeued: {dequeued_item}, Queue: {list(queue)}")
dequeued_item = queue.popleft() # Dequeue item 'Y'
print(f"Dequeued: {dequeued_item}, Queue: {list(queue)}")
How it works: `collections.deque` (double-ended queue) is a highly optimized list-like container that supports O(1) time complexity for appending and popping elements from both ends. This makes it an ideal and efficient choice for implementing LIFO (Last-In, First-Out) stacks using `append()` and `pop()`, and FIFO (First-In, First-Out) queues using `append()` and `popleft()`. Unlike standard lists, `deque` avoids costly reallocations when modifying ends.