Chapter 8 Stack and Queue

This chapter focuses on stack- and queue-driven techniques. Many of these problems can be solved using explicit stacks, monotonic stacks, or queue-based sweeps to efficiently process streaming data.

8.0.1 Stack Fundamentals

A stack is a Last-In-First-Out (LIFO) data structure that supports two primary operations: - Push: Add element to top - \(O(1)\) - Pop: Remove element from top - \(O(1)\) - Peek: View top element without removing - \(O(1)\)

Java Implementation:

Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.peek();  // Returns 1
int removed = stack.pop();  // Returns and removes 1
boolean empty = stack.isEmpty();

When to Use Stacks:

  • Problems involving nested structures (parentheses, brackets)

  • Backtracking and undo operations

  • Depth-first exploration patterns

  • Processing data with most recent first priority

8.0.2 Monotonic Stack Pattern

A monotonic stack maintains elements in either strictly increasing or decreasing order. This pattern is extremely powerful for finding next greater/smaller element problems.

8.0.2.1 Monotonic Decreasing Stack (Find Next Greater)

A stack where elements are in descending order from bottom to top helps find the next greater element to the right.

Core Concept:

  • When a new element is larger than stack top, we’ve found the “next greater” for all smaller elements
  • Pop smaller elements and record their next greater
  • Push current element

Template:

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);

    Stack<Integer> stack = new Stack<>();  // Stores indices

    for (int i = 0; i < n; i++) {
        // Pop smaller elements - current is their next greater
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }

        stack.push(i);
    }

    return result;
}

Example: nums = [2, 1, 2, 4, 3]

i=0: stack=[0]           // Push 2
i=1: stack=[0,1]         // Push 1 (smaller than 2)
i=2: Pop 1, result[1]=2  // 2 is next greater for 1
     stack=[0,2]         // Push 2
i=3: Pop 2, result[2]=4  // 4 is next greater for 2
     Pop 0, result[0]=4  // 4 is next greater for original 2
     stack=[3]           // Push 4
i=4: stack=[3,4]         // Push 3

Result: [4, 2, 4, -1, -1]

8.0.2.2 Monotonic Increasing Stack (Find Next Smaller)

A stack where elements are in ascending order helps find the next smaller element.

Template:

public int[] nextSmallerElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);

    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        // Pop greater elements - current is their next smaller
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }

        stack.push(i);
    }

    return result;
}

8.0.2.3 Monotonic Stack Variations

Variant Stack Order What to Find When to Pop
Decreasing Top \(\to\) Bottom: Decreasing Next Greater Element nums[i] > stack.top()
Increasing Top \(\to\) Bottom: Increasing Next Smaller Element nums[i] < stack.top()
Previous Greater Process right-to-left Previous Greater Same as next greater, reversed
Previous Smaller Process right-to-left Previous Smaller Same as next smaller, reversed

Applications:

  • Next Greater Element problems
  • Daily Temperatures - Classic monotonic decreasing stack
  • Largest Rectangle in Histogram (next smaller on both sides)
  • Trapping Rain Water (height boundaries)
  • Stock Span Problem (consecutive smaller days)
  • Car Fleet - Monotonic stack for time calculations

Time Complexity: \(O(n)\) - Each element pushed and popped once Space Complexity: \(O(n)\) - Stack storage

8.0.3 Parentheses and Bracket Matching

Stacks are the canonical solution for validating nested structures like parentheses, brackets, and tags.

Pattern:

  1. Push opening symbols onto stack
  2. When closing symbol appears, check if it matches stack top
  3. Stack should be empty at the end for valid expression

Template for Balanced Parentheses:

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        // Opening brackets - push
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        }
        // Closing brackets - check match
        else {
            if (stack.isEmpty()) return false;

            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }

    return stack.isEmpty();
}

Advanced Pattern - Longest Valid Parentheses:

For finding the longest valid substring, use stack to track indices instead of characters.

Approach:

  • Push index when encountering (
  • Pop when encountering )
  • If stack becomes empty, push current index as new base
  • Otherwise, calculate length: current index - stack.peek()

Related Problems:

Time Complexity: \(O(n)\) Space Complexity: \(O(n)\)

8.0.4 Stack-Based State Tracking

Stacks excel at maintaining contextual state during sequential processing.

Pattern: Min/Max Stack

Track minimum or maximum alongside normal stack operations in \(O(1)\) time.

Approach 1: Parallel Min Stack

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        // Push current min
        int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(currentMin);
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Approach 2: Single Stack with Pairs

class MinStack {
    Stack<int[]> stack;  // [value, currentMin]

    public void push(int val) {
        int currentMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, currentMin});
    }

    public int getMin() {
        return stack.peek()[1];
    }
}

Related Problems:

  • Min Stack - Track minimum in \(O(1)\)
  • Max Stack - Same pattern for maximum

Time Complexity: \(O(1)\) for all operations Space Complexity: \(O(n)\)

8.0.5 Queue Fundamentals

A queue is a First-In-First-Out (FIFO) data structure supporting: - Offer/Add: Add element to rear - \(O(1)\) - Poll/Remove: Remove element from front - \(O(1)\) - Peek: View front element - \(O(1)\)

