Stacks

The previous three lessons described concrete layouts: a contiguous block, a growing block, linked nodes. This lesson asks a different question — not how the data is stored, but which operations are permitted.

Abstract Data Type

An abstract data type defines the operations a structure offers and what those operations mean; it does not say how the data sits in memory. It is the data structures counterpart of the interface–implementation distinction from the Programming Fundamentals course.

The distinction’s value runs both ways. The consumer writes code relying only on the contract; the implementer can change the internal structure without breaking the contract. The same abstract type can be implemented in more than one way, each with a different cost profile.

The stack is the abstract data type this lesson covers, and it is defined by a single rule: the last element added is the first one out.

Stack Operations

Four operations suffice:

Operation	Meaning	Cost
push	Adds an element to the top	$O(1)$
pop	Removes and returns the top element	$O(1)$
peek	Shows the top element without removing it	$O(1)$
is_empty	Reports whether the stack is empty	$O(1)$

The operations not on this list are also part of the definition: a middle element cannot be accessed in a stack, there is no search, there is no traversal. The restriction is not a deficiency but the design itself — a restricted interface makes misuse impossible.

Two Implementations

The same contract can be met by two different structures, and both perform every operation in constant time.

With a dynamic array: The top is the end of the array. Insertion is appending, removal is deleting from the end; neither requires shifting. The amortized cost is constant, and cache behavior is good thanks to contiguous layout.

With a linked list: The top is the head of the list. Prepending and removing from the head are constant time. Reallocation never happens; in exchange, there is per-node pointer overhead and scattered layout.

The selection criterion repeats the previous lessons’ conclusion: a dynamic array if predictable single-operation duration is not required, a linked list if it is.

class Stack:
    """Last in, first out; built on a dynamic array."""

    def __init__(self) -> None:
        self._data: list = []

    def push(self, value) -> None:
        self._data.append(value)

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

    def peek(self):
        if self.is_empty():
            raise IndexError("an empty stack has no top")
        return self._data[-1]

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)


stack = Stack()
for measurement in (12, 18, 7):
    stack.push(measurement)

print(stack.peek(), len(stack))       # 7 3
print(stack.pop(), stack.pop())       # 7 18
print(len(stack), stack.is_empty())   # 1 False

Popping from an empty stack raising an error is part of the contract. Silently returning a null value would carry the null value problem from the Programming Fundamentals course over to the caller.

Why the Stack

The stack is the natural structure for every problem that can be described as “return to the most recently unfinished task.”

The call stack. The frame arrangement established in the How Computers Work course is exactly this: the function called last returns first. Recursion depth was this stack’s fullness.

Undo. Operations performed in an editor are pushed onto a stack; undo pops the top operation.

Matching validation. Every opening parenthesis is pushed onto a stack; every closing parenthesis is compared against the top.

Backtracking. Keeping tried choices on a stack makes it possible to return to the last decision when a dead end is reached.

Depth-first search. As will be seen in this course’s final topic, depth-first search in graphs runs on a stack — in its recursive form, this stack is the call stack itself.

Example: Parenthesis Checking

Whether the parentheses in a piece of text match correctly is tested in a single pass, with a stack:

MATCHES = {")": "(", "]": "[", "}": "{"}

def is_balanced(text: str) -> bool:
    """Tests whether the parentheses open and close in the correct order."""
    stack = Stack()
    for char in text:
        if char in "([{":
            stack.push(char)
        elif char in MATCHES:
            if stack.is_empty() or stack.pop() != MATCHES[char]:
                return False                # a closing bracket that does not match
    return stack.is_empty()                 # unbalanced if anything is left open


print(is_balanced("(12 + [18 - 7])"))       # True
print(is_balanced("(12 + [18 - 7)]"))       # False   — out of order
print(is_balanced("((12)"))                 # False   — left open
print(is_balanced("12)"))                   # False   — extra closing bracket

The reason the solution requires a stack is that the depth of nesting is not known in advance: the most recently opened parenthesis is the one that must close first. The same structure applies to anything that nests — code blocks, markup tags, expression parsing.

This is the core of the parsing stage covered in the previous course; the nested structures of grammar rules are processed on a stack.

Example: Expression Evaluation

The second classic use is evaluating arithmetic expressions. In postfix notation, where operators are written after their operands, no parentheses are needed and evaluation runs with a single stack: a number is pushed when seen, and when an operator is seen, two values are popped and the result is pushed back.

def evaluate_postfix(expression: str) -> float:
    """Computes a postfix-notation expression using a stack."""
    stack = Stack()
    for token in expression.split():
        if token in "+-*/":
            right = stack.pop()
            left = stack.pop()
            if token == "+": stack.push(left + right)
            elif token == "-": stack.push(left - right)
            elif token == "*": stack.push(left * right)
            else: stack.push(left / right)
        else:
            stack.push(float(token))
    return stack.pop()


print(evaluate_postfix("12 18 +"))            # 30.0
print(evaluate_postfix("12 18 + 2 /"))        # 15.0   — (12 + 18) / 2
print(evaluate_postfix("12 18 7 - +"))        # 23.0   — 12 + (18 - 7)

The second call is the postfix form of the average calculation used throughout this course. Note the importance of pop order: the value popped first is the right operand, because it is the one pushed last. If this order is mixed up in subtraction and division, the result comes out silently wrong.

Converting an expression in the (familiar) infix form to postfix notation also requires a stack; operator precedence determines when the operators waiting on the stack are popped. A compiler’s expression-parsing stage is a generalized form of this arrangement.

Limits

The stack’s restricted interface brings with it some questions that cannot be answered: how many elements have a given value, what a middle element is, whether the elements are sorted. If this information is needed, the stack is the wrong choice.

In a fixed-capacity implementation there is a second limit: overflow occurs when capacity fills up. The stack overflow in the How Computers Work course was this situation’s counterpart in the call stack.

Cost Table

Structure	Access	Search	Insert	Delete
Dynamic array	$O(1)$	$O(n)$	at end $O(1)$ amortized	from middle $O(n)$
Linked list	$O(n)$	$O(n)$	at start $O(1)$	node in hand $O(1)$
Stack	top only $O(1)$	—	$O(1)$	$O(1)$

Summary

• An abstract data type defines the operations offered and their meanings; it does not specify layout.
• The stack is defined by the last-in-first-out rule, and its four operations are constant time.
• A restricted interface is not a deficiency but a design decision that prevents misuse.
• A dynamic array and a linked list implement the stack with the same costs; the choice is made based on single-operation duration and cache behavior.
• Call management, undo, matching validation, and backtracking are the family of problems solved with a stack.
• Popping from an empty stack raises an error; in a fixed-capacity implementation, overflow is the second limit.

Next Step

In some problems, the expected behavior is the reverse: the first to arrive must be the first processed — in a job queue, a printer line, a network buffer. The next lesson takes up this model and the circular buffer that allows continuous stream processing with fixed memory.