Stacks

Introduction

Stack is abstract data structure enforcing Last-In-First-Out (LIFO) access. Last element pushed is first popped. Real-world analogy: stack of plates (add to top, remove from top). Applications: expression evaluation, DFS, undo functionality, function call stack.

Restricted access: can only interact with top element. Simpler than general lists, enables efficient implementations, natural for specific problems. Fundamental building block in compilers (expression parsing), operating systems (call stacks), algorithms (backtracking).

Implementation: array-based (fixed/dynamic size) or linked list. Array: better cache, simpler. Linked list: unbounded size, allocation on demand. Choice depends on expected size and performance requirements.

"Stacks are elegant in their simplicity and powerful in their applications. LIFO discipline enables solutions to problems that seem intractable without it." -- Algorithm design principles

LIFO Principle and Stack Properties

LIFO Behavior

Last element pushed first to pop. Sequence: push 1, push 2, push 3. Pop order: 3, 2, 1. Reversing sequence.

Stack visualization (top on right):
Push 1: [1]
Push 2: [1, 2]
Push 3: [1, 2, 3] ← top
Pop: [1, 2], removed 3
Pop: [1], removed 2
Pop: [], removed 1

Properties

• Access restricted: Only top element accessible
• Insertion/Deletion: Both at top (single location)
• Order preservation: LIFO order maintained exactly
• No random access: Can't access middle elements

Empty and Full States

Empty: no elements. Operations on empty: pop() raises error, peek() raises error. Full (fixed-size): no more space. Push to full raises error. Resizing (dynamic) expands automatically.

Stack Interface: Push, Pop, Peek

Core Operations

Error Handling

Pop/peek on empty: raise exception (underflow). Push on full (fixed-size): raise exception (overflow). Modern stacks dynamic (no overflow). Defensive: check is_empty() before pop().

Safe popping:
if not stack.is_empty():
 value = stack.pop()
else:
 print("Stack empty, cannot pop")

Array-Based Implementation

Structure

class Stack:
 def __init__(self, capacity):
 self.items = [None] * capacity
 self.top = -1 # Index of top element, -1 means empty

 def push(self, value):
 if self.top == len(self.items) - 1:
 # Resize: double capacity
 self.items.extend([None] * len(self.items))
 self.top += 1
 self.items[self.top] = value

 def pop(self):
 if self.top == -1:
 raise IndexError("Stack underflow")
 value = self.items[self.top]
 self.items[self.top] = None # Clear reference
 self.top -= 1
 return value

 def peek(self):
 if self.top == -1:
 raise IndexError("Stack empty")
 return self.items[self.top]

 def is_empty(self):
 return self.top == -1

 def size(self):
 return self.top + 1

Analysis

Push: O(1) amortized (occasional O(n) resize). Pop, peek: O(1). Space: O(n) for n elements (plus some capacity overhead). Array-based simpler, faster than linked list (better cache).

Dynamic Resizing

When full, allocate array 2x size. Copy elements, update top pointer. Amortized O(1) per push (resizing rare). Python lists, Java ArrayLists implement this.

Linked List Implementation

Structure

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

class Stack:
 def __init__(self):
 self.top = None # Head of linked list

 def push(self, value):
 new_node = Node(value)
 new_node.next = self.top
 self.top = new_node

 def pop(self):
 if self.top is None:
 raise IndexError("Stack underflow")
 value = self.top.value
 self.top = self.top.next
 return value

 def peek(self):
 if self.top is None:
 raise IndexError("Stack empty")
 return self.top.value

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

Analysis

Push, pop, peek: O(1) (no traversal, operate at head). Space: O(n) plus pointer overhead. No resizing overhead, unbounded growth. Slower than array in practice (cache, pointer dereferencing).

Comparison

Array: faster (cache locality), simpler code. Linked list: no resizing, unbounded. Modern preference: array-based (dynamic arrays available in most languages).

Time and Space Complexity

Practical Performance

Array-based faster: cache locality. Linked list: pointer traversal overhead. For small stacks, array negligible difference. For large or frequent operations, array significantly faster.

Applications: Expression Parsing

Balanced Parentheses

Check if expression balanced: push '(' on open, pop and match on close. Final: stack must be empty.

