Stacks & Applications

Topics Covered:
30. Stack Abstract Data Type (LIFO) & Core Operations • Static & Dynamic Array Stack Implementations (Amortized Analysis) • Linked List Stack • Hardware Call Stack & Activation Records • Expression Evaluation (Infix, Prefix, Postfix, Shunting-Yard Algorithm) • Balanced Delimiter Matching (Dyck Language & Formal Induction Proof) • Production Multi-Language Implementations

The stack is one of computing's most fundamental restricted-access linear abstractions, operating under the strict Last-In, First-Out (LIFO) principle. All element insertions and removals occur at a single designated boundary: the top. Beyond its utility as a software container, the stack is embedded directly into computer architecture as the CPU execution call stack, powering subroutine invocation, local variable scoping, and recursion. This chapter examines array and pointer-linked stack implementations, activation record lifecycles, balanced bracket validation, postfix expression evaluation, and Dijkstra's Shunting-Yard parsing algorithm.

• Formalize the Stack Abstract Data Type (ADT) interface and enforce strict Last-In, First-Out (LIFO) invariants.
• Compare contiguous dynamic-array stack backing buffers against heap pointer-linked implementations in terms of allocation latency and memory overhead.
• Trace hardware activation records, frame pointers (%rbp), and return addresses on the physical CPU call stack to diagnose stack overflow and buffer overflow conditions.
• Prove the correctness of linear-time balanced delimiter matching over the Dyck Language $D_k$ using mathematical induction.
• Implement postfix (Reverse Polish Notation) arithmetic evaluation and Dijkstra's Shunting-Yard algorithm for converting infix expressions to postfix.
• Master robust production implementations across C++, Python, and Java with full error handling and cache consciousness.

A Stack restricts element access to a single boundary called Top:

• Push: Places an element onto the top of the container.
• Pop: Removes and returns the element currently residing at the top.
• Peek / Top: Inspects the value of the top element without mutating state.

Interactive Simulations:
Experiment with LIFO dynamics live in the Interactive Stack Push Simulator and the Interactive Stack Pop Simulator.

Paradigm A: Contiguous Array Implementation

Maintains a backing array storage[] and an integer offset topIndex:

• Empty State: topIndex = -1.
• Push($x$): Check bounds; topIndex += 1; storage[topIndex] = x;.
• Pop(): Check for underflow (topIndex == -1); val = storage[topIndex]; topIndex -= 1; return val;.

Amortized Cost: When backed by a geometrically doubling dynamic array, Push incurs occasional $O(n)$ reallocations, but achieves $O(1)$ amortized cost across any sequence of $n$ operations while maintaining exceptional CPU L1/L2 cache locality.

Paradigm B: Linked-List-Based Stack

Maintains a pointer to the head node:

• Push(x): Allocate new node, set newNode.next = top, top = newNode.
• Pop(): Retrieve top.data, advance top = top.next, free old node.

Guaranteed Strict Bound: Every single operation executes in guaranteed worst-case $\Theta (1)$ time without memory reallocation pauses, but consumes $16\text{ bytes}$ of pointer and padding overhead per element.

In von Neumann computer architecture, subroutine execution is governed by the hardware call stack located in the upper region of the process virtual address space. On x86-64 / AMD64 architectures:

• The stack grows downward from higher memory addresses toward lower memory addresses.
• The %rsp (Stack Pointer) register holds the memory address of the current top of the stack.
• The %rbp (Base / Frame Pointer) register anchors the base of the current subroutine activation record.

Call Stack Lifecycle:

1. Prologue: When a function is called (callq):
   • The CPU pushes %rip (return address) onto the stack.
   • The callee executes: pushq %rbp; movq %rsp, %rbp; subq $N, %rsp; to allocate $N$ bytes of local stack memory.
2. Epilogue: Before returning (retq):
   • The callee executes: movq %rbp, %rsp; popq %rbp; retq;.
   • The CPU pops %rip into the program counter and resumes the caller seamlessly.
3. Stack Overflow: If recursive invocations exceed the OS stack ceiling (typically 8 MB on Linux, 1 MB on Windows), %rsp collides with the memory guard page, triggering an immediate SIGSEGV fault.

The balanced parenthesis problem requires validating whether a string $S$ over alphabet $\Sigma =\{(,),[,],\{,\}\}$ belongs to the Dyck Language $D_k$.

Grammar of $D_k$:

Correctness Invariant & Induction Proof:

• Loop Invariant: Prior to scanning index $i$, the stack contains the exact sequence of unmatched open delimiters in the order they were opened.
• Base Case ($i=0$): The stack is empty. An empty prefix $\epsilon$ has no unmatched delimiters. Invariant holds.
• Inductive Step: Assume invariant holds for prefix $S[0\dots i-1]$.
  • If $S[i]\in \{(,[,\{\}$, it must eventually match a future closing bracket of the same type. Pushing $S[i]$ onto the stack preserves the invariant.
  • If $S[i]\in \{),],\}\}$, by the Dyck grammar, the most recently opened unmatched delimiter must be its exact counterpart. Peeking at TOP:
    • If stk.IsEmpty(), an unopen closing delimiter exists $⟹$ invalid.
    • If stk.Top() != match(S[i]), delimiters are improperly nested $⟹$ invalid.
    • If stk.Top() == match(S[i]), popping the top successfully completes the inner Dyck reduction $\mathcal{S}\to (\mathcal{S})$. The invariant is preserved for $S[0\dots i]$.
