Collections
Deque
Double-Ended Queue
Your text editor needs undo (stack) and your print queue needs first-come-first-served
(queue). Using a list for queue is slow - pop(0) is O(n). Deque gives you O(1)
operations on both ends.
Undo with a stack
Use deque as a stack for undo functionality.
stack_undo.py
from collections import deque
def main():
# Undo history using deque as stack
undo_history = deque()
current_text = ""
print("=== Text Editor with Undo ===\n")
# Perform actions (each saves state to undo stack)
current_text = perform_action(undo_history, current_text, "Hello")
current_text = perform_action(undo_history, current_text, " World")
current_text = perform_action(undo_history, current_text, "!")
# More editing actions
current_text = perform_action(undo_history, current_text, " How")
current_text = perform_action(undo_history, current_text, " are")
current_text = perform_action(undo_history, current_text, " you?")
print(f'Current text: "{current_text}"')
print(f"Undo stack size: {len(undo_history)}")
# Undo operations
print("\n=== Performing Undo ===")
current_text = undo(undo_history, current_text)
current_text = undo(undo_history, current_text)
print(f'\nAfter 2 undos: "{current_text}"')
# Undo more actions
current_text = undo(undo_history, current_text)
current_text = undo(undo_history, current_text)
print(f'After more undos: "{current_text}"')
def perform_action(history, current, addition):
history.append(current) # Save current state (push)
new_text = current + addition
print(f'Action: Add "{addition}" → "{new_text}"')
return new_text
def undo(history, current):
if history: # Check if not empty
previous = history.pop() # Get previous state
print(f'Undo: "{current}" → "{previous}"')
return previous
else:
print("Nothing to undo!")
return current
main()
append() pushes, pop() pops from right. Last in, first out.
deque
Double-ended queue from `collections`. O(1) operations on both ends.
Process tasks in order
Use deque as a queue for FIFO processing.
queue_tasks.py
from collections import deque
def main():
# Task queue - process in order received
task_queue = deque()
print("=== Task Queue System ===\n")
# Add tasks to queue
print("Adding tasks:")
task_queue.append("Process order #101")
print(" Added: Process order #101")
task_queue.append("Send confirmation email")
print(" Added: Send confirmation email")
task_queue.append("Update inventory")
print(" Added: Update inventory")
# Add more tasks
task_queue.append("Generate report")
task_queue.append("Notify warehouse")
task_queue.append("Archive order")
print(" Added 3 more tasks...")
print(f"\nQueue: {list(task_queue)}")
print(f"Tasks pending: {len(task_queue)}")
# Process tasks in order
print("\n=== Processing Tasks ===")
task_num = 1
while task_queue:
task = task_queue.popleft() # Remove from FRONT
print(f"{task_num}. {task} ✓")
task_num += 1
print("\n=== All tasks completed! ===")
print(f"Queue empty: {len(task_queue) == 0}")
main()
append() adds to right, popleft() removes from left. First in, first out.
popleft
Remove from left end: O(1) unlike list's `pop(0)` which is O(n).
Work with both ends
Add and remove from either end.
deque_both_ends.py
from collections import deque
def main():
# Deque allows operations on both ends
d = deque()
print("=== Adding to Both Ends ===")
# Add to right
d.append(2)
print(f"append(2): {list(d)}")
d.append(3)
print(f"append(3): {list(d)}")
# Add to left
d.appendleft(1)
print(f"appendleft(1): {list(d)}")
d.appendleft(0)
print(f"appendleft(0): {list(d)}")
# Access without removing
print("\n=== Access Elements ===")
print(f"d[0] (leftmost): {d[0]}")
print(f"d[-1] (rightmost): {d[-1]}")
print(f"d[2] (index 2): {d[2]}")
# Remove from both ends
print("\n=== Removing from Both Ends ===")
print(f"Current: {list(d)}")
left = d.popleft()
print(f"popleft() → {left}, deque now: {list(d)}")
right = d.pop()
print(f"pop() → {right}, deque now: {list(d)}")
# Practical: Palindrome check
print("\n=== Palindrome Check ===")
def is_palindrome(s):
# Remove non-letters and lowercase
chars = deque(c.lower() for c in s if c.isalpha())
while len(chars) > 1:
if chars.popleft() != chars.pop():
return False
return True
test_words = ["radar", "hello", "A man a plan a canal Panama"]
for word in test_words:
result = "✓ Palindrome" if is_palindrome(word) else "✗ Not palindrome"
print(f'"{word}" → {result}')
main()
appendleft() adds to left, pop() removes from right. Full flexibility.
Sliding window with maxlen
Keep only the N most recent items.
maxlen_window.py
from collections import deque
def main():
# Deque with maxlen - automatic sliding window
recent_temps =
print("=== Weather Station (Last 5 Readings) ===\n")
# Simulate temperature readings
temperatures = [72, 74, 71, 75, 78, 80, 76, 73, 70, 68]
for temp in temperatures:
recent_temps.append(temp) # Old items auto-removed!
avg = sum(recent_temps) / len(recent_temps)
print(f"Reading: {temp}°F | Recent: {list(recent_temps)} | Avg: {avg:.1f}°F")
print(f"\nFinal window: {list(recent_temps)}")
print(f"maxlen is: {recent_temps.maxlen}")
# Browser history with limit
print("\n=== Browser History (Max 3 pages) ===")
history = deque(maxlen=3)
pages = ["google.com", "github.com", "python.org", "stackoverflow.com", "docs.python.org"]
for page in pages:
history.append(page)
print(f"Visited {page}")
print(f" History: {list(history)}")
# Stock price moving average
print("\n=== Stock Moving Average ===")
window = deque(maxlen=3)
prices = [100, 102, 101, 105, 107, 103, 108, 110]
print("Price\tWindow\t\t\t3-day Avg")
print("-" * 45)
for price in prices:
window.append(price)
if len(window) == window.maxlen:
avg = sum(window) / len(window)
print(f"${price}\t{list(window)}\t\t${avg:.2f}")
else:
print(f"${price}\t{list(window)}\t\t(building window)")
main()
deque(maxlen=N) automatically drops oldest items when full.
maxlen
Bounded deque: `deque(maxlen=5)`. Auto-removes oldest when capacity exceeded.
Reverse a list
Use deque to reverse element order.
reverse_list.py
from collections import deque
def main():
# Reverse a list using deque
numbers = [1, 2, 3, 4, 5]
print("=== Reversing a List ===")
print(f"Original: {numbers}")
# Method 1: Using deque as stack
stack = deque(numbers)
reversed_list = []
while stack:
reversed_list.append(stack.pop())
print(f"Reversed: {reversed_list}")
# Method 2: Using reverse() method
d = deque([1, 2, 3, 4, 5])
d.reverse() # In-place reverse
print(f"Using reverse(): {list(d)}")
# Method 3: Using reversed()
d2 = deque(reversed(deque([1, 2, 3, 4, 5])))
print(f"Using reversed(): {list(d2)}")
# Reverse a string
print("\n=== Reversing a String ===")
original = "Hello World"
stack = deque(original)
reversed_chars = []
while stack:
reversed_chars.append(stack.pop())
reversed_string = "".join(reversed_chars)
print(f'Original: "{original}"')
print(f'Reversed: "{reversed_string}"')
# Simpler Python way (for comparison)
print(f'Pythonic: "{original[::-1]}"')
# Practical: Check for balanced brackets
print("\n=== Balanced Brackets Check ===")
def is_balanced(s):
stack = deque()
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
test_cases = ["()", "()[]{}", "(]", "([)]", "{[()]}", "((())"]
for test in test_cases:
result = "✓ Balanced" if is_balanced(test) else "✗ Not balanced"
print(f'"{test}" → {result}')
main()
Push all items to right, pop from left - they come out reversed.
Exercise: rotate.py
Explore deque.rotate() for circular shifts