Implementing Stack Data Structure

A stack is an array or linked list restricted so that all insertion and removal happens at a single end (the top) — that restriction is what makes every operation O(1): there is never a need to shift elements or search, because the only mutable position is the last one written.

Recognize the pattern

• Problem mentions "most recent", "undo", "matching pairs", or "nested" structures (brackets, tags, function calls).
• You must reverse the order items were seen, or process the last-arrived item first — LIFO.
• You are tracking a chain of open/pending items where only the innermost one can close next (recursion call stack, backtracking, DFS, expression evaluation).

Brute force → optimal

Brute force: use a dynamic array but always insert/remove at index 0 to visually mimic "newest on top". Every push/pop shifts every remaining element by one slot — O(n) time per operation because the array must stay contiguous from index 0.

Optimal: insert/remove at the tail of the array (or the head of a singly linked list) instead. Nothing after the top element needs to move, so push/pop/peek become O(1).

Complexity, derived from first principles

Array-backed stack: push/pop/peek touch exactly one index (top) — one read or write, no loop → O(1) time. When the backing array fills, we allocate a new array of double the size and copy n elements: that copy costs O(n), but it happens only once every n pushes since the previous resize, so the amortized cost per push is O(n)/n = O(1).

More rigorously (potential method, informally): define potential Φ = 2·size − capacity. A non-resizing push does O(1) real work and increases size by 1, so Φ rises by 2 — 1 unit pays for the work done, 1 unit is banked as credit. By the time the array is full and a resize triggers, size == capacity == n, so Φ = n; that banked credit exactly covers the O(n) cost of copying n elements during the resize, keeping amortized cost (real cost + ΔΦ) at O(1) per push over any sequence. Space is O(n) for n stored elements; the array never shrinks, so up to 2n slots can be allocated at any time even if only n are occupied.

Linked-list-backed stack: push/pop operate on the head pointer only — O(1) time, no amortization needed since no resize/copy ever happens. Space is O(n) for n nodes, plus real per-node overhead: each Node object carries roughly a 16-byte object header (typical 64-bit JVM) plus its field(s). The next reference itself is 4 bytes, not 8, under compressed oops — the JVM's default for heaps under ~32GB — but that per-pointer saving is dwarfed by the header, so realistic overhead is closer to 16–24 bytes per node depending on JVM and padding. Either way, this is more per-element overhead than the array version, which has none once allocated.

Traced worked example (array-backed, capacity starts at 2)

Java: array-based stack

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

    public ArrayStack(int capacity) { data = new Object[capacity]; }

    public void push(T val) {
        // Math.max(1, ...) guards the capacity == 0 case: doubling a
        // zero-length array stays zero-length, which would then write
        // out of bounds below.
        if (top + 1 == data.length) resize(Math.max(1, data.length * 2));
        data[++top] = val;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) throw new RuntimeException("stack underflow");
        T val = (T) data[top];
        data[top--] = null; // drop reference so GC can reclaim it
        return val;
    }

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

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

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

Java: linked-list-based stack

public class LinkedStack<T> {
    private static class Node<T> {
        T val; Node<T> next;
        Node(T val, Node<T> next) { this.val = val; this.next = next; }
    }
    private Node<T> head; // head IS the top
    private int size = 0;

    public void push(T val) { head = new Node<>(val, head); size++; }

    public T pop() {
        if (isEmpty()) throw new RuntimeException("stack underflow");
        T val = head.val;
        head = head.next;
        size--;
        return val;
    }

    public T peek() {
        if (isEmpty()) throw new RuntimeException("stack underflow");
        return head.val;
    }

    public boolean isEmpty() { return head == null; }
}

Pitfalls

• Popping/peeking an empty stack without checking isEmpty() first — array version throws ArrayIndexOutOfBounds or returns stale garbage; linked-list version NPEs on head.val.
• Forgetting to null out popped array slots — for object stacks this is a memory leak: the array still holds a strong reference to a "removed" object.
• Assuming a single push/pop is O(1) worst-case in the array version — the resizing push is O(n); only the amortized cost is O(1), which matters if you're in a hard real-time loop.
• Constructing with capacity 0 — a naive resize(data.length * 2) stays at length 0 forever and the next write goes out of bounds; guard with something like Math.max(1, data.length * 2) (shown above).
• Assuming the array shrinks back down — this implementation (like the one above) only ever grows via doubling; it never shrinks on pop. A stack that peaks at capacity N and drains to empty still holds an N-length array underneath. Some production stacks add an explicit shrink policy (e.g., halve when size drops below capacity/4); don't assume one exists unless you wrote it.

When to use / when not — array vs linked list

Use the array-backed stack when you want cache-friendly contiguous memory and don't need to share nodes; it has zero per-element pointer overhead and better constants despite occasional O(n) resizes. (java.util.ArrayDeque gets similar cache-friendliness, but via a circular buffer with independent head and tail indices that wrap around a fixed-then-grown array — a different mechanism from the single growing top-pointer array taught here, not the same design.) Use the linked-list-backed stack when you need guaranteed O(1) worst case per operation (no resize spikes — relevant for hard real-time systems) or when elements must be large/movable objects that shouldn't be copied during a resize. Avoid a hand-rolled stack altogether for general use in Java — prefer ArrayDeque (faster, no null issues) over the legacy java.util.Stack (synchronized, extends Vector, slower).

Takeaways

• LIFO restriction to one end is exactly what buys O(1) operations — any structure that lets you touch only the "last written" position works.
• Array stacks: O(1) amortized due to doubling (provable via a potential-function argument); linked-list stacks: O(1) worst-case but real per-node overhead (object header + reference, roughly 16–24 bytes under a typical 64-bit JVM with compressed oops).
• Always guard pop/peek with an isEmpty() check — underflow is the most common real bug; also guard construction/resize against a zero or non-doubling capacity.
• In production Java code, reach for ArrayDeque, not java.util.Stack.

Recall: Why is a single push on an array-backed stack described as "amortized O(1)" rather than worst-case O(1), and what specific operation causes the worst case?

Synthesized from standard stack-implementation teaching (array vs. linked-list backing, push/pop/peek/isEmpty) and extended with a potential-method amortized-cost derivation, a corrected traced example, JVM memory-layout accuracy (compressed oops, object headers), a capacity-0 edge-case fix, and array-vs-linked-list trade-off analysis per the study guide's depth bar.