• Termination: At string conclusion ($i=n$), $S\in D_k⟺\text{stk.IsEmpty()}$. Any remaining element represents an unclosed delimiter. $■$

Mathematical expressions can be formalized in three distinct notations:

1. Infix: $A+B\times C$ (human-readable; requires operator precedence and parentheses).
2. Prefix (Polish): $+A\times BC$ (operator precedes operands).
3. Postfix (Reverse Polish Notation / RPN): $ABC\times +$ (operands precede operator; zero parentheses required).

Step-by-Step Conversion Trace: 3 + 4 * 2 / ( 1 - 5 )

A. C++20 Cache-Conscious Templated Dynamic Stack

#include <iostream>
#include <vector>
#include <stdexcept>
#include <string>

template <typename T>
class ArrayStack {
private:
    T* buffer_;
    size_t capacity_;
    size_t size_;

    void resize(size_t new_capacity) {
        T* new_buffer = new T[new_capacity];
        for (size_t i = 0; i < size_; ++i) {
            new_buffer[i] = std::move(buffer_[i]);
        }
        delete[] buffer_;
        buffer_ = new_buffer;
        capacity_ = new_capacity;
    }

public:
    explicit ArrayStack(size_t initial_capacity = 8)
        : buffer_(new T[initial_capacity]), capacity_(initial_capacity), size_(0) {}

    ~ArrayStack() {
        delete[] buffer_;
    }

    // Disable copy for RAII safety
    ArrayStack(const ArrayStack&) = delete;
    ArrayStack& operator=(const ArrayStack&) = delete;

    // Enable move semantics
    ArrayStack(ArrayStack&& other) noexcept
        : buffer_(other.buffer_), capacity_(other.capacity_), size_(other.size_) {
        other.buffer_ = nullptr;
        other.capacity_ = 0;
        other.size_ = 0;
    }

    void push(const T& item) {
        if (size_ == capacity_) {
            resize(capacity_ * 2);
        }
        buffer_[size_++] = item;
    }

    void push(T&& item) {
        if (size_ == capacity_) {
            resize(capacity_ * 2);
        }
        buffer_[size_++] = std::move(item);
    }

    T pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow: cannot pop from empty stack.");
        }
        T val = std::move(buffer_[--size_]);
        if (size_ > 0 && size_ <= capacity_ / 4 && capacity_ > 8) {
            resize(capacity_ / 2);
        }
        return val;
    }

    [[nodiscard]] const T& top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty.");
        }
        return buffer_[size_ - 1];
    }

    [[nodiscard]] bool empty() const noexcept { return size_ == 0; }
    [[nodiscard]] size_t size() const noexcept { return size_; }
};

B. Python 3 Production Shunting-Yard & Postfix Evaluator

from typing import List

def shunting_yard(tokens: List[str]) -> List[str]:
    """Converts an infix token list into Reverse Polish Notation (RPN)."""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    right_associative = {'^'}
    output: List[str] = []
    op_stack: List[str] = []

    for token in tokens:
        if token.isnumeric() or (token.startswith('-') and token[1:].isnumeric()):
            output.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack and op_stack[-1] != '(':
                output.append(op_stack.pop())
            if not op_stack:
                raise ValueError("Mismatched parentheses in expression.")
            op_stack.pop()  # Discard '('
        elif token in precedence:
            curr_p = precedence[token]
            while (op_stack and op_stack[-1] != '(' and
                   (precedence.get(op_stack[-1], 0) > curr_p or
                    (precedence.get(op_stack[-1], 0) == curr_p and token not in right_associative))):
                output.append(op_stack.pop())
            op_stack.append(token)
        else:
            raise ValueError(f"Unrecognized token: {token}")

    while op_stack:
        op = op_stack.pop()
        if op in {'(', ')'}:
            raise ValueError("Mismatched parentheses in expression.")
        output.append(op)

    return output

def evaluate_postfix(rpn_tokens: List[str]) -> float:
    """Evaluates an RPN token list in O(n) time using an operand stack."""
    stack: List[float] = []
    for token in rpn_tokens:
        if token.isnumeric() or (token.startswith('-') and token[1:].isnumeric()):
            stack.append(float(token))
        else:
            if len(stack) < 2:
                raise ValueError("Malformed RPN expression.")
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(a / b)
            elif token == '^': stack.append(a ** b)
    if len(stack) != 1:
        raise ValueError("Invalid RPN evaluation: excess operands.")
    return stack[0]

1. LIFO Discipline: Stacks enforce restricted access where all operations occur in $O(1)$ time at the TOP boundary.
2. Array vs. Linked List: Contiguous dynamic arrays achieve superior CPU cache locality with amortized $O(1)$ push; linked lists guarantee strict $O(1)$ worst-case push with pointer overhead.
3. Execution Call Stack: The CPU utilizes an internal stack to manage activation records, return pointers, and local scoping during function execution.
4. Parsing Foundations: Stacks are the core computational engine driving syntax tree generation, delimiter balancing, and Reverse Polish Notation (RPN) compilers via the Shunting-Yard algorithm.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 10: Elementary Data Structures. MIT Press.
2. Dijkstra, E. W. (1961). Making a Translator for ALGOL 60. ALGOL Bulletin, 10, 10-11.
3. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.), Chapter 4: Syntax Analysis. Addison-Wesley.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3: Bags, Queues, and Stacks. Addison-Wesley.