3.1 Stack ADT and Applications

Stacks are one of the most fundamental data structures you'll encounter. A stack enforces a simple rule: the last element you add is the first one you remove. This Last-In-First-Out (LIFO) behavior shows up everywhere, from how your computer manages function calls to how the undo button works in a text editor.

Every primary stack operation runs in $O(1)$ time, which makes stacks extremely efficient when you only need access to the most recently added element.

Stack ADT Fundamentals

Stack Abstract Data Type

An abstract data type (ADT) defines what operations a data structure supports without specifying how they're implemented. The Stack ADT organizes elements in LIFO order, where all insertions and deletions happen at the same end, called the top of the stack.

Think of a stack of plates: you always add a new plate on top, and you always grab the top plate first. You never pull from the middle or bottom.

The five primary operations are:

1. push(element) — Insert an element onto the top of the stack
2. pop() — Remove and return the top element
3. peek() (also called top()) — View the top element without removing it
4. isEmpty() — Return true if the stack contains no elements
5. size() — Return the number of elements currently in the stack

All five operations run in $O(1)$ time because they only interact with the top of the stack. There's no traversal involved.

LIFO Principle

The LIFO principle means the last element pushed onto the stack is the first one popped off. The element sitting at the bottom was the first one inserted and will be the last one removed.

This means a stack accesses elements in the reverse order of their insertion. That reversal property is exactly what makes stacks useful for things like:

• Pressing the back button in a web browser (you return to the most recently visited page first)
• Undo operations (the most recent action gets undone first)
• Backtracking (you retrace your most recent steps before earlier ones)

Applications of Stacks

Function call management. When a function is called, the system pushes a stack frame onto the call stack. That frame holds local variables, parameters, and the return address. When the function finishes, its frame is popped off, and execution returns to the caller. This is how recursive functions unwind: each recursive call stacks a new frame, and they resolve in reverse order.

Expression evaluation. Stacks are used to evaluate arithmetic expressions in postfix (reverse Polish) notation. Operands get pushed onto the stack; when an operator is encountered, the required operands are popped, the operation is performed, and the result is pushed back. Infix and prefix evaluation also rely on stacks to handle operator precedence. Calculators use this approach internally.

Undo/redo functionality. Text editors and design tools maintain a stack of previous actions. Each undo pops the most recent action off the stack. A separate redo stack can hold undone actions so they can be reapplied.

Backtracking algorithms. Depth-first search (DFS) uses a stack to track which nodes have been visited and which paths remain to explore. When a dead end is reached, the algorithm pops back to the most recent node with unexplored neighbors.

Syntax parsing and validation. Compilers check for balanced parentheses, brackets, and braces by pushing each opening symbol onto a stack. When a closing symbol appears, the top of the stack is popped and checked for a match. If the stack is empty at the end and every symbol matched, the expression is balanced.

Time Complexity of Stack Operations

All basic stack operations run in constant time because they only access or modify the top element, with no need to traverse the rest of the structure:

The space complexity of a stack is $O(n)$, where $n$ is the number of elements stored. The stack grows linearly as you push more elements onto it. In practice, this matters for things like deep recursion: if a recursive function calls itself thousands of times, the call stack consumes $O(n)$ memory and can overflow if $n$ is large enough.