Stacks and Queues in Python: Balanced Brackets, and deque vs list as a Queue

Fri Aug 14 2026

A stack pops from the same end it pushes to (LIFO); a queue pops from the opposite end it pushes to (FIFO). This post uses a plain Python list as a stack to check bracket balance, collections.deque as a FIFO queue, then times popping from the front of a deque against popping from the front of a list.

The code

import time
from collections import deque


def is_balanced(expr):
    # Stack via a plain list: push on open bracket, pop on close bracket.
    # If the popped bracket doesn't match, or the stack is empty at a
    # close bracket, or non-empty at the end, the expression is unbalanced.
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0


tests = ["(a+b)*[c-d]", "([)]", "{[()]}", "(("]
print("=== Stack: balanced brackets ===")
for expr in tests:
    print(f"{expr!r:>14} -> {is_balanced(expr)}")

print("\n=== Queue: deque as a FIFO ===")
q = deque()
q.append("a")
q.append("b")
q.append("c")
print("after append a, b, c:", list(q))
print("popleft():", q.popleft())
print("queue now:", list(q))

# Time popping from the front: deque.popleft() vs list.pop(0)
n = 20000
print(f"\ntiming {n} front-pops: deque.popleft() vs list.pop(0)")

dq = deque(range(n))
start = time.perf_counter()
while dq:
    dq.popleft()
deque_time = time.perf_counter() - start

lst = list(range(n))
start = time.perf_counter()
while lst:
    lst.pop(0)
list_time = time.perf_counter() - start

print(f"deque.popleft(): {deque_time:.6f}s")
print(f"list.pop(0):     {list_time:.6f}s")

is_balanced pushes each open bracket onto stack and pops on a close bracket, checking the popped value against the expected match. The queue section appends 3 items to a deque then popleft()s one to show FIFO order, then times draining an n = 20000 element deque with popleft() against draining an equal-size list with pop(0).

Running it

Real output:

=== Stack: balanced brackets ===
 '(a+b)*[c-d]' -> True
        '([)]' -> False
      '{[()]}' -> True
          '((' -> False

=== Queue: deque as a FIFO ===
after append a, b, c: ['a', 'b', 'c']
popleft(): a
queue now: ['b', 'c']

timing 20000 front-pops: deque.popleft() vs list.pop(0)
deque.popleft(): 0.000781s
list.pop(0):     0.016423s

The bracket checker got all four cases right against what each expression actually looks like: '(a+b)*[c-d]' and '{[()]}' balanced, '([)]' (crossed brackets) and '((' (unclosed) did not. On the queue, popleft() returned 'a', the first item appended, leaving ['b', 'c'] — FIFO order. In the timing run, draining 20000 items with deque.popleft() took 0.000781s versus 0.016423s for list.pop(0) on the same size — about 21x longer for list.pop(0) in this run.

Takeaway

The run showed a working stack (list) correctly balancing brackets including the crossed-bracket and unclosed-bracket cases, a working FIFO queue (deque) returning items in insertion order, and deque.popleft() measuring about 21x faster than list.pop(0) for 20000 front-removals.