Java Implementation:

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
int front = queue.peek();  // Returns 1
int removed = queue.poll();  // Returns and removes 1
boolean empty = queue.isEmpty();

When to Use Queues:

  • Breadth-first exploration patterns (BFS)

  • Level-order processing (trees, graphs)

  • Task scheduling and time-based simulations

  • Processing data with first-come-first-served order

8.0.6 Implementing Queue Using Stacks

A classic problem demonstrating stack/queue relationships.

Approach 1: Two Stacks (Amortized O(1))

Use two stacks to simulate queue behavior: - inStack: For enqueue operations - outStack: For dequeue operations

Key Insight: Transfer elements from inStack to outStack only when outStack is empty.

class MyQueue {
    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);  // O(1)
    }

    public int pop() {
        moveIfNeeded();
        return outStack.pop();  // Amortized O(1)
    }

    public int peek() {
        moveIfNeeded();
        return outStack.peek();
    }

    private void moveIfNeeded() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

Why Amortized O(1)?

  • Each element is moved from inStack to outStack exactly once

  • Over \(n\) operations, total moves \(\le n\)

  • Average per operation: \(O(1)\)

Related Problems:

Time Complexity:

  • Push: \(O(1)\)
  • Pop/Peek: Amortized \(O(1)\), worst-case \(O(n)\) Space Complexity: \(O(n)\)

8.0.7 Queue-Based Simulation

Queues naturally model time-based simulations and task scheduling problems.

Pattern:

  1. Process events in chronological order
  2. Use queue to maintain pending tasks/events
  3. Simulate time progression step-by-step

Common Applications:

  • Task scheduling with cooldowns

  • Time-based resource allocation

  • Process simulation

Example Pattern - Task Scheduling with Cooldown:

public int taskScheduling(char[] tasks, int cooldown) {
    // Count task frequencies
    Map<Character, Integer> freq = new HashMap<>();
    for (char task : tasks) {
        freq.put(task, freq.getOrDefault(task, 0) + 1);
    }

    // Process in rounds
    int time = 0;
    while (!freq.isEmpty()) {
        List<Character> toRemove = new ArrayList<>();

        // Execute up to (cooldown + 1) tasks
        for (int i = 0; i <= cooldown && !freq.isEmpty(); i++) {
            char task = getMaxFreqTask(freq);
            freq.put(task, freq.get(task) - 1);
            if (freq.get(task) == 0) {
                toRemove.add(task);
            }
            time++;
        }

        // Remove completed tasks
        for (char task : toRemove) {
            freq.remove(task);
        }

        // Add idle time if needed
        if (!freq.isEmpty() && executedThisRound < cooldown + 1) {
            time += (cooldown + 1 - executedThisRound);
        }
    }

    return time;
}

Related Problems:

  • Task Scheduler - CPU scheduling with cooldown
  • Simulation problems requiring time-based processing

8.0.8 Stack vs Queue Decision Guide

Consideration Use Stack Use Queue
Processing Order Most recent first (LIFO) Oldest first (FIFO)
Algorithm Pattern DFS, Backtracking BFS, Level Order
Structure Type Nested (parentheses) Sequential (tasks)
State Management Undo/Redo, History Task Queue, Buffer
Monotonic Problems Next Greater/Smaller -
Example Use Cases Expression evaluation, Function calls, Undo operations BFS traversal, Task scheduling, Message queue

8.0.9 Common Stack/Queue Patterns Summary

Pattern Data Structure Use Case Time Space
Monotonic Stack Stack (Decreasing/Increasing) Next greater/smaller element \(O(n)\) \(O(n)\)
Parentheses Matching Stack Validate nested structures \(O(n)\) \(O(n)\)
Min/Max Stack Stack + Auxiliary Stack Track extrema in \(O(1)\) \(O(1)\) \(O(n)\)
Queue using Stacks Two Stacks Implement queue behavior Amortized \(O(1)\) \(O(n)\)
Task Simulation Queue Time-based processing \(O(n)\) \(O(n)\)
BFS Traversal Queue Level-order exploration \(O(V + E)\) \(O(V)\)

8.0.10 Problem-Solving Checklist

When approaching stack/queue problems:

  1. ✅ Identify the pattern:
    • Need next greater/smaller? → Monotonic stack
    • Nested structure validation? → Stack with matching
    • Level-order or BFS? → Queue
    • State tracking (min/max)? → Auxiliary stack/queue
    • Time-based simulation? → Queue
  2. ✅ Choose the right variant:
    • Monotonic stack: Decreasing (next greater) vs Increasing (next smaller)
    • Stack: Store indices vs values vs pairs
    • Queue: Simple queue vs priority queue vs deque
  3. ✅ Handle edge cases:
    • Empty stack/queue before pop/peek
    • All elements in increasing/decreasing order (monotonic stack)
    • Single element
    • Duplicate values
  4. ✅ Optimize:
    • Store indices instead of values when needed
    • Use monotonic stack to reduce \(O(n^2)\) to \(O(n)\)
    • Consider amortized analysis for two-stack queue