Data Structure1 Practice6 Interview

Stack

GuideCode Labs

Last-in-first-out structure for nested state, expression evaluation, and iterative traversal. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Stack when the prompt's constraints and required operations match this shape: Last-in-first-out structure for nested state, expression evaluation, and iterative traversal.

On this page · Mental Model

Checking your account…

Mental Model

A stack exposes only the most recently pushed unfinished item. That LIFO boundary fits nested state, expression evaluation, and iterative traversal because new work must finish before older suspended work can resume. Items below the top form a compressed history in their exact return order.

Python List as a Stack

Use append to push, pop to remove the top, and stack[-1] to peek. These operations are O(1) amortized at the list’s right end. Avoid insert(0, value) and pop(0), which shift the remaining references. The Python list reference(opens in a new tab) also defines the IndexError raised by an unguarded pop from an empty stack.

Match Nested State

For delimiters, the stack contains exactly the unmatched opening characters in the processed prefix. A closer must match the current top; finding a compatible opener deeper in the stack does not repair incorrectly nested inner state.

Match Nested Delimiters

Reference

def is_balanced(text):
    matching = {')': '(', ']': '[', '}': '{'}
    opening = set(matching.values())
    stack = []
    for character in text:
        if character in opening:
            stack.append(character)
        elif character in matching:
            if not stack or stack.pop() != matching[character]:
                return False
    return not stack

Practice

Implement is_balanced(text) for (), [], and {}. Ignore non-delimiter characters and require every closer to match the latest unmatched opener.

def is_balanced(text):
    opening = set('([{')
    closing = set(')]}')
    return sum(character in opening for character in text) == sum(character in closing for character in text)

Public tests

Verify LIFO delimiter matching

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Reduce with the Stack Top

For adjacent cancellation, keep the fully reduced processed prefix on the stack. The next token creates only one possible new pair—with the top. Cancel that pair or push the token. Since each token is pushed once and popped at most once, cascading reductions still take O(n) total time.

Reduce Adjacent Equal Pairs

Reference

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        else:
            stack.append(token)
    return stack

Practice

Implement reduce_adjacent_pairs(tokens). Cancel the current token with an equal stack top; otherwise push it, then return the reduced sequence.

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        stack.append(token)
    return stack

Public tests

Verify cascading top reductions

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Stack or Recursion

Recursion already supplies a call stack and can be clearest for small, naturally recursive trees. Choose an explicit stack when depth may exceed Python’s recursion limit, frame state is small, or visit order needs direct control. Choose a queue when older work must be processed before newer work.

Common Pitfalls

Peeking or popping before checking emptiness turns a valid unmatched closer into IndexError.
Searching the entire stack ignores nesting and adds unnecessary linear work per input.
Copying a full path into every traversal frame can produce quadratic memory use.
Pushing children in natural order visits them in reverse because the last child is popped first.

Explain It in an Interview

State what one stack item represents and what the complete stack means after each input. Name the events that push and pop. Justify O(n) with aggregate accounting rather than claiming every loop body is identical: every item enters once and leaves at most once. Worst-case auxiliary space is O(n) when nothing resolves early.

Apply One Stack Reduction(opens in a new tab) isolates top interaction. Min Stack(opens in a new tab) adds synchronized metadata so minimum lookup remains O(1) without rescanning values.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Stack itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Stack workflow	`O(n)`	`O(n)`	When each new item can combine only with the most recent unresolved item, a stack represents exactly the pending state. The stack is the fully reduced form of the processed prefix and contains no adjacent equal pair.

Space

O(n) for the demonstrated Stack workflow.

Assumptions

The bound assumes deque or list-end operations; removing from the front of a Python list is O(n).
The bound counts the operations in Apply One Stack Reduction and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Stack invariant before coding and preserve it after every update, traversal step, or recursive return.
When each new item can combine only with the most recent unresolved item, a stack represents exactly the pending state. This remains true after every accepted operation.
The stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. This remains true after every accepted operation.

When To Use Or Avoid Stack

Use It When

Use Stack when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Stack invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def reduce_adjacent_pairs(tokens):
    pass

Use instead

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        else:
            stack.append(token)
    return stack

Where you will hit this: Apply One Stack Reduction(opens in a new tab)

Breaking the central invariant

Pushes the current token even after popping its matching neighbor, so canceled pairs remain represented.

Prevent it: Keep this invariant visible while editing: State the precise Stack invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        stack.append(token)
    return stack

Use instead

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        else:
            stack.append(token)
    return stack

Where you will hit this: Apply One Stack Reduction(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(n).

Avoid

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        stack.append(token)
    return stack

Use instead

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        else:
            stack.append(token)
    return stack

Where you will hit this: Min Stack(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Stack Code Labs

Mental Model

Python List as a Stack

Match Nested State

Public tests

Reduce with the Stack Top

Public tests

Choose Stack or Recursion

Common Pitfalls

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Stack

Use It When

Choose Another Tool When

Common Pitfalls

Leaving the core transition unfinished

Breaking the central invariant

Hiding Python work inside the loop

Related Practice

Related Interview Problems

Reviewed References