Stacks and Queues

Stack: Last-In-First-Out (LIFO)

A stack is a linear data structure that restricts insertion and deletion to a single end, known as the "top."

Push (Insertion):      Pop (Deletion):
     +---+              +---+
     | 5 | ← top  top → | 5 |  → 5 popped
     +---+              +---+
     | 3 |              | 3 |
     +---+              +---+
     | 1 |              | 1 |
     +---+              +---+

In Java, it is recommended to use the Deque interface (with ArrayDeque implementation) instead of the legacy Stack class:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // Push element onto the stack
stack.push(3);
stack.push(5);
int top = stack.peek(); // View top element without removing: 5
int val = stack.pop();  // Remove and return top: 5
boolean empty = stack.isEmpty();

Typical Application: Parentheses Matching

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } 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(); // Empty stack indicates successful matching
}

Typical Application: Function Call Stack

Function calls in programming are implemented using a stack: when a new function is called, the current context is pushed onto the stack; when the function returns, the context is popped and restored. Recursion relies inherently on the system call stack, and "converting recursion to iteration" typically involves using an explicit stack to simulate these calls.

Monotonic Stack

A monotonic stack is a specialized technique for solving "Next Greater/Smaller Element" problems, optimizing O(n²) brute force solutions to O(n).

Core Concept: Maintain the stack in a strictly monotonic (increasing or decreasing) order. When a new element violates this order, pop elements from the stack and record the results.

// Next Greater Element: For each element, find the first larger value to its right.
// Time: O(n), Space: O(n)
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1); // Default to -1 if no greater element exists
    Deque<Integer> stack = new ArrayDeque<>(); // Store indices for result mapping

    for (int i = 0; i < n; i++) {
        // While the current element is larger than the top of the stack,
        // it serves as the "Next Greater Element" for the stack's top.
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Walkthrough:

nums = [2, 1, 5, 3, 6]
i=0: push 0, stack=[0]
i=1: nums[0]=2 > nums[1]=1, maintain; push 1, stack=[0, 1]
i=2: nums[1]=1 < 5, pop 1, result[1]=5; 
     nums[0]=2 < 5, pop 0, result[0]=5; 
     push 2, stack=[2]
i=3: nums[2]=5 > 3, maintain; push 3, stack=[2, 3]
i=4: nums[3]=3 < 6, pop 3, result[3]=6; 
     nums[2]=5 < 6, pop 2, result[2]=6; 
     push 4, stack=[4]
Result: [5, 5, 6, 6, -1]

Mnemonic: Iterate left to right; the stack holds "candidates seeking answers." When a new element arrives that is larger than the top, the candidate finally finds its answer—pop and settle.

Queue: First-In-First-Out (FIFO)

A queue allows insertion at the back ("enqueue") and removal from the front ("dequeue").

Queue<Integer> queue = new LinkedList<>();
// Alternatively: Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);         // Enqueue (offer is preferred over add as it avoids exceptions)
queue.offer(2);
int head = queue.peek(); // View front: 1
int val = queue.poll();  // Dequeue: 1

Typical Application: BFS

Breadth-First Search (BFS) is implemented using a queue to ensure expansion happens layer by layer:

void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size(); // Nodes in the current layer
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // Process node...
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        // One layer complete
    }
}

Priority Queue (Heap)

A Priority Queue does not follow FIFO. Instead, it serves elements based on their priority (natural order or custom comparator). In Java, PriorityQueue defaults to a Min-Heap.

// Min-Heap: poll() returns the smallest element
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll(); // Returns 1 (the smallest)

// Max-Heap: use a reverse comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Or: new PriorityQueue<>((a, b) -> b - a);

Typical Application: Top K Problem

Finding the K largest elements in an array: Maintain a Min-Heap of size K.

// Top K Frequent Elements: Time O(n log k), Space O(k)
int[] topKFrequent(int[] nums, int k) {
    // 1. Count frequencies
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int n : nums) freqMap.merge(n, 1, Integer::sum);

    // 2. Min-Heap ordered by frequency, capped at size k
    // If heap size exceeds k, poll the least frequent element.
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> e : freqMap.entrySet()) {
        minHeap.offer(new int[]{e.getKey(), e.getValue()});
        if (minHeap.size() > k) minHeap.poll();
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll()[0];
    return result;
}

Why a Min-Heap for Largest Elements?
The top of a Min-Heap is its smallest value. By maintaining a size of K, when a larger element arrives, we discard the current smallest via poll(). What remains in the heap are the largest candidates—using the "smallest" as a sentinel to filter candidates.

Double-Ended Queue (Deque)

A Deque supports insertion and removal at both ends, allowing it to function as either a stack or a queue:

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);  // Enqueue at head
deque.offerLast(2);   // Enqueue at tail
deque.pollFirst();    // Dequeue at head
deque.pollLast();     // Dequeue at tail

Typical Application: Sliding Window Maximum

Use a monotonic Double-Ended Queue (decreasing order) to maintain the maximum value within a window.

// Time: O(n), Space: O(k)
int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // Indices, head is always the maximum node index

    for (int i = 0; i < n; i++) {
        // 1. Remove indices that are out of the window range
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // 2. Maintain monotonic decrease: remove smaller elements from the tail
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        // 3. Record result if the first window is filled
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

Implementing Queue with Stacks / Stack with Queues

A classic architectural problem exploring the structural differences between these formats.

Queue Using Two Stacks

class MyQueue {
    Deque<Integer> inStack = new ArrayDeque<>();  // For enqueue
    Deque<Integer> outStack = new ArrayDeque<>(); // For dequeue

    void push(int x) { inStack.push(x); }

    int pop() {
        if (outStack.isEmpty()) {
            // Transfer all from inStack to outStack (reverses order to FIFO)
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.pop();
    }

    int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.peek();
    }

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

Amortized Complexity: Each element moves from inStack to outStack exactly once, resulting in an O(1) amortized time for pop and peek.

Summary