PYTHON
Implement a Double-Ended Queue (Deque) with collections.deque
Utilize Python's collections.deque for efficient appending and popping elements from both ends of a list-like object, perfect for queues and history.
from collections import deque
# Initialize a deque
my_deque = deque([1, 2, 3])
print(f"Initial deque: {my_deque}")
# Append to the right (end)
my_deque.append(4)
print(f"After append(4): {my_deque}")
# Append to the left (beginning)
my_deque.appendleft(0)
print(f"After appendleft(0): {my_deque}")
# Pop from the right (end)
popped_right = my_deque.pop()
print(f"Popped from right: {popped_right}, Deque: {my_deque}")
# Pop from the left (beginning)
popped_left = my_deque.popleft()
print(f"Popped from left: {popped_left}, Deque: {my_deque}")
# Deque with a fixed maximum length (e.g., for a history buffer)
history = deque(maxlen=3)
history.append('a')
history.append('b')
history.append('c')
print(f"History (3 items): {history}")
history.append('d') # 'a' is automatically discarded
print(f"History after 'd' (a discarded): {history}")
# Expected output:
# Initial deque: deque([1, 2, 3])
# After append(4): deque([1, 2, 3, 4])
# After appendleft(0): deque([0, 1, 2, 3, 4])
# Popped from right: 4, Deque: deque([0, 1, 2, 3])
# Popped from left: 0, Deque: deque([1, 2, 3])
# History (3 items): deque(['a', 'b', 'c'])
# History after 'd' (a discarded): deque(['b', 'c', 'd'])
How it works: The `collections.deque` (double-ended queue) is a list-like container offering O(1) time complexity for appending and popping elements from both ends. Unlike standard Python lists, which are efficient only for appends/pops at the end (O(1)) but slow for operations at the beginning (O(n)), `deque` maintains efficiency at both ends. This makes it ideal for implementing queues, stacks, or any scenario requiring efficient 'first-in, first-out' (FIFO) or 'last-in, first-out' (LIFO) behavior, as well as maintaining a fixed-size 'history' where older items are automatically discarded.