Stacks

A stack is an abstract data type that stores a sequence of elements and supports insertion and removal at only one end, called the top. The two defining operations are `push(x)`, which adds `x` to the top, and `pop()`, which removes and returns the top element. This access pattern is called LIFO: Last In, First Out. A helper operation `peek()` (or `top()`) returns the top element without removing it, and `isEmpty()` reports whether the stack has any elements. The key conceptual move is separating the interface (what operations exist, and what they mean) from the implementation (how the elements are actually stored in memory). CLRS-style abstract data types are defined by their behavioral contract, not by a specific data layout. A stack can be built on top of a dynamic array (as in Arrays and Dynamic Arrays) or on top of a singly linked list; both satisfy the same LIFO contract, but they differ in memory locality, worst-case single-operation cost, and how they behave under resizing. Central to every correct implementation is an invariant: a property that must hold true before and after every operation. For a stack, the invariant is that the top pointer (an index into an array, or a reference to a linked-list head) always refers to exactly the most recently pushed element that has not yet been popped — and if the stack is empty, top signals "no such element" (an index of $-1$, or a null reference). Every `push` and `pop` must update this pointer in lockstep with adding or removing the element, or the structure silently corrupts: a stale top, a dangling reference, or a phantom empty check.

Array-based stack. Maintain a backing array `A` of capacity `cap` and an integer `top` denoting the index of the last used slot (`top = -1` means empty). `push` writes to `A[top+1]` and increments `top`; `pop` reads `A[top]` and decrements `top`. When `top+1` would exceed `cap`, the array is reallocated to twice its size (a dynamic array resize), and all existing elements are copied over — this is the same doubling trick used in dynamic arrays generally.

Linked-list-based stack. Maintain a pointer `head` to a singly linked list, where `head` represents the top of the stack. `push` allocates a new node whose `next` field points to the old `head`, then reassigns `head` to the new node. `pop` reads `head.value`, reassigns `head` to `head.next`, and (in languages without garbage collection) frees the old head node. No resizing ever occurs, because nodes are allocated individually. ```pseudocode // ---------- Array-based stack ---------- structure ArrayStack: A[0 .. cap-1] // backing array cap // current capacity top // index of top element; -1 if empty ArrayStack.init(initialCap = 4): cap <- initialCap A <- new array of size cap top <- -1 ArrayStack.isEmpty(): return top == -1 ArrayStack.push(x): if top + 1 == cap: // would overflow: grow cap <- 2 * cap A' <- new array of size cap for i from 0 to top: A'[i] <- A[i] A <- A' top <- top + 1 A[top] <- x ArrayStack.pop(): if isEmpty(): error "pop from empty stack" x <- A[top] A[top] <- undefined // optional: drop the reference top <- top - 1 return x ArrayStack.peek(): if isEmpty(): error "peek on empty stack" return A[top]

// ---------- Linked-list-based stack ---------- structure Node: value next structure ListStack: head // reference to top node; null if empty ListStack.init(): head <- null ListStack.isEmpty(): return head == null ListStack.push(x): n <- new Node(value = x, next = head) head <- n ListStack.pop(): if isEmpty(): error "pop from empty stack" x <- head.value head <- head.next return x ListStack.peek(): if isEmpty(): error "peek on empty stack" return head.value ``` Both implementations expose exactly the same interface — `push`, `pop`, `peek`, `isEmpty` — so any client code (a parser, a DFS routine, an expression evaluator) can be written against the ADT alone, without knowing which realization backs it.

Time complexity.

• Linked-list stack: `push` and `pop` are O(1) worst case, always. Each touches only `head` and one node — no traversal, no dependency on stack size.
• Array stack: `push` and `pop` are O(1) amortized, and O(1) worst case except during a resize, when a single `push` costs $O(n)$ to copy $n$ existing elements into the new array. Using the standard doubling argument (identical to dynamic arrays): if the array doubles whenever full, then across any sequence of $n$ pushes starting from empty, the total copying work is

so the amortized cost per push is $O(n)/n = O(1)$. Pop never needs to reallocate in this simplified version (a further optimization is to shrink the array when it becomes at most $1/4$ full, halving it — this preserves $O(1)$ amortized pop as well, while avoiding oscillation between growing and shrinking at exactly half-full).

