Stacks and Queues: Advanced Applications

From Storage to Strategy

When you book a Tatkal ticket on IRCTC and the seats run out, you don't get rejected outright — you get a waitlist number, say WL 14. As confirmed passengers cancel, the person at WL 1 gets confirmed first, then WL 2, and so on, strictly in the order they joined the list. Nobody who joined the waitlist later jumps ahead of someone who joined earlier. That rule — first come, first served — is exactly what a computer scientist means by a queue. Compare this to pressing Ctrl+Z in a document editor: it undoes your most recent change first, not your first change. That's a stack — last in, first out.

You've likely already met stacks and queues as simple containers with a handful of operations. This chapter is about what becomes possible once you actually use them to solve problems a plain array or list struggles with. As a quick refresher before we build on it:

The interesting part is that these two simple rules — "reverse the order" and "preserve the order" — turn out to be the load-bearing idea behind checking whether code compiles, how a calculator evaluates an expression without any notion of "operator precedence," and how a network is searched for the shortest route. We'll build all three from the ground up, then use them together to build something neither structure can do alone.

Application 1: Are the Brackets Balanced? — Stacks in Syntax Checking

Every time you write code, a compiler or interpreter checks whether your brackets, parentheses, and braces are correctly nested before it does anything else. Consider the expression ([a+b]*{c-d}). Is it valid? Your eye can probably tell — but how would you write a rule a machine can follow mechanically, one character at a time, without "seeing" the whole expression at once?

Here's the key insight: every time you see an opening bracket, you don't yet know which closing bracket must match it — you only know it must be matched by something, and that something must appear before any bracket that opened before it gets closed. That "most recently opened, must close first" rule is precisely LIFO. So we push every opening bracket onto a stack, and every time we meet a closing bracket, we check that it matches whatever is currently on top of the stack.

def is_balanced(expr):
    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 not stack

print(is_balanced("([a+b]*{c-d})"))

Let's trace it character by character, watching the stack (shown left-to-right, top on the right):

