DSA Linear Structures

Stacks

The editor's Undo must reverse the latest edit first. Cmd+Z after typing, pasting, then deleting should undo the delete, then the paste, then the type. A queue would play those actions in arrival order and break the product.

A stack restricts access to one end, the . is the contract: the newest unfinished item is resolved before older work.

Algorithm journey

Newest-first need

Must the latest unfinished item leave before older ones?

State that pop reverses push order on the live sequence.

Representation

Array top, linked head, or library deque at the efficient end.

Throw, optional, or precondition before every pop/peek.

What actually happens

Naive idea: keep edits in an ordinary array and walk from the oldest when undoing. Correct for a history log, wrong for Undo. After edits A, B, C, the user expects C to reverse first.

Better idea: push each committed action onto a stack. Undo is pop plus apply inverse. The invariant holds after every mutation: if the live items from bottom to top are [s₀, …, sₖ], then the unique top is sₖ, and pop returns exactly that value.

The improved design still fails when you pop an empty stack (), push past a fixed capacity without a policy, push/pop at the slow array end (Θ(n) shifts), or confuse an explicit stack with the runtime depth limit.

Invariant (LIFO)

After every successful push or pop, the sequence of live items has a single accessible end (the top). The next pop must return the most recently pushed item that has not yet been popped. Empty means size = 0 and no top exists.

How to choose a stack

1. Is the next item to resolve the newest one? Nesting, undo, DFS frontier, and matching delimiters fit. Oldest-first work needs a queue; priority needs a heap.

2. What does one stack item mean? A character, a command plus inverse, a graph vertex, or a full resume frame. Wrong payload design breaks undo and backtracking even when LIFO is correct.

3. Bound and empty policy? Fixed capacity, dynamic growth ( Θ(1) push), or linked nodes. Decide underflow behavior before coding callers.

Quantitative check

A delimiter scan of length n pushes and pops each token at most once: Θ(n) stack operations. A monotonic next-greater pass does the same: each of n indices enters and leaves at most once, so nested while-loops still total Θ(n). Recursive DFS on a path of length n needs Θ(n) call-stack frames; an explicit stack of the same depth usually lives on the heap and can be capped.

Contract first, representation second

The abstract stack is not “an array drawn vertically.” It is the behavior below. Code using the stack should not depend on capacity, node addresses, or how elements are stored. If the logical contents from bottom to top are S = [s₀, …, sₖ], the operations transform that sequence predictably.

Push

push(x) changes S to S followed by x; x becomes the unique top.

Pop

On non-empty S, pop returns sₖ and leaves the prefix through sₖ₋₁.

Peek

On non-empty S, peek returns sₖ while S and size remain unchanged.

Size agreement

size equals the number of logical items; empty means size = 0.

Order consequence: pushing A, B, C and then popping until empty returns C, B, A. Iterating an underlying array from index 0 may show the opposite direction, so always state whether a display is bottom-to-top or top-to-bottom.

Interactive: operate on a concrete stack

This original visualization lets you push, pop, and peek. Its six-item cap deliberately demonstrates that overflow belongs to a bounded representation, not to the abstract LIFO contract.

Stack Operations

ℹ️ Ready to stack items!

LIFO: Last In, First Out

Book A

Book B

Book C

Stack Bottom

Underflow and overflow are API decisions

Underflow: no top exists

pop or peek on an empty stack has no valid result. An API may throw, return an optional result, offer a separate tryPop, or require a non-empty precondition. Returning a normal sentinel such as null is ambiguous if that value may also be stored.

Overflow: storage cannot accept another item

A fixed-capacity stack can detect size == capacity before writing. A dynamic stack usually grows, so its practical failures are allocation failure or a configured limit. A call-stack overflowis different: recursion exhausted the runtime's finite frame budget.

Examples of empty-stack behavior in common stack APIs
API	Remove top	Observe top	Empty behavior
Python list	`pop()`	`stack[-1]`	Both raise `IndexError`
Java Deque	`pop()` / `poll()`	`element()` / `peek()`	First form throws; second returns null
Explicit safe API	`tryPop()`	`tryPeek()`	Returns option/result or success flag

Java's ArrayDeque rejects null elements, which keeps null-returning methods unambiguous. Itspop() is equivalent to removing from the deque's front: the chosen stack top.

Implementation choices and their real costs

