Stacks and Queues with list and deque

LIFO and FIFO

A stack is last in, first out (LIFO): push and pop at the same end. A Python list is an excellent stack using append and pop(), both O(1). Stacks power undo history, expression evaluation, matching brackets, backtracking and depth-first search, and the call stack itself. A queue is first in, first out (FIFO): add at the back, remove from the front. A list is a poor queue because pop(0) is O(n). Use collections.deque (double-ended queue), implemented as a doubly linked list of fixed-size blocks: append, appendleft, pop and popleft are all O(1), and deque(maxlen=n) keeps only the last n items, perfect for sliding windows and recent-history buffers. Indexing into the middle of a deque is O(n). For communication between threads, use queue.Queue (FIFO), LifoQueue or PriorityQueue, which add locking and blocking get/put with timeouts; for asyncio, use asyncio.Queue. Queues power breadth-first search, task scheduling, buffering and rate limiting.

Stack versus queue

A stack adds and removes at the top; a queue adds at the back and removes from the front.

Bracket matching with a stack and a recent-items queue

list as a stack, deque as a queue and a bounded buffer.

from collections import deque

def balanced(expression: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expression:
        if ch in "([{":
            stack.append(ch)                  # push
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:   # pop and compare
                return False
    return not stack

print(balanced("{[a + b] * (c - d)}"))        # True
print(balanced("(a + b]"))                    # False

support_queue = deque()
for ticket in ["T1", "T2", "T3"]:
    support_queue.append(ticket)              # enqueue at the back
print(support_queue.popleft())                # T1: first in, first out
support_queue.appendleft("URGENT")            # jump the queue
print(list(support_queue))                    # ['URGENT', 'T2', 'T3']

recent_views = deque(maxlen=3)                # keeps only the last 3
for product in ["pen", "ink", "pad", "stapler"]:
    recent_views.append(product)
print(list(recent_views))                     # ['ink', 'pad', 'stapler']

Use queue.Queue between threads

A deque's individual append and popleft are thread-safe in CPython, but coordinating producers and consumers (waiting for items, signalling completion) is much easier with queue.Queue, which provides blocking get, task_done and join.

Quick check: Which structure gives O(1) removal from the front of a sequence?

• list.pop(0)
• tuple slicing
• collections.deque.popleft()
• str.lstrip