• ( — push. Stack: [(]
• [ — push. Stack: [(, []
• a, +, b — not brackets, ignored.
• ] — pop the top, which is [. It matches ]'s expected partner. Stack: [(]
• * — ignored.
• { — push. Stack: [(, {]
• c, -, d — ignored.
• } — pop the top, which is {. Matches. Stack: [(]
• ) — pop the top, which is (. Matches. Stack: []

At the end, the stack is empty, so the function returns True. Notice something important about this trace: the stack never holds all three bracket types at once. It reaches a maximum depth of exactly 2 — first [(, [], and later [(, {] — because the ] closes and removes the [ before the { is ever pushed. This is worth checking carefully if you're tracing it yourself, because it's easy to assume the stack "fills up" with every opening bracket seen in the whole expression; it doesn't. It only ever holds brackets that are currently open, and the order of characters in this particular expression means at most two are open simultaneously.

A common misconception: some students believe that checking "balance" just means checking that the count of each bracket type matches — for example, one ( and one ), one [ and one ]. This is false, and it's worth seeing why with a concrete counterexample: ([)]. Count the brackets — one (, one ), one [, one ] — perfectly equal. Yet this expression is not validly nested (the [ opened after ( should close before it, but here ) appears first). Trace it: push (, push [, then we meet ). We pop the stack's top, which is [ — but ) expects (. Mismatch, so the function correctly returns False immediately. Order, not just count, is what a stack is uniquely good at enforcing, because a stack's defining property — LIFO — mirrors exactly how nesting must close: innermost first.

Application 2: Postfix Evaluation — Stacks in Calculators and Compilers

The expressions you normally write, like 3 + 4 * 2, are called infix notation — the operator sits between its operands. To evaluate this correctly, you need to remember rules: multiplication before addition, and parentheses override everything. A computer evaluating your code has to constantly look ahead and behind to apply these rules.

Postfix (also called Reverse Polish Notation) sidesteps all of that by writing operators after their operands: 3 4 2 * + means the same thing as 3 + 4 * 2. There is no ambiguity and no need for precedence rules or parentheses at all — you simply scan left to right, and whenever you hit an operator, it always applies to the two operands that came immediately before it. This is exactly why many real calculators (and the intermediate code inside compilers and interpreters) use postfix internally: it's mechanical to evaluate with a stack.

The algorithm: scan the tokens left to right. If a token is a number, push it. If it's an operator, pop the top two values off the stack — the second-popped is the left operand, the first-popped is the right operand — apply the operator, and push the result back. When you reach the end, exactly one value remains on the stack: the answer.

def evaluate_postfix(expr):
    stack = []
    for token in expr.split():
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                result = a // b
            stack.append(result)
        else:
            stack.append(int(token))
    return stack.pop()

print(evaluate_postfix("6 2 3 + - 3 8 2 / + *"))

Note the choice of // (integer division) rather than / — since every value here is a whole number and we want a whole-number answer, integer division keeps the arithmetic clean. Now trace it, tracking the stack after each token:

• 6 → push. Stack: [6]
• 2 → push. Stack: [6, 2]
• 3 → push. Stack: [6, 2, 3]
• + → pop b=3, pop a=2, push 2+3=5. Stack: [6, 5]
• - → pop b=5, pop a=6, push 6-5=1. Stack: [1]
• 3 → push. Stack: [1, 3]
• 8 → push. Stack: [1, 3, 8]
• 2 → push. Stack: [1, 3, 8, 2]
• / → pop b=2, pop a=8, push 8 // 2 = 4. Stack: [1, 3, 4]
• + → pop b=4, pop a=3, push 3+4=7. Stack: [1, 7]
• * → pop b=7, pop a=1, push 1*7=7. Stack: [7]

The loop ends, and stack.pop() returns 7 — an integer, printed as 7, not 7.0, because we deliberately used //. Note carefully why the order of the pop matters: for subtraction and division, a op b is not the same as b op a. Since a was pushed before b, it sits deeper in the stack and must be popped second — it represents the left-hand operand of the operation in the original expression.

Application 3: Shortest Routes on a Network — Queues (and Stacks) in Graph Traversal

Now for the section that connects stacks and queues to graphs directly. Imagine a small illustrative network of five interchange stations — Rajiv Chowk, New Delhi, Kashmere Gate, Central Secretariat, and Hauz Khas — connected as follows (this is a simplified made-up network for the example, not the real Delhi Metro map):

• Rajiv Chowk — New Delhi
• Rajiv Chowk — Central Secretariat
• New Delhi — Kashmere Gate
• Kashmere Gate — Hauz Khas
• Central Secretariat — Hauz Khas

Starting at Rajiv Chowk, what's the route to Hauz Khas that passes through the fewest stations? A queue answers this question naturally through an algorithm called Breadth-First Search (BFS). The idea: start at Rajiv Chowk, and explore outward one "ring" at a time — first all stations one hop away, then all stations two hops away, and so on. A queue enforces exactly this ordering, because whatever gets discovered first (i.e., is closest) gets processed first.

from collections import deque

def bfs_shortest_path(graph, start, goal):
    visited = {start}
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            break
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

graph = {
    'Rajiv Chowk': ['New Delhi', 'Central Secretariat'],
    'New Delhi': ['Rajiv Chowk', 'Kashmere Gate'],
    'Kashmere Gate': ['New Delhi', 'Hauz Khas'],
    'Central Secretariat': ['Rajiv Chowk', 'Hauz Khas'],
    'Hauz Khas': ['Kashmere Gate', 'Central Secretariat']
}

print(bfs_shortest_path(graph, 'Rajiv Chowk', 'Hauz Khas'))

Trace the queue (front on the left): start with [Rajiv Chowk]. Dequeue Rajiv Chowk, discover New Delhi and Central Secretariat (both one hop away), enqueue both: [New Delhi, Central Secretariat]. Dequeue New Delhi, discover Kashmere Gate: [Central Secretariat, Kashmere Gate]. Dequeue Central Secretariat, discover Hauz Khas: [Kashmere Gate, Hauz Khas]. Dequeue Kashmere Gate — Hauz Khas is already discovered, nothing new happens. Dequeue Hauz Khas — it's the goal, stop. Following the parent pointers back from Hauz Khas gives Rajiv Chowk → Central Secretariat → Hauz Khas, printed as that list — a 2-hop route.

Now here's the crucial contrast. What if, instead of a queue, we used a stack — Depth-First Search (DFS) — exploring as deep as possible down one branch before backtracking?

def dfs_path(graph, start, goal):
    visited = {start}
    parent = {start: None}
    stack = [start]
    while stack:
        node = stack.pop()
        if node == goal:
            break
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                stack.append(neighbor)
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

print(dfs_path(graph, 'Rajiv Chowk', 'Hauz Khas'))

Trace the stack (top on the right): start with [Rajiv Chowk]. Pop Rajiv Chowk. Its neighbours, reversed, are [Central Secretariat, New Delhi], so we push Central Secretariat first, then New Delhi — leaving New Delhi on top: [Central Secretariat, New Delhi]. Pop New Delhi (the top), discover Kashmere Gate, push it: [Central Secretariat, Kashmere Gate]. Pop Kashmere Gate, discover Hauz Khas, push it: [Central Secretariat, Hauz Khas]. Pop Hauz Khas — it's the goal, stop. The parent chain now gives Rajiv Chowk → New Delhi → Kashmere Gate → Hauz Khas — a 3-hop route, even though the true shortest route (2 hops, via Central Secretariat) exists in the graph and was sitting one slot deeper in the stack the whole time.

This is a genuinely important misconception to correct explicitly: many students assume DFS and BFS are just "two ways of visiting the same nodes" and will therefore find equally good paths. They will visit the same set of nodes, but not in the same order, and order is everything here. BFS guarantees the shortest path in an unweighted graph precisely because it exhausts every path of length k before trying any path of length k+1 — so the very first time it reaches a node, it must be by the shortest possible route. DFS commits early to one direction and only backtracks when it hits a dead end; it can easily "find" a node through a long detour before the short route is ever considered, and once a node is marked visited, the algorithm never revisits it to check for a shorter way in. If you need shortest hop-count, the choice of data structure — queue, not stack — is not a style preference; it is the entire correctness argument.

Application 4: Building a Queue Out of Two Stacks

Here's a classic advanced-data-structures problem that shows the two structures aren't rivals — they can build each other. Suppose, for some reason, your programming environment only gives you a stack (push/pop), but your algorithm needs a queue (enqueue/dequeue). Can you simulate a queue using only stacks?

The trick uses two stacks. Keep an in_stack for everything coming in, and an out_stack for everything about to leave. Enqueuing is simple: always push onto in_stack. Dequeuing is the clever part: if out_stack is empty, pour the entire contents of in_stack into out_stack one at a time (via pop-then-push) — this reverses their order once. Since in_stack had the oldest element at the bottom, after reversal that oldest element sits on top of out_stack, ready to be popped — which is exactly the FIFO element we want.

class QueueUsingStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, x):
        self.in_stack.append(x)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

q = QueueUsingStacks()
q.enqueue(5)
q.enqueue(6)
print(q.dequeue())
q.enqueue(7)
print(q.dequeue())
print(q.dequeue())

Trace it: enqueue(5) → in_stack=[5]. enqueue(6) → in_stack=[5, 6]. First dequeue(): out_stack is empty, so pour everything across — pop 6, push to out (out_stack=[6]); pop 5, push to out (out_stack=[6, 5]); in_stack is now empty. Pop from out_stack: returns 5 — correctly the first element ever enqueued. out_stack=[6] remains. enqueue(7) → in_stack=[7] (out_stack untouched). Second dequeue(): out_stack is not empty, so skip the pour — just pop it directly: returns 6. out_stack=[]. Third dequeue(): out_stack empty again, pour in_stack=[7] across → out_stack=[7], pop it: returns 7. The three printed values are 5, 6, 7 — exactly the order they were enqueued, confirming true FIFO behaviour built entirely from two LIFO structures. Notice that every individual element is pushed and popped at most twice across its whole lifetime (once into in_stack, once out of it into out_stack, once out of out_stack) — so even though a single dequeue() call can occasionally look expensive (when it has to pour everything), the average cost per operation, spread over many calls, stays O(1). This is called amortized constant time, an idea you'll meet again in more advanced data structures.

Summary

Stacks and queues are simple to define — LIFO and FIFO — but their real power is in what they let you build. A stack's "undo the most recent thing" property is exactly what's needed to check nested syntax and to evaluate postfix expressions without any precedence rules, because both problems are fundamentally about matching or resolving the most recently opened thing first. A queue's "preserve arrival order" property is exactly what's needed to search a network level by level and guarantee the shortest route, because it processes everything at distance k before anything at distance k+1. And because both are just restricted ways of storing and retrieving data, one can even be built out of the other, as the two-stack queue shows. The single most important habit from this chapter: before reaching for a stack or a queue, ask what order you actually need results back in — "most recent first" or "in the order things arrived" — and let that answer choose the structure, not habit.

Practice: Test Yourself

1. Trace is_balanced("{[a-(b+c)]*2}") by hand, writing the stack's contents after every push and pop. Does it return True or False?

Answer: { push → [{]; [ push → [{, []; a,- ignored; ( push → [{, [, (]; b,+,c ignored; ) pops (, matches → [{, []; ] pops [, matches → [{]; *,2 ignored; } pops {, matches → []. Stack empty at the end, so it returns True. Note this one genuinely does reach depth 3 at one point, unlike the worked example in the chapter — always trace character by character rather than assuming.

2. Evaluate the postfix expression 4 6 2 + * by hand, showing the stack after each token.

Answer: push 4 → [4]; push 6 → [4, 6]; push 2 → [4, 6, 2]; +: pop b=2, pop a=6, push 8 → [4, 8]; *: pop b=8, pop a=4, push 32 → [32]. Result: 32. (This corresponds to the infix expression 4 * (6 + 2).)

3. In your own words, explain why BFS with a queue guarantees the shortest hop-count path in an unweighted graph, while DFS with a stack does not.

Answer: BFS processes nodes strictly in order of discovery, and because it explores every neighbour of every node at distance k before moving to distance k+1, the first time any node is reached, it must have been reached by the shortest possible path — there is no shorter path left unexplored at that point. DFS instead commits to one branch and follows it as deep as possible before backtracking, so it can reach a node for the first time via a long, winding route while a much shorter route through an unvisited neighbour is still sitting further back in the stack, never explored because the node already got marked visited.

4. Trace the QueueUsingStacks class through this sequence: enqueue(10), enqueue(20), enqueue(30), dequeue(), dequeue(), enqueue(40), dequeue(), dequeue(). What four values are returned, in order?

Answer: After the three enqueues, in_stack=[10, 20, 30]. First dequeue(): out_stack empty, pour → out_stack=[30, 20, 10], in_stack empty, pop → returns 10, out_stack=[30, 20]. Second dequeue(): out_stack non-empty, pop directly → returns 20, out_stack=[30]. enqueue(40) → in_stack=[40]. Third dequeue(): out_stack non-empty ([30]), pop → returns 30, out_stack=[]. Fourth dequeue(): out_stack empty, pour in_stack=[40] → out_stack=[40], pop → returns 40. Returned values, in order: 10, 20, 30, 40 — exactly the enqueue order, confirming FIFO.

5. Why does postfix notation never require parentheses, no matter how complex the expression?

Answer: In postfix, every operator always applies to exactly the two values most recently computed or read — its position relative to its operands fully and unambiguously encodes the order of operations. There is never a choice about "which operator binds tighter" because the notation is evaluated strictly left to right with a stack; parentheses in infix notation exist only to override the default precedence rules, and postfix has no default precedence rules to override.