A stack retrieves the most recently added item; a queue retrieves the earliest waiting item. Choosing between them depends on what work must happen next. Interview questions become easier when you connect the access order to the problem instead of reciting the abbreviations LIFO and FIFO.

Why does bracket matching need a stack?

The next closing bracket must match the most recent unmatched opening bracket. Earlier opening brackets are still waiting underneath it. A stack directly represents that unfinished nesting.

from collections import deque

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

assert balanced("a[(b)]")
assert balanced("")
assert not balanced("([)]")
assert not balanced("]")
assert not balanced("((")

queue = deque(["first", "second"])
queue.append("third")
assert queue.popleft() == "first"
assert list(queue) == ["second", "third"]

This function intentionally ignores non-bracket characters. That policy belongs to the exercise, not every parsing task. A real language parser would need rules for quoted text, escapes and other syntax.

What does the stack contain after each character?

It contains exactly the opening brackets not yet matched, in their nesting order. When a closing bracket appears, the last item is the only opening bracket that can validly match it. A different top item proves a mismatch.

The final empty check matters. A string can avoid every closing-bracket error and still have unmatched openings left. For example, two opening parentheses are not a balanced result.

When would a queue be the correct model?

Use a queue when work should be handled in the order it was discovered or received. A basic breadth-first traversal uses that property to process one discovery layer before later layers. A queue of pending requests can use the same access order without making any graph claim.

In Python, deque supports the end operations used by this example. Repeatedly removing the first element of a normal list requires shifting later elements. Choosing a list because it is familiar can therefore create the wrong cost for queue behavior.

What should a complexity answer include?

The bracket checker visits each character once. Its stack can grow with the nesting depth, which can be as large as the input length. It is not constant-space merely because the code has only one list variable.

Also identify what the complexity does not include. This in-memory example receives an existing string. Reading a remote file or tokenizing a language would add work outside the shown checker.

How can empty-state errors be avoided?

Check whether the stack has an item before removing one in a case where empty input is possible. Similarly, a queue consumer needs an explicit rule for no waiting work. Returning a sentinel, raising an exception and waiting for future work are different API contracts.

Do not silently turn an invalid operation into a successful result merely to avoid an exception. Decide what empty means for the task and test that decision.

Practice variations

  • Trace the stack for a correctly nested expression.
  • Explain why counting opening and closing brackets alone is insufficient.
  • Change the non-bracket policy from ignore to reject.
  • Describe why a queue would not match nested brackets correctly.

A strong answer states the unfinished-work model. Once that model is clear, the container choice and the final checks follow naturally.

References and next practice

ocw.mit.edu — algorithms

Browse interview topics · Practise a question in Interview Challenge · How to Answer Technical Interview Questions Out Loud