Space complexity. Both implementations use $O(n)$ space for $n$ elements. The array stack may have up to $2n$ allocated slots right after a doubling (a constant-factor overhead); the linked-list stack uses exactly $n$ nodes but each node carries the overhead of a `next` pointer, which is often larger in practice for small elements (e.g., a stack of integers wastes relatively more memory per element as a linked list than as an array).

Correctness argument. The proof that these implementations satisfy the LIFO contract is an invariant proof. Define the invariant $I$: > After any sequence of operations, the elements at indices $0, 1, \dots, \text{top}$ of the array (or the nodes reachable from `head` in the list) are exactly the currently-stored elements, in the order they were pushed, with `A[top]` (or `head.value`) equal to the most recently pushed element not yet popped.

• Base case: an empty stack (`top = -1`, or `head = null`) trivially satisfies $I$ — there are no elements, and "most recent" is vacuously undefined, matching `isEmpty() = true`.
• Inductive step (push): assume $I$ holds before `push(x)`. The operation places `x` immediately after the current top (index `top+1`, or as the new `head` whose `next` is the old `head`) and then updates the top pointer to reference it. Since `x` was just added and no other element moved, `x` is now the most recent, and $I$ holds again.
• Inductive step (pop): assume $I$ holds and the stack is non-empty. By $I$, the current top is the most recently pushed element; removing it and moving the top pointer to the previous element (`top - 1`, or `head.next`) restores $I$ for the remaining elements, whose relative order and "most recent" status are untouched.

Because $I$ holds initially and is preserved by every operation, it holds after any sequence of operations — this is exactly why `peek()` always returns the correct element and why `pop()` always undoes the most recent `push()` that hasn't already been undone.

Tradeoffs. Array stacks win on cache locality (contiguous memory, better for CPU prefetching) and lower per-element memory overhead, but pay for occasional resize spikes — a real concern in latency-sensitive systems, where an $O(n)$ push can violate a real-time deadline even though it is rare. Linked-list stacks give a hard worst-case guarantee per operation and never waste unused capacity, but every node is a separate heap allocation, hurting cache behavior and adding pointer overhead. Neither implementation supports efficient random access or search — both are $O(n)$ for "is $x$ in the stack," which is by design: a stack that let you peek at the middle would no longer be a stack.

Consider using a stack to check whether the string `"( a ( b ) [ c ] )"` has correctly balanced and nested brackets — a canonical stack application. The algorithm: scan left to right; push every opening bracket; on a closing bracket, pop and check that it matches.

Each `pop` in this trace relies on the stack invariant: at step 5, the top of the stack is guaranteed to be the innermost still-open bracket, because that is precisely the most recently pushed, not-yet-popped element — exactly what the invariant $I$ guarantees. If the input had instead been `"( a ( b ] )"`, step 5 would pop `(` while reading `]`, the mismatch would be detected immediately, and the algorithm would report the string as unbalanced in the same $O(n)$ single pass, using $O(n)$ stack space in the worst case (all opens, no closes, e.g. `"((((("`). This same "match against the top" pattern generalizes directly to evaluating postfix (reverse Polish) expressions, implementing undo/redo, and — via an explicit stack replacing the implicit call stack — converting a recursive tree traversal into an iterative one.

The stack as an explicit data structure emerged alongside the earliest work on programming language implementation, expression evaluation, and formal automata theory, where it became inseparable from the very definition of what a computer program's execution is.

Every function call in every programming language relies on a call stack: each call pushes a new stack frame holding local variables, parameters, and a return address, and returning from the function pops that frame — which is exactly why deep unbounded recursion causes a "stack overflow." Compilers and interpreters use explicit stacks to evaluate expressions (converting infix to postfix via the shunting-yard algorithm, then evaluating postfix with a stack), to manage nested scopes, and to implement virtual machines (the Java Virtual Machine and many bytecode interpreters are explicitly stack-based). Browsers use a stack for back-button history and undo systems in editors use one for undo/redo. Balanced-bracket and syntax checking in parsers, backtracking search (maze solving, Sudoku solvers, and general depth-first search), and iterative simulations of recursive algorithms all lean on the stack's LIFO discipline. The stack is also the conceptual seed for Tree Traversals (pre-order/in-order/post-order can be done recursively via the implicit call stack or iteratively via an explicit one) and shares its "simple pointer, strong invariant" design philosophy with the union-find structure at the heart of Disjoint-Set Union-Find.

Ask the tutor: How would you adapt this stack implementation to support a `getMin()` operation in O(1) time?