Fixed-array, dynamic-array, and linked stack trade-offs
Representation	Strength	Cost / risk	Good fit
Fixed array	Predictable memory, no resizing, excellent locality	Must choose capacity; push can report overflow	Embedded, real-time, or bounded protocols
Dynamic array	Compact, cache-friendly, amortized constant-time push	Occasional Θ(n) copy and spare capacity	Default general-purpose explicit stack
Singly linked list	No bulk resize; worst-case constant pointer rewiring	Allocation, pointer overhead, and weaker locality per item	Stable nodes or segmented/custom allocation needs

Terminal

# Fixed-capacity array; top is the next free slot
push(x):
    if top == capacity: error OVERFLOW
    data[top] = x
    top += 1
 
pop():
    if top == 0: error UNDERFLOW
    top -= 1
    x = data[top]
    clear data[top]       # release reference if needed
    return x
 
peek():
    if top == 0: error UNDERFLOW
    return data[top - 1]

Array invariant

0 ≤ top ≤ capacity; live items occupy exactly data[0:top], and data[top − 1] is the logical top when non-empty.

Linked invariant

head is the top; following next visits items from newest to oldest, and exactly size nodes are reachable.

Mutation discipline

Check the precondition before changing state. Update storage and size together so an exception cannot expose a half-written stack.

Why dynamic-array push is amortized Θ(1)

Suppose capacity doubles when full. Most pushes write one slot. A growth push allocates a larger buffer and copies the existing items, so that single push is Θ(n). Across n pushes, however, copied counts form a geometric series:

1 + 2 + 4 + … + largest copied capacity < 2n

The n direct writes plus fewer than 2n copies total Θ(n), so the average charge per push is Θ(1). This is an amortized guarantee over a sequence, not a claim that every push has constant latency.

Ordinary push

Θ(1)

One bounds check and one write.

Growth push

Θ(n) worst

Allocate and copy current items.

n pushes

Θ(n) total

With geometric, not +1: growth.

Shrinking needs hysteresis: shrinking as soon as size falls one below capacity can make alternating push/pop operations repeatedly copy the array. Shrink at a much lower load threshold, such as one quarter full, or do not shrink automatically.

Language idioms: keep the top at the efficient end

Python list

python

stack = []

stack.append("A")      # push at the right end
stack.append("B")
top = stack[-1]        # peek: "B"
popped = stack.pop()   # pop:  "B"
remaining_top = stack[-1] if stack else None

print(top, popped, remaining_top)  # B B A

# Avoid insert(0, x) and pop(0): shifting makes them Θ(n).

Java Deque

java

import java.util.ArrayDeque;
import java.util.Deque;

final class StackIdioms {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("A");
        stack.push("B");

        String top = stack.peek();          // "B"; null if empty
        String popped = stack.pop();        // "B"; throws if empty
        String remainingTop = stack.peek(); // "A"

        System.out.println(top + " " + popped + " " + remainingTop); // B B A
    }
}

// Prefer Deque/ArrayDeque for new LIFO code.
// java.util.Stack is a legacy synchronized Vector subclass.

Interactive: watch algorithms maintain a stack invariant

Switch among delimiter matching, postfix evaluation, and next-greater-element processing. Each is linear because it performs a bounded amount of work per token: or, for the monotonic case, pushes and pops each index at most once.

Execution laboratory

Balanced delimiter parser

{[()()]}

Step 1 of 9

token: —

Current action

Initialize an empty stack

No input has been consumed, so there are no unmatched opening delimiters.

Loop invariant

The stack contains exactly the unmatched openers in the consumed prefix.

Output state

valid so far

Rule: Push openers. A closer must match the opener at the top.

Stack state

unmatched openers

size = 0

TOP ↓

empty stack

BOTTOM

Keyboard: focus this demo, then use ← →, Home, or End.

Application templates

Delimiter parsing

Stack stores: Unmatched opening delimiters
Invariant: The stack is the open nesting path for the consumed prefix.
Common failure: Closer with no opener, mismatched top, or leftover opener at end.

Expression evaluation

Stack stores: Operands, partial values, or pending operators
Invariant: Every value represents one complete subexpression.
Common failure: Too few operands, extra values, or reversed left/right operands.

Iterative DFS

Stack stores: Vertices or frames whose work remains
Invariant: Every reachable but unfinished branch is represented.
Common failure: Marking visited too late can push a vertex many times.

Backtracking

