Stacks: newest first

After this page, you should be able to:

• Trace newest-first access with explicit returns and empty behaviour.

• Connect an array-backed invariant to amortised endpoint costs.

Builds on: Sequence operations permit arbitrary positions; a stack exposes only its top.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Julia uses one-based positions and named functions such as enqueue! rather than Python-style instance methods. Endpoint adapters use the supplied linked DequeBuffer, so they do not hide linear array-front shifts. Empty operations reject the request; null/nothing remain valid payloads.

LIFO and the top¶

A stack adds and removes items at one logical end, the top. It follows last in, first out (LIFO): the most recently pushed item still present is the next one popped.

Empty operations need a policy¶

Popping an empty stack is underflow. Here both empty pop() and empty peek() raise IndexError. Returning None instead would be ambiguous if None were a legitimate stored item, unless the interface supplied another way to distinguish these outcomes.

Trace the result and state separately¶

Starting empty, push A, B and C: each push returns None. peek() returns C and leaves A,B,C stored. pop() returns C and leaves A,B. Pushing D then returns None and leaves A,B,D, matching the diagram. Duplicates and None are permitted; exceptions distinguish an empty stack from a stored None.

An array-backed implementation¶

Use the back of a Python list as the top. Adding or removing there avoids shifting the earlier references.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return not self._items

class Stack {
    constructor() { this._items = []; }
    push(item) { this._items.push(item); }
    pop() { if (this.is_empty()) throw new RangeError("empty stack"); return this._items.pop(); }
    peek() { if (this.is_empty()) throw new RangeError("empty stack"); return this._items.at(-1); }
    size() { return this._items.length; }
    is_empty() { return this.size() === 0; }
}

mutable struct Stack
    items::Vector{Any}
end
Stack() = Stack(Any[])
stack_push!(s::Stack, item) = (push!(s.items, item); nothing)
function stack_pop!(s::Stack)
    isempty(s.items) && throw(BoundsError())
    return pop!(s.items)
end
function stack_peek(s::Stack)
    isempty(s.items) && throw(BoundsError())
    return s.items[end]
end
Base.length(s::Stack) = length(s.items)
Base.isempty(s::Stack) = isempty(s.items)

The representation rule is: _items holds the logical stack from bottom to top, and its last position is the top. The underscore marks internal state by convention; clients should use the stack methods. push returns None, while pop returns the removed item.

Implementation choices and operation costs¶

Choosing the list’s back as the top avoids shifting other records. Using index zero instead would preserve LIFO if both operations used that end, but would make updates linear. A linked stack puts its top at the head and changes a fixed number of links.

Persistent storage is O(n+1) references under ordinary dynamic-array capacity management. The invariant establishes correctness: append creates the newest top; back removal selects exactly that top; observation does not mutate it.

The amortised bound includes occasional growth or shrinking; it is not a constant worst-case promise for every call.

Reversing and nesting¶

Undo history reverses recent actions: changing a colour is undone before the earlier action of adding a label. A useful stack stores enough information to reverse each action, not merely its name. Function calls also nest: a called function finishes before its caller resumes. See the call stack.

Match the most recent unmatched opener¶

For nested brackets, keep unmatched opening symbols in a stack. A closing symbol must match the top. Counting opening and closing symbols is insufficient: ({)} has equal counts but incorrect nesting.

def brackets_balanced(text):
    openers = []
    matching = {')': '(', ']': '[', '}': '{'}
    for symbol in text:
        if symbol in '([{':
            openers.append(symbol)
        elif symbol in matching:
            if not openers or openers.pop() != matching[symbol]:
                return False
    return not openers

function brackets_balanced(text) {
    const openers = [], matching = new Map([[")", "("], ["]", "["], ["}", "{"]]);
    for (const symbol of text) {
        if (["(", "[", "{"].includes(symbol)) openers.push(symbol);
        else if (matching.has(symbol)) {
            if (!openers.length || openers.pop() !== matching.get(symbol)) return false;
        }
    }
    return openers.length === 0;
}

function brackets_balanced(text)
    openers = Char[]
    matching = Dict(')'=>'(', ']'=>'[', '}'=>'{')
    for symbol in text
        if symbol in "([{"
            push!(openers, symbol)
        elseif haskey(matching, symbol)
            (isempty(openers) || pop!(openers) != matching[symbol]) && return false
        end
    end
    return isempty(openers)
end

The invariant is that the stack contains exactly the unmatched openers in the processed prefix, in nesting order. An unexpected closer or wrong type rejects immediately; leftover openers reject at the end. This teaching function ignores all non-bracket characters; it does not parse quoted strings or comments in a programming language.

For $n$ characters, the scan takes $O(n)$ time and up to $O(n)$ auxiliary space; early rejection can finish sooner.

Check your understanding¶

Predict the operation result and the resulting state before opening the explanation.

1. Push None onto an empty stack, then pop. What is returned and what is the size?

2. If a list-backed stack uses the front for push and pop, is it still LIFO?

Next: Queues.