3.1 Stacks: Last In, First Out

Prerequisites: Choosing Arrays or Linked Lists. This section first enforces the LIFO contract, then compares array-based and linked-list-based stacks, and finally applies the same principle to bracket matching and depth-first search.

LIFO Uses One Accessible End

Push key, brick, and book into one container, then pop three times. The observed order is book, brick, key. The interface guarantees:

Items placed later are retrieved first; items placed earlier are retrieved later.

This rule is Last In, First Out (LIFO). An abstract data type that follows it is a stack. We care about the behavior at the top; the implementation may use an array, a linked list, or another structure that preserves the same contract.

Remember the Operation Contract

Operation	Meaning	Agreement when stack is empty	Target cost in abstract model
push(x)	Push x onto the stack top	Always insert, unless resource exhaustion occurs	Θ(1)
pop()	Pop and return the top element	Throw an exception or return a failure state	Θ(1)
peek()	Peek at the top element without removing it	Throw an exception or return a failure state	Θ(1)
is_empty()	Check if the stack is empty	Return True	Θ(1)
len(stack)	Return the number of elements	Return 0	Θ(1)

Performing pop or peek on an empty stack is called underflow. Different libraries handle failure differently: some throw exceptions, others return null or a boolean status. When designing an interface, you must choose one contract, and the caller must adhere to the same contract.

One Stack, Two Ways to Store

The first approach places the stack top at the right end of a dynamic array. CPython list appends and tail pops take amortized Θ(1) time. An append may grow the buffer; a pop may shrink it. Tail removal avoids suffix shifts, but allocation or copying can still take more than constant work. The list_pop_impl and list_resize functions in CPython 3.14 show this path.

The second approach uses a singly linked list with the head as the stack top. push creates a node before the old head; pop moves the head pointer past it. In the linked list abstract model, both operations are Θ(1); actual runtime also incurs the overhead of each node allocation and link preservation.

The following program processes a batch of items using two different implementations and verifies that the results are consistent:

class ArrayStack:
    def __init__(self):
        self._data = []

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

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

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

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

    def to_list(self):
        return self._data.copy()

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

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class LinkedStack:
    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, item):
        self._head = Node(item, self._head)
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self._head.value
        self._head = self._head.next
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._head.value

    def is_empty(self):
        return self._head is None

    def to_list(self):
        values = []
        current = self._head
        while current is not None:
            values.append(current.value)
            current = current.next
        return list(reversed(values))

    def __len__(self):
        return self._size

def is_valid_brackets(text):
    matching = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in matching.values():
            stack.append(char)
        elif char in matching:
            if not stack or stack.pop() != matching[char]:
                return False
    return not stack

if __name__ == "__main__":
    array_stack = ArrayStack()
    linked_stack = LinkedStack()
    for item in ["alpha", "beta", "gamma"]:
        array_stack.push(item)
        linked_stack.push(item)

    print(f"Top of the stack: {array_stack.peek()}")
    print(f"Popped: {array_stack.pop()}")
    linked_stack.pop()
    print(f"Remaining: {array_stack.to_list()}")
    print(
        "Bracket matching: "
        f"{is_valid_brackets('map[{key}]')} "
        f"{is_valid_brackets('map[(])')}"
    )

    assert array_stack.to_list() == linked_stack.to_list()
    assert len(array_stack) == len(linked_stack) == 2
    print("Stack check passed")

Top of the stack: gamma
Popped: gamma
Remaining: ['alpha', 'beta']
Bracket matching: True False
Stack check passed

Read the Array Stack

1. _data[-1] is on top of the stack. Stack users should not bypass the interface to modify _data.
2. push adds elements to the right end; pop removes from the right end.
3. peek reads only from the stack top, so it doesn't change the length.
4. pop and peek first check for an empty stack to avoid treating accidental errors in the underlying container as part of the public contract.
5. to_list returns a copy, allowing examples to inspect the status without leaking the internal list.

Read the Linked Stack

Assume the nodes from the head are gamma -> beta -> alpha:

• push("delta") creates a new node, points it to the old head, then updates _head to point to the new node.
• pop() saves the value of the old head, and _head points to the second node.
• Neither operation involves traversing the linked list.

Both to_list methods make a shallow copy for inspection, using Θ(n) time and output space; the linked version also traverses the nodes. A copy still shares its element objects. Its cost is separate from an individual push or pop.

Bracket Matching: Saving the Most Recent Unfinished Work

While scanning map[{key}], an opening bracket represents unfinished nesting, so push it onto the stack. A closing bracket must match the most recent unmatched opening bracket. Skipping an inner bracket to match an outer one would cross the pairs.

