Lesson 12 · Linear structures

Stacks

A stack is a Last-In-First-Out (LIFO) data structure. While conceptually simple, the choice of underlying implementation affects memory and performance. Stacks are the foundation of recursion, parsing, and expression evaluation.

One End, Four Operations

A stack is a linear structure with a single point of access. Elements are added and removed at the same end, called the top, so the most recently added element is always the first one out — Last In, First Out.

Four operations define it. push places a value on the top. pop removes and returns the top value. peek (or top) reads the top without removing it. isEmpty reports whether anything remains. All four are O(1), because each touches one end and never examines the rest.

Two error conditions deserve explicit names. Underflow is popping or peeking an empty stack; it must throw or return a sentinel, never silently return whatever memory happens to be there. Overflow is pushing to a fixed-capacity stack that is full — impossible with a dynamically sized backing, but very real for a fixed array and for the call stack.

What defines the structure is what it refuses. There is no indexing, no search, no reaching into the middle. That restriction is the value: a stack in a signature is a promise about ordering, and any implementation offering more than these four operations has stopped being a stack and given up the guarantee that made it worth choosing.

All access happens at the top — LIFO
push, pop, peek, isEmpty, each O(1)
Underflow on empty; overflow only when capacity is fixed
No indexing and no search — the restriction is the point

Array or Linked List

An array-backed stack keeps the elements contiguous and an integer top marking the next free slot. Push writes at top and increments; pop decrements and reads. Elements sit consecutively in memory, so the CPU prefetches them and the structure is fast in practice — usually the better default.

Its one complication is capacity. When the array fills, a larger one is allocated and everything copied across, an O(n) event. Because implementations double the capacity, those copies grow rarer at exactly the rate their cost grows, so the average cost per push stays constant: push is amortised O(1), not worst-case O(1). A single unlucky push can still cost O(n), which matters for real-time code and is worth stating precisely in an exam answer.

A linked-list-backed stack pushes by allocating a node and inserting at the head, and pops by advancing the head. There is no capacity and no resize, so every operation is strictly O(1) with no amortisation. The costs are a pointer per element, an allocation per push, and nodes scattered across memory that defeat prefetching.

Choose the array unless you specifically need the worst-case guarantee or cannot tolerate a large contiguous allocation. This is why std::vector backs std::stack by default, why Python's list is the idiomatic stack via append and pop, and why Java's older Stack class — synchronised and inheriting from Vector — is superseded by ArrayDeque.

The two backings, and what each costs
	Array-backed	Linked-list-backed
Push	Amortised O(1)	Strict O(1)
Pop, peek	O(1)	O(1)
Worst-case push	O(n) on resize	O(1)
Memory per element	Value only	Value + pointer + allocation header
Locality	Contiguous, prefetched	Scattered, cache misses
Capacity	Grows by reallocation	Unbounded

Array: contiguous and fast, amortised O(1) on push
Doubling makes resizes rare enough to average out
Linked list: strictly O(1), no resize, worse locality
Prefer the array unless worst-case latency matters

Evaluating Expressions

Arithmetic as humans write it — infix, as in 3 + 4 × 2 — is awkward for a machine because precedence and parentheses mean the operators cannot simply be applied in order. Converting to postfix (reverse Polish notation), where the same expression is 3 4 2 × +, removes the ambiguity entirely: no parentheses are needed and no precedence rules apply at evaluation time.

Dijkstra's shunting-yard algorithm performs the conversion with an operator stack. Operands go straight to the output; an operator pops any stacked operators of higher or equal precedence to the output before being pushed itself; a closing parenthesis pops back to its matching opener. The stack is what holds operators whose operands are not yet complete.

Evaluating the postfix result then needs a second stack, this one holding operands. Push each number; on an operator, pop two values, apply, and push the result back. When the input is exhausted a single value remains, and it is the answer.

Order matters on non-commutative operators. The first value popped is the right operand, so subtraction and division must be applied as second_popped OP first_popped. Reversing them yields correct results for + and × and silently wrong ones for − and ÷, which is why it survives casual testing.

This is not a teaching exercise — it is roughly how expression evaluation works inside interpreters and calculators, and stack-based virtual machines such as the JVM and CPython execute bytecode on exactly this model.

Postfix removes precedence and parentheses from evaluation
Shunting-yard converts infix using an operator stack
Evaluation pushes operands and pops two per operator
First popped is the right operand — critical for − and ÷

Key reference

Terms, operations, and practical uses

Core operations

PushAdding an element to the top of the stack. O(1) time complexity.
PopRemoving and returning the element at the top of the stack. O(1) time complexity.
Peek / TopLooking at the element on the top of the stack without removing it.

Implementation details

