Introduction to Stack

A stack is a linear collection where every operation touches only one end — the top — which is what forces Last-In-First-Out (LIFO) order: an element can only be removed after every element pushed on top of it has already been removed, so history unwinds in exact reverse of how it was built.

Recognize the pattern

• The problem needs to undo or reverse a sequence of actions (undo/redo, backtracking, browser history).
• You must match nested/paired structures — brackets, tags, function calls — where the most recent unmatched thing must resolve first.
• You need the nearest unresolved item relative to current position (next greater element, monotonic stack, expression evaluation).
• Recursion needs to be simulated iteratively (call stack, DFS without recursion).

Brute force vs optimal

Brute force — use an array and always manipulate index 0 (insert/delete at front): each push/pop shifts every remaining element by one slot to keep indices dense, costing O(n) per operation because up to n elements move — Θ(n²) aggregated over n operations.

Optimal (real stack) — restrict all mutation to one fixed end (the top). A dynamic array (ArrayList) or a singly linked list both support insert/delete at one end without touching other elements, giving O(1) per push/pop.

Complexity, derived

Time. Push/pop/peek touch exactly the top pointer/index and, for an array-backed stack, occasionally trigger a resize. Amortized analysis: if capacity doubles on overflow, a sequence of n pushes causes resize copies of sizes 1, 2, 4, … n/2 (the size-n copy only happens on push n+1) — total copies = 1+2+4+…+n/2 = n−1 when n is a power of 2, < n in general. Spread over n pushes that's O(1) amortized per push; pop/peek/isEmpty are strictly O(1) — no scan is ever needed since only the top is examined.

Space. O(n) to hold n elements, plus O(1) extra for the top pointer — no auxiliary structure is proportional to input size.

Traced example

Sequence: push(10), push(20), push(30), peek(), pop(), push(40), pop()

Minimal Java implementation

class ArrayStack<T> {
    private Object[] data = new Object[4];
    private int top = -1; // index of top element, -1 = empty

    public void push(T val) {
        if (top + 1 == data.length) resize();
        data[++top] = val;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) throw new RuntimeException("stack empty");
        T val = (T) data[top];
        data[top--] = null; // avoid memory leak
        return val;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new RuntimeException("stack empty");
        return (T) data[top];
    }

    public boolean isEmpty() { return top == -1; }

    private void resize() {
        Object[] bigger = new Object[data.length * 2];
        System.arraycopy(data, 0, bigger, 0, data.length);
        data = bigger;
    }
}

Pitfalls

• Popping/peeking an empty stack — always check isEmpty() first; unchecked pop is the #1 source of runtime crashes in stack code.
• Forgetting to null out a popped array slot in a garbage-collected language — the array still holds a reference, causing a memory leak in long-lived stacks.
• Fixed-capacity array without resizing silently overflows or throws on isFull() in real workloads where input size isn't known ahead of time.
• Using a stack when order doesn't matter or FIFO is needed — reaching for a stack out of habit instead of a queue.

When to use / when not — trade-offs

Use a stack when the most recently seen unresolved item is what you need next: parsing/matching brackets, undo history, DFS/backtracking, expression evaluation, monotonic-stack problems (next greater element).

Avoid it when you need FIFO order (task scheduling, BFS, print queues) — a Queue is the named alternative there, since it removes from the opposite end it inserts from, preserving arrival order instead of reversing it. Also avoid a plain stack when you need random access to arbitrary elements (use a dynamic array/list) or fast lookup by key (use a hash map) — a stack deliberately gives up both to guarantee O(1) LIFO access.

Takeaways

• LIFO is a direct consequence of restricting all operations to one end — that restriction is what makes O(1) amortized push/pop possible.
• Array-backed stacks need amortized-cost resizing; linked-list-backed stacks avoid resizing but pay per-node allocation overhead.
• Reach for a stack when the next-needed item is always the most recently added unresolved one; reach for a queue when it's the opposite.

Recall: Why is popping from the front of a plain array O(n) while popping from the back is O(1)?

Synthesized for interview-prep study guide; grounded in standard DSA references (CLRS, GeeksforGeeks stack tutorials).