Stack stores: Choices plus enough state to undo or resume
Invariant: The stack describes the current root-to-state path.
Common failure: Forgetting to restore mutable state when abandoning a choice.

Monotonic stack

Stack stores: Unresolved indices in a value order
Invariant: Values remain increasing or decreasing after each input.
Common failure: Using < instead of ≤ (or vice versa) changes duplicate handling.

Undo / redo

Stack stores: Commands, inverse commands, or snapshots
Invariant: Undo top is the latest committed action not yet undone.
Common failure: A new edit after undo normally clears the redo stack.

Delimiters

Python

python

def is_balanced(text):
    expected = {')': '(', ']': '[', '}': '{'}
    openers = set(expected.values())
    stack = []

    for token in text:
        if token in openers:
            stack.append(token)
        elif token in expected:
            if not stack or stack.pop() != expected[token]:
                return False

    return not stack  # no unmatched opener remains

Java

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
import java.util.Set;

final class Delimiters {
    static boolean isBalanced(String text) {
        Map<Character, Character> expected = Map.of(
            ')', '(', ']', '[', '}', '{'
        );
        Set<Character> openers = Set.of('(', '[', '{');
        Deque<Character> stack = new ArrayDeque<>();

        for (char token : text.toCharArray()) {
            if (openers.contains(token)) {
                stack.push(token);
            } else if (expected.containsKey(token)) {
                if (stack.isEmpty() || !stack.pop().equals(expected.get(token))) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Iterative DFS

Python

python

def dfs(graph, start):
    stack = [start]
    seen = {start}                 # mark when scheduled

    while stack:
        node = stack.pop()
        visit(node)

        # Reverse if graph[node] is in the desired visit order:
        for neighbor in reversed(graph[node]):
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)

Java

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;

final class DepthFirst {
    static <T> void dfs(Map<T, List<T>> graph, T start, Consumer<T> visit) {
        Deque<T> stack = new ArrayDeque<>();
        Set<T> seen = new HashSet<>();
        stack.push(start);
        seen.add(start);                 // mark when scheduled

        while (!stack.isEmpty()) {
            T node = stack.pop();
            visit.accept(node);

            List<T> neighbors = graph.getOrDefault(node, List.of());
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                T neighbor = neighbors.get(i);
                if (seen.add(neighbor)) stack.push(neighbor);
            }
        }
    }
}

Monotonic

Python

python

def next_greater(values):
    answer = [-1] * len(values)
    stack = []                     # unresolved indices

    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            answer[stack.pop()] = value
        stack.append(i)

    return answer

# Each index is pushed once and popped at most once: Θ(n).

Java

java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

final class NextGreater {
    static int[] nextGreater(int[] values) {
        int[] answer = new int[values.length];
        Arrays.fill(answer, -1);
        Deque<Integer> stack = new ArrayDeque<>(); // unresolved indices

        for (int i = 0; i < values.length; i++) {
            while (!stack.isEmpty() && values[stack.peek()] < values[i]) {
                answer[stack.pop()] = values[i];
            }
            stack.push(i);
        }
        return answer;
    }
}

The call stack versus an explicit stack

Recursive code uses a stack managed by the language runtime. Each active call has a frame containing control information such as a return location plus parameters and locals. An explicit stack stores only the state your algorithm chooses. Both can express depth-first work, but they have different operational trade-offs.

Runtime call stack

Often gives the clearest code for naturally recursive structures.
Depth is limited; a long chain can raise a recursion/stack-overflow error.
Frame layout and scheduling are controlled by the runtime.
Do not assume tail-call optimization in Python or Java.

Explicit stack object

Usually grows in heap memory and can handle deeper traversals.
Can be paused, serialized, inspected, or given a deliberate memory cap.
Must store a frame, not just a node, when work resumes in multiple phases.
Push neighbors in reverse to reproduce a recursive left-to-right DFS order.

Replacing recursion mechanically with “push each child” is not always equivalent. Tree postorder, parser descent, and backtracking may require frames like (node, nextChildIndex, phase) so execution can resume after a child.

Operation complexity, with assumptions exposed

Stack operation contracts and costs by representation
Operation	Contract	Dynamic array	Linked head
push(x)	Place x at the top; size increases by one.	Amortized Θ(1); worst Θ(n) when growth copies elements	Θ(1) with head as top, under the usual allocation model
pop()	Remove and return the current top; underflow if empty.	Θ(1), excluding an optional shrink policy	Θ(1)
peek() / top()	Return the top without changing the stack.	Θ(1)	Θ(1)
isEmpty() / size()	Observe state without changing logical order.	Θ(1)	Θ(1) when size is stored; isEmpty is always Θ(1)
search(x)	Not a core stack operation; it exposes the representation.	O(n), worst Θ(n)	O(n), worst Θ(n)

Live storage

Θ(n)

For n stored items in either representation.

DFS peak

O(V) worst

Explicit worklist; recursive frames instead use O(depth).

Monotonic total

Θ(n)

Each of n indices enters and leaves at most once.

These bounds use the usual RAM model. They ignore allocator pauses, cache effects, synchronization, element-copy cost, and destructors. A pushed object is normally stored by reference in Python/Java; copying a large value type in another language may change constants or costs.

Correctness pattern: define what the stack means

Initialization

Show the empty stack correctly represents the unprocessed problem state.

Maintenance

For each token or choice, prove pushes and pops restore the representation invariant.

Termination

Relate the final empty/non-empty or one-value state to the required answer.

Why monotonic stacks are linear despite a while-loop

Do not multiply the outer n iterations by a possible n pops. Charge each pop to the unique earlier push of that index. Since an index cannot be popped twice, there are at most n pushes and n pops across the whole run. This aggregate argument proves Θ(n) total work for the stack operations.

Concurrency and reentrancy

Shared between threads

Most general-purpose stack collections are not thread-safe. Even when individual methods are synchronized,if (!empty()) pop() is a check-then-act race unless the pair is protected by one lock. Choose an atomic tryPop, external locking, or a purpose-built concurrent stack. Producer/consumer workflows usually need a blocking queue rather than LIFO semantics.

Callbacks and recursive re-entry

A module-global scratch stack can be corrupted when a callback or recursive invocation re-enters the same routine. Prefer a stack local to each operation, pass ownership explicitly, and avoid invoking arbitrary user code while representation invariants are temporarily broken.

Advanced note: lock-free linked stacks must address safe memory reclamation and the ABA problem; atomic compare-and-swap alone is not a complete production design.

Pitfalls that survive easy examples

Using the slow array end

For Python lists and dynamic arrays, push/pop at the end, not index 0, which shifts Θ(n) items.

Checking after popping

Establish the non-empty precondition first, or use a single atomic try-pop operation.

Reversing binary operands

In postfix evaluation, first pop is right; second pop is left. This matters for −, ÷, and exponentiation.

Losing desired DFS order

Because LIFO reverses insertion order, push neighbors in reverse when order is observable.

Wrong duplicate inequality

A monotonic stack for strictly greater uses a different pop condition from greater-or-equal.

Calling every recursive algorithm O(n) space

Peak call-stack space is active depth, which may be O(log n), O(n), or another bound.

Retaining stale references

Clear vacated array slots in manual implementations so garbage collection can reclaim popped objects.

Assuming synchronized means atomic workflow

Multiple individually safe calls can still race; protect the entire state transition.

Simple rule of thumb

Choose a stack when the next item to resolve is always the most recently discovered unfinished item. Use a dynamic-array stack by default; choose a fixed array when the bound and latency matter, or a linked/custom representation when its allocation and node-stability trade-offs are deliberate. If you need oldest-first service, priorities, random access, or removal from both ends, use a queue, heap, array, or deque instead.

Ask 1

What exactly does one stack item represent?

Ask 2

What invariant does push/pop preserve?

Ask 3

What is the maximum live depth and empty policy?

Exercises

Push A, B, C then pop twice. What is the top, and what sequence of pops empties the stack? State the invariant after each step.
n = 10⁵ tokens of balanced parentheses. Argue why a stack solution is Θ(n) time and O(n) space in the worst case. Give an input that forces Θ(n) depth.
A Python list used as a stack does insert(0, x) and pop(0). For n pushes and n pops, what is the total cost, and which end restores amortized Θ(1) updates?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): stacks and the LIFO abstract data type.
Knuth, The Art of Computer Programming, Vol. 1: sequential and linked stack representations.
Java Deque / ArrayDeque documentation (prefer over legacy Stack).

Takeaway

A stack is a LIFO contract with one accessible end. Once you define what the top means for your problem and how empty cases fail, delimiter matching, undo, DFS, and monotonic scans become the same invariant with different payloads.