Stacks

A stack is a Last-In, First-Out (LIFO) data structure. The last element added is the first one removed — like a stack of plates.

Operations

| Operation | Description | Time | |---|---|---| | push(x) | Add x to the top | O(1) | | pop() | Remove and return the top element | O(1) | | peek() / top() | Return the top element without removing | O(1) | | is_empty() | Check if the stack is empty | O(1) | | size() | Number of elements | O(1) |

Implementations

Array-Based

Use a dynamic array with a top pointer.

STRUCTURE Stack
    data : dynamic array

FUNCTION NEW_STACK()
    RETURN new Stack with empty data

PROCEDURE PUSH(stack, val)
    APPEND val TO stack.data

FUNCTION POP(stack)
    RETURN REMOVE_LAST(stack.data)  // returns None if empty

FUNCTION PEEK(stack)
    RETURN LAST(stack.data)  // returns None if empty

FUNCTION IS_EMPTY(stack)
    RETURN LENGTH(stack.data) = 0

FUNCTION SIZE(stack)
    RETURN LENGTH(stack.data)

Advantages: Cache-friendly. No pointer overhead. Amortized O(1) push. Disadvantages: Occasional O(n) resize on push (amortized O(1)).

Linked-List-Based

Push/pop at the head of a singly linked list.

Advantages: Worst-case O(1) push/pop (no resize). Easy to implement. Disadvantages: Pointer overhead. Cache-unfriendly. More allocations.

In practice, array-based is almost always preferred due to cache performance.

Min/Max Stack

A stack that supports O(1) get_min() (or get_max()).

Approach 1: Auxiliary Stack

Maintain a second stack tracking the minimum at each level.

STRUCTURE MinStack
    data : dynamic array
    mins : dynamic array  // tracks minimum at each level

PROCEDURE PUSH(stack, val)
    APPEND val TO stack.data
    IF stack.mins is empty THEN
        new_min ← val
    ELSE
        new_min ← MIN(val, LAST(stack.mins))
    APPEND new_min TO stack.mins

FUNCTION POP(stack)
    REMOVE_LAST(stack.mins)
    RETURN REMOVE_LAST(stack.data)

FUNCTION GET_MIN(stack)
    RETURN LAST(stack.mins)

Approach 2: Store Differences

Store val - current_min instead of val. When the stored value is negative, the actual value was a new minimum. Space: O(1) extra (just one min variable).

Monotonic Stack

A stack where elements are maintained in monotonically increasing (or decreasing) order.

Algorithm

When pushing x:

1. While the stack is non-empty and top ≤ x (for increasing): pop.
2. Push x.

Each element is pushed and popped at most once → O(n) total for n operations.

Applications

Next Greater Element: For each element in an array, find the first element to its right that is greater.

FUNCTION NEXT_GREATER(arr)
    n ← LENGTH(arr)
    result ← array of n values, all set to -1
    stack ← empty stack  // stores indices

    FOR i ← 0 TO n - 1 DO
        WHILE stack is not empty AND arr[TOP(stack)] < arr[i] DO
            idx ← POP(stack)
            result[idx] ← arr[i]
        PUSH(stack, i)
    RETURN result

Largest Rectangle in Histogram: Find the largest rectangular area in a histogram. Classic monotonic stack problem. O(n).

Stock Span Problem: For each day, how many consecutive previous days had price ≤ today's price.

Trapping Rain Water: Can be solved with monotonic stack (or two-pointer approach).

Applications of Stacks

Expression Evaluation

Infix to Postfix (Shunting-Yard Algorithm):

Dijkstra's algorithm for converting infix expressions (A + B * C) to postfix (A B C * +).

Uses an operator stack. Respects precedence and associativity.

Postfix Evaluation:

Expression: 3 4 + 2 *
Stack trace:
  Push 3: [3]
  Push 4: [3, 4]
  +: Pop 4 and 3, push 7: [7]
  Push 2: [7, 2]
  *: Pop 2 and 7, push 14: [14]
Result: 14

Balanced Parentheses

Check if a string of brackets is properly nested:

FUNCTION IS_BALANCED(s)
    stack ← empty stack
    FOR EACH character c IN s DO
        IF c IN {'(', '[', '{'} THEN
            PUSH(stack, c)
        ELSE IF c = ')' THEN
            IF POP(stack) ≠ '(' THEN RETURN false
        ELSE IF c = ']' THEN
            IF POP(stack) ≠ '[' THEN RETURN false
        ELSE IF c = '}' THEN
            IF POP(stack) ≠ '{' THEN RETURN false
    RETURN IS_EMPTY(stack)

Function Call Stack

The program's call stack is the most important use of a stack:

main() → calls foo() → calls bar()

Stack:
  [bar's frame]  ← SP (stack pointer)
  [foo's frame]
  [main's frame]

Each stack frame contains: return address, saved registers, local variables, function arguments.

Stack overflow: When recursion goes too deep, the stack exceeds its allocated size. Causes a segmentation fault or stack overflow error.

Undo Mechanism

Each action is pushed onto a stack. Undo = pop. Redo uses a second stack.

Actions:   [type 'h'] [type 'e'] [type 'l'] [delete]
Undo:      Pop [delete] → restore 'l'

Browser History

Back = pop from history stack, push current page to forward stack. Forward = pop from forward stack, push to history stack.

DFS (Depth-First Search)

Recursive DFS uses the call stack. Iterative DFS uses an explicit stack:

FUNCTION DFS_ITERATIVE(graph, start)
    visited ← array of LENGTH(graph) values, all set to false
    stack ← empty stack
    PUSH(stack, start)

    WHILE stack is not empty DO
        node ← POP(stack)
        IF visited[node] THEN CONTINUE
        visited[node] ← true
        FOR EACH neighbor IN graph[node] DO
            IF NOT visited[neighbor] THEN
                PUSH(stack, neighbor)
    RETURN visited

Syntax Parsing

Compilers use stacks for parsing (shift-reduce parsing, recursive descent via call stack).

Two-Stack Queue

Implement a queue using two stacks:

• Push stack: Push new elements here.
• Pop stack: Pop from here. If empty, reverse the push stack into it.

Amortized O(1) per operation (each element is moved at most once between stacks).

Applications in CS

• Compiler: Expression parsing, syntax analysis (shift-reduce), scope management.
• Operating systems: Call stack management, interrupt handling (save state on stack).
• Memory management: Stack-based allocation (alloca). Stack frames for function calls.
• Algorithms: DFS, topological sort, strongly connected components, backtracking.
• Text editors: Undo/redo history.
• Virtual machines: Stack-based VMs (JVM, Python bytecode, WebAssembly). Operand stacks.
• Mathematics: Expression evaluation, reverse Polish notation, parenthesis matching.