def is_balanced(expression):
 stack = Stack()
 pairs = {'(': ')', '[': ']', '{': '}'}
 for char in expression:
 if char in pairs:
 stack.push(char)
 elif char in pairs.values():
 if stack.is_empty() or pairs[stack.pop()] != char:
 return False
 return stack.is_empty()

Infix to Postfix Conversion

Convert "3 + 4 * 2 / (1 - 5)" to postfix "3 4 2 * 1 5 - / +". Stack precedence tracking. Shunting-yard algorithm uses stack for operators.

Expression Evaluation

Evaluate postfix: push operands, pop two and apply operator when encountered. "3 4 + 5 *" = (3+4)*5 = 35. Stack naturally evaluates postfix.

def evaluate_postfix(tokens):
 stack = Stack()
 for token in tokens:
 if token in {'+', '-', '*', '/'}:
 b = stack.pop()
 a = stack.pop()
 if token == '+': result = a + b
 elif token == '-': result = a - b
 elif token == '*': result = a * b
 elif token == '/': result = a // b
 stack.push(result)
 else:
 stack.push(int(token))
 return stack.pop()

Depth-First Search (DFS)

Iterative DFS Using Stack

Push start vertex, pop and visit, push unvisited neighbors. Stack naturally implements DFS (vs. BFS uses queue).

def dfs(graph, start):
 visited = set()
 stack = Stack()
 stack.push(start)
 while not stack.is_empty():
 vertex = stack.pop()
 if vertex not in visited:
 print(vertex)
 visited.add(vertex)
 for neighbor in graph[vertex]:
 if neighbor not in visited:
 stack.push(neighbor)

Graph Traversal Applications

Topological sort, strongly connected components, cycle detection. All naturally use stacks (or recursion, which uses call stack).

Function Calls and Recursion

Call Stack

Every function call pushed as frame (local variables, return address). Return pops frame, resumes caller. Recursion: nested frames. Deep recursion: stack overflow (too many frames).

Call stack example (factorial):
factorial(4):
 Call factorial(3):
 Call factorial(2):
 Call factorial(1):
 Base case, return 1
 Return 2*1 = 2
 Return 3*2 = 6
 Return 4*6 = 24

Stack during deepest: [main, fact(4), fact(3), fact(2), fact(1)]

Recursion Limits

Python: sys.setrecursionlimit() (default ~1000). Stack overflow if exceed. Iterative solutions (using explicit stack) avoid recursion limit.

Converting Recursion to Iteration

Maintain explicit stack: simulate function calls. More code but no recursion depth limit. Example: tree traversal with explicit stack mimics recursive traversal.

Backtracking and Undo Operations

Undo Functionality

Each action pushed as state. Undo: pop previous state, restore. Stack naturally models undo (LIFO).

Backtracking Algorithms

N-Queens, Sudoku solver, maze solving. Try move, push state. If invalid, pop and backtrack. Stack maintains solution path.

def solve_maze_backtrack():
 stack = Stack()
 stack.push(start_position)
 while not stack.is_empty():
 pos = stack.pop()
 if pos == goal:
 return True
 for neighbor in neighbors(pos):
 if is_valid(neighbor):
 stack.push(neighbor)
 return False

Advanced Stack Problems

Largest Rectangle in Histogram

Given histogram heights, find max rectangle area. Stack stores indices of increasing heights. Popping when larger height encountered enables O(n) solution.

Stock Span Problem

For each price, find consecutive preceding days with lower price. Stack of (price, span) pairs. O(n) vs. naive O(n^2).

Trapping Rain Water

Given height array, compute water trapped between bars. Stack or two-pass approach. Uses monotonic stack (stack maintains decreasing height).

Min/Max Stack

Stack supporting push, pop, find-min, find-max all O(1). Maintain parallel min/max stacks. Each element paired with min/max so far.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, 3rd edition, 2009.
• Knuth, D. E. "The Art of Computer Programming, Volume 1: Fundamental Algorithms." Addison-Wesley, 3rd edition, 1997.
• Sedgewick, R., and Wayne, K. "Algorithms, Part I." Addison-Wesley, 4th edition, 2011.
• Skiena, S. S. "The Algorithm Design Manual." Springer, 2nd edition, 2008.
• Lafore, R. "Data Structures and Algorithms in Java." Sams Publishing, 2nd edition, 2002.