Take [(]) as an example:

Character read	Stack (bottom → top)	Action
[	[	Left bracket pushed onto stack
(	[ (	Left bracket pushed onto stack
]	[ (	Top of stack is (, which does not match ], failure

This algorithm has three failure paths:

• A right bracket appears when the stack is empty, indicating a missing left bracket;
• The stack is nonempty, but its top has the wrong bracket type, as in [(]);
• After processing all input, the stack is not empty, indicating a missing closing right bracket.

The function deliberately ignores non-bracket characters. Real programming languages have more complex lexical and grammatical rules; parsers often use explicit stacks, implicit stacks formed by recursive function calls, or a combination of both to handle nested structures. This program checks only pairing and nesting of three bracket types; it does not recognize brackets inside strings or comments. For n input characters, worst-case time and auxiliary space are Θ(n), as with an input consisting only of opening brackets.

Explicit Stack and Call Stack

Recursive functions pass off "what to do next" to the call stack for preservation. An iterative version can instead store the same state in an explicit container. Both approaches consume memory, but differ in whether the state is managed by the runtime or by the program itself.

def depth_first_order(graph, start):
    order = []
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        stack.extend(reversed(graph[node]))
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
assert depth_first_order(graph, "A") == ["A", "B", "D", "C"]

Every reachable vertex must have an adjacency list in graph. Reversing neighbors makes the leftmost neighbor pop first. Since marking happens on pop, a vertex may enter the stack several times, though it is expanded only once. Let V and E count reachable vertices and adjacency entries. With constant-time hashing, time is Θ(V+E); this explicit stack can hold O(V+E) entries in the worst case. It does not inherit recursive DFS’s O(V) stack-space bound.

An empty operation can also return a status rather than throw an exception. The key is to avoid leaving the caller guessing:

def try_pop(stack):
    if not stack:
        return False, None
    return True, stack.pop()

assert try_pop([]) == (False, None)
assert try_pop([None]) == (True, None)
assert try_pop(["Key"]) == (True, "Key")

Python's recursion limit is not a fixed value of "about 1000." The current interpreter value can be read via sys.getrecursionlimit(), and can also be adjusted within allowed bounds. Increasing the limit does not eliminate constraints from the C stack or process memory. When dealing with deeply nested trees or graphs, an explicit stack typically provides better control over failure conditions and memory usage.

The call stack is implemented by the language runtime, the ABI, compiler-generated calling conventions, and the machine's registers and instructions. This section uses only the LIFO relationship and does not analyze these system-level details.

Stack Interfaces in Common Languages

Language	Recommended Container	Push / Pop / Peek	Notes
Python	list	append(x) / pop() / stack[-1]	Tail append/pop are amortized O(1); an empty pop or read raises IndexError
Java 17	Deque<E> + ArrayDeque<E>	push / pop / peek	Stack is a legacy API, without @Deprecated; ArrayDeque rejects null and is not thread-safe; empty pop throws, empty peek returns null
C++	std::stack<T>	push / pop / top	Defaults to std::deque; check nonempty, then read top and call pop; pop returns no element

References:

• Python list as a stack
• Java Stack
• Java Deque
• C++ std::stack

How to Diagnose Common Errors

Symptom	First Check
Stack pop order appears FIFO	Are push and pop on the same end of the stack?
Failure on an empty stack is hard to locate	Does the public method check whether the stack is empty?
Crossed bracket pairs return true	Is the closing parenthesis being compared against the stack top, not against any arbitrary left parenthesis?
Still misjudges true after scanning ends	Is the stack empty checked before returning?
Incorrect linked list stack length	Is push and the successful pop each updating _size exactly once per operation?

Hands-on Verify LIFO and Underflow

1. Push A, B, C sequentially, then call pop twice. What do you get? What remains in the stack?
2. Write a test for an empty stack with peek. What exception should it throw?
3. Manually compute the stack state after {a[(b+c)]} and {a[(b+c])}.
4. Add clear to the linked stack. Updating its head and size takes constant assignments; why might reclaiming n old nodes still take Θ(n) work?
5. Advanced: Implement a queue using two stacks. Why does each element move between the two stacks only once?

State the Stack’s Boundaries

push and pop use the same end, peek preserves the length, and an empty operation fails as documented. Test both stack implementations with the same inputs, then account separately for resizing and to_list. Bracket matching also needs type checks and a final check for unmatched openings.

Next, queues show how first-in, first-out changes the roles of the two ends.