Unit 10 — Stacks, Queues & Deques

Slide 1 of 25

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.
- 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

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

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

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

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
```
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

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

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

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
```
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.
- 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.

Unit 10 — Stacks, Queues & Deques

Lesson 1 — LIFO Stacks and FIFO Queues

Lesson 2 — Evaluate Postfix & Monotonic Stack

A Stack-and-Queue Checklist