Array BackingUsing a dynamic array and an integer 'top' index. Extremely cache-friendly but occasionally requires O(N) resizing.
Linked List BackingInserting and removing strictly at the 'head' node. No resizing overhead, but causes memory fragmentation.
Stack OverflowAn error that occurs when a stack exceeds its allocated memory limit, most famously caused by infinite recursion.

Practical applications

Call StackThe internal structure used by the OS and runtime to track active function calls, local variables, and return addresses.
Expression ParsingUsing stacks to validate nested parentheses, brackets, or XML/HTML tags.
Shunting-YardDijkstra's algorithm for parsing mathematical equations from human-readable Infix notation to machine-friendly Postfix notation.

Implementation

Validating Parentheses

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs.keys():
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    return len(stack) == 0

print('Valid:', is_valid("{[()]}"))

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (pairs.count(c)) {
            if (st.empty() || st.top() != pairs[c]) return false;
            st.pop();
        }
    }
    return st.empty();
}
int main() {
    cout << "Valid: " << (isValid("{[()]}") ? "True" : "False") << endl;
    return 0;
}

import java.util.*;
class Main {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(c)) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println("Valid: " + (isValid("{[()]}") ? "True" : "False"));
    }
}

Watch it run

Step through it

Running on String: '{ [ ( ) ] }'

Output

Read all 14 Steps

An empty stack, and a string to scan We read '{[()]}' left to right. The stack starts empty and only ever grows or shrinks at its top — that single restriction is what makes this problem O(n) instead of a nested search.
Read '{' — push it Opening brackets carry no information about whether they are correct yet, so we defer the decision: push '{' and move on. The stack is now remembering one unclosed bracket.
Read '[' — push it Another opening bracket, pushed on top of the first. The stack order now records the nesting order exactly: '{' was opened first, so it must be closed last.
Read '(' — push it Three unclosed brackets. The top of the stack is always the most recently opened one, which is precisely the one that must close next.
Read ')' — compare against the top The first closing bracket. Its partner must be '(' and the top of the stack is '(' — so peek and compare. Nothing has been removed yet; this step is the test.
Match — pop it The pair is closed, so the '(' is discarded. The stack shrinks to two, and the square bracket becomes the new top — the next one that must be closed.
Read ']' — compare against the top The closing square bracket needs its opening partner, which is exactly what sits on top. We never search the stack: only the top can match, because anything below it was opened earlier and must close later.
Match — pop it Two pairs closed, one left. Every character so far has been touched exactly once, which is where the O(n) comes from.
Read '}' — compare against the top The closing brace needs '{', and the last remaining item is '{'. The first bracket opened is the last one closed, which is the definition of correct nesting.
Match — pop it The stack empties at the same moment the string is exhausted.
Both empty — the string is valid Two conditions must hold at the end: the string is finished AND the stack is empty. Both are true here, so every bracket was matched in the right order.
Failure 1: the wrong closer Scanning '{[)]}' instead, the ')' arrives while the top of the stack is a square bracket. The comparison fails, so the function returns false immediately without reading the rest of the string.
Failure 2: the stack runs out Scanning '())', the third character is a closing bracket with an empty stack beneath it. There is nothing to pop against, and popping anyway is the crash most people write on their first attempt — test isEmpty before popping.
Failure 3: leftovers at the end Scanning '{[', the string ends with two brackets still stacked. Nothing fails during the loop, which is exactly why the final emptiness check exists — without it this input would wrongly pass.

The Call Stack

The most consequential stack is the one the runtime maintains for you. Each function call pushes a stack frame holding the arguments, local variables, and the return address; when the function returns, its frame is popped and execution resumes at that address.

LIFO is the correct discipline here for a structural reason: calls nest exactly as brackets do. If a calls b which calls c, then c must finish before b can, which must finish before a can. The most recently started call is always the next to complete.

This is also what makes recursion work. Each recursive call gets its own frame with its own copy of the locals, so the parameters of one level do not disturb another. The base case is what stops the pushing; without it, frames accumulate until the stack's fixed region of memory is exhausted and the program dies with a stack overflow — typically after a few thousand to a few tens of thousands of frames, depending on frame size and platform.

Understanding the call stack is what makes a stack trace readable: it is a snapshot of the frames, innermost first, showing exactly the chain of calls that led to the failure.

The relationship runs both ways, which is worth remembering. Any recursive algorithm can be rewritten iteratively by managing an explicit stack of the state the frames were holding — the standard escape when input depth would otherwise overflow, and the reason iterative depth-first search and iterative tree traversals exist.

A frame per call holds locals, arguments, and the return address
Nested calls complete in reverse order — LIFO by necessity
Recursion depth without a base case exhausts the stack
An explicit stack converts any recursion into iteration