Unit 10 — Stacks, Queues & Deques

Is the bracket string ([{}]) balanced, and why does changing only its final bracket make ([{}]] fail? The answer depends on which opening bracket is still waiting most recently. A STACK remembers the NEWEST waiting item, a QUEUE the OLDEST; Python's deque does both. We build it as a short ladder of executable demos (each with a Notice), then a full stdin solver.

You will learn

Tell a stack (last in, first out) from a queue (first in, first out).
Use a deque as a stack with appendleft, popleft and stack[0], or as a queue with append and popleft.
Check that brackets are balanced with a stack.
Evaluate postfix expressions and find the next greater value with a monotonic stack.

Lesson 1 — LIFO Stacks and FIFO Queues

A STACK is last-in-first-out. With a deque, push with appendleft, peek with stack[0], pop with popleft.

from collections import deque
stack = deque()
stack.appendleft("A")
stack.appendleft("B")
print("top", stack[0])
stack.popleft()
print("top", stack[0])

Output

top B
top A

Notice

The newest item (B) is on top; popleft removes it, exposing A.

A QUEUE is first-in-first-out: enqueue with append, dequeue with popleft, test empty with len(q) == 0.

from collections import deque
queue = deque()
queue.append("Ava")
queue.append("Bo")
print("serve", queue.popleft())
print("empty?", len(queue) == 0)

Output

serve Ava
empty? False

Notice

The OLDEST item (Ava) is served first — the opposite end from a stack.

Match brackets with a stack: push each opener; on a closer, the top must be its matching opener.

from collections import deque
stack = deque()
matched = True
for ch in "([])":
    if ch in "([{":
        stack.appendleft(ch)
    else:
        expected = "("
        if ch == "]":
            expected = "["
        elif ch == "}":
            expected = "{"
        if len(stack) == 0 or stack[0] != expected:
            matched = False
        else:
            stack.popleft()
print("balanced:", matched and len(stack) == 0)

Output

balanced: True

Notice

Each closer checks the MOST RECENT opener; a full match leaves the stack empty.

Put it together: the program reads one bracket string from stdin and prints YES if it is balanced, else NO.

Try it yourself

from collections import deque
import sys

data = sys.stdin.read()
expression = data.strip()
stack = deque()
answer = "YES"
for character in expression:
    if character in "([{":
        stack.appendleft(character)
    else:
        if len(stack) == 0:
            answer = "NO"
        else:
            expected = "("
            if character == "]":
                expected = "["
            elif character == "}":
                expected = "{"
            if stack[0] != expected:
                answer = "NO"
            else:
                stack.popleft()
if len(stack) > 0:
    answer = "NO"
print(answer)

Run the full solver from this unit folder:

python assets/l1.py < assets/l1/1.in

Notice

Push openers; on a closer the top (stack[0]) must match, else the answer is NO; a clean run ends with an empty stack.

Complexity: O(n) — one pass, each bracket pushed/popped once.

Lesson 2 — Evaluate Postfix & Monotonic Stack

In postfix, an operator acts on the two most recent values: pop two, combine, push the result.

from collections import deque
stack = deque()
stack.appendleft(8)
stack.appendleft(3)
right = stack.popleft()
left = stack.popleft()
stack.appendleft(left - right)
print(stack[0])

Output

Notice

For 8 3 -, pop 3 (right) then 8 (left) and push 8 - 3 = 5 — order matters.

from collections import deque
tokens = "8 3 - 2 *".split()
stack = deque()
for token in tokens:
    if token in "+-*" and len(token) == 1:
        right = stack.popleft()
        left = stack.popleft()
        if token == "+":
            stack.appendleft(left + right)
        elif token == "-":
            stack.appendleft(left - right)
        else:
            stack.appendleft(left * right)
    else:
        stack.appendleft(int(token))
print(stack[0])

Output

Notice

Processing 8 3 - 2 * leaves 10 on the stack — the whole expression in one pass.

A different stack pattern: the MONOTONIC stack finds, for each item, the next greater value to its right.

from collections import deque
numbers = [4, 2, 7, 1]
answer = []
for n in numbers:
    answer.append(-1)
stack = deque()
i = 0
while i < len(numbers):
    while len(stack) > 0 and numbers[stack[0]] < numbers[i]:
        waiting = stack[0]
        stack.popleft()
        answer[waiting] = numbers[i]
    stack.appendleft(i)
    i = i + 1
print(answer)

Output

[7, 7, -1, -1]

Notice (pivot — a second stack use): the stack holds indices still waiting for a greater value; each is resolved once, so the pass is O(n).

Put it together: the postfix program reads a whitespace-separated expression from stdin and prints its value.

Try it yourself

from collections import deque
import sys

data = sys.stdin.read()
tokens = data.split()
stack = deque()
for token in tokens:
    if token in "+-*" and len(token) == 1:
        right = stack.popleft()
        left = stack.popleft()
        if token == "+":
            value = left + right
        elif token == "-":
            value = left - right
        else:
            value = left * right
        stack.appendleft(value)
    else:
        stack.appendleft(int(token))
print(str(stack[0]))

Run the full solver from this unit folder:

python assets/l2.py < assets/l2/1.in

Notice

Push numbers; on +/-/* pop two (right then left), combine, push the result; the final stack top is the answer.

Complexity: O(n) — one pass over the tokens.

A Stack-and-Queue Checklist

(1) Newest-waiting → stack (appendleft/popleft/stack[0]); (2) oldest-waiting → queue (append/popleft); (3) always check len == 0 before peeking/popping; (4) for postfix, pop RIGHT before LEFT.

Recap

A stack serves the NEWEST item first; a queue serves the OLDEST.
Check len(stack) == 0 before peeking at stack[0] or calling popleft.
Brackets balance when every closer matches the most recent opener and the stack ends empty.
In postfix, take the right value off first, then the left, combine them and push the result.
A monotonic stack holds indices still waiting for a greater value, so each is settled once in O(n).

You can now choose a stack or a queue and use it to solve a contest problem.