Data Structures & Algorithms / Contracts, sequences, and search / Lesson 4

Stacks, queues, and ordering policies

Choose removal order from the task and prove that the container preserves the unfinished work it represents.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Order is the abstraction
Match nested structure with a stack invariant
Use a queue to preserve arrival order

Order is the abstraction

A stack removes the most recently added unfinished item first, while a queue removes the oldest item first. Their usefulness comes from those policies, not from a particular class name. Nested delimiter matching needs the latest unmatched opener, while fair turn-taking needs earlier arrivals before requeued work. Define what each stored item represents and when it enters or leaves. A correct container with the wrong policy still gives the wrong algorithm. These examples operate on tiny local strings and job records; they do not run system schedulers, services, or load experiments.

Match nested structure with a stack invariant

For delimiter checking, the stack contains exactly the unmatched opening delimiters in encounter order. A closing delimiter must match the top, because nested structure closes the innermost still-open group first. The first program ignores ordinary non-delimiter characters and rejects an unexpected or mismatched closing symbol. At the end, a nonempty stack means some opener never closed. This is a syntactic toy contract, not a full programming-language parser: it does not understand quoted strings, escapes, comments, or a language grammar. Those features require a richer tokenization and parsing design.

python Self-contained Python3 algorithm example using synthetic local data.

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

print(balanced("a([{}])"))
print(balanced("([)]"))
print(balanced(""))

Expected output

True
False
True

A list append/pop at the same end implements the stack policy. The empty string has no unmatched delimiters.

Use a queue to preserve arrival order

The second program simulates round-robin work with one unit per turn. Removing from the front and appending unfinished work at the back ensures a job already waiting gets its next turn first. A deque supports efficient end operations and avoids repeatedly shifting a Python list with pop(0). The simulation assumes nonnegative integer work and a closed finite input; a real scheduler needs arrival timing, priorities, cancellation, and resource rules. The trace illustrates order only and is not a recommendation for operating-system scheduling or a claim of universal fairness under arbitrary arrivals.

python Self-contained Python3 algorithm example using synthetic local data.

from collections import deque

def turns(jobs):
    queue = deque()
    for name, remaining in jobs:
        if not isinstance(remaining, int) or remaining < 0:
            raise ValueError("Work must be a nonnegative integer")
        if remaining:
            queue.append((name, remaining))
    trace = []
    while queue:
        name, remaining = queue.popleft()
        trace.append(name)
        remaining -= 1
        if remaining:
            queue.append((name, remaining))
    return trace

print(turns([("A", 2), ("B", 1)]))
print(turns([("Idle", 0)]))

Expected output

['A', 'B', 'A']
[]

A runs once, B runs while A waits, then A finishes. Zero-work jobs need no queue entry.

Include maximum unfinished work in space analysis

Delimiter checking can require linear stack space for a string containing only opening symbols. The queue simulation can hold at most one entry per unfinished input job under this contract, while the returned trace has one item per work unit. That output can be much larger than the number of jobs, so analyze total work W separately from job count n. The simulation is O(n+W) under bounded-cost operations, and storing the whole trace costs O(W) output space. A streaming consumer could avoid retaining that trace if the result contract permitted it.

Handle empty removal and bounded capacity deliberately

Popping an empty stack or queue should be prevented by the algorithm’s invariant or exposed as a documented failure. Do not catch every exception and silently pretend an item existed. A bounded deque with maxlen can discard entries when new items arrive, which may be useful for a recent-history buffer but incorrect for an unfinished-work queue. Capacity policy is part of correctness. If every queued job must eventually be processed, silent eviction violates the contract even though the container behaves exactly as its API specifies.

Verify order and conservation together

For a stack matcher, test unmatched closers, unmatched openers, wrong nesting, correct nesting, empty text, and ignored ordinary characters. For the queue, verify the trace count for each job equals its requested work and that initial waiting jobs precede a requeued first job. Include zero work and invalid negative work. Conservation checks catch lost or duplicated jobs that a plausible trace prefix might miss. Tests remain deterministic and small; no concurrent threads, real schedulers, or benchmark load are needed to establish these local ordering rules.

Common errors and fixes

A queue uses pop() and reverses waiting order

Why it happens: Removal followed stack policy instead of FIFO.
How to fix it: Remove from the front with an appropriate queue implementation.
Prevent it next time: Test three distinct initial arrivals.

Wrong nesting passes a delimiter check

Why it happens: The algorithm counted symbols but ignored their order.
How to fix it: Match each closer against the stack top.
Prevent it next time: Include ([)] as a counterexample.

A bounded queue silently loses unfinished jobs

Why it happens: History-buffer eviction was used for required work.
How to fix it: Choose explicit capacity rejection or an unbounded synthetic queue.
Prevent it next time: Verify per-job conservation counts.

Check your understanding

1. Why is equal count of opening and closing parentheses insufficient?

Show worked solution

The string )( has equal counts but closes before any opener exists. With several delimiter types, ([)] also has matching totals but wrong nesting. The stack invariant preserves both availability and innermost order, which counting alone loses.

2. What is the total trace length for work counts 2,0,3?