Skip to content

Stacks & Queues

Stack — LIFO (Last In, First Out). Push/pop from top. Use for: expression evaluation, backtracking, DFS, matching parentheses. Queue — FIFO (First In, First Out). Enqueue at rear, dequeue from front. Use for: BFS, scheduling, buffering. Java: Stack/Deque for stack, Queue/LinkedList/ArrayDeque for queue.

Key Concepts

Deep Dive: Stack Applications

Valid Parentheses: 

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

Min Stack (O(1) getMin): 

class MinStack {
    Deque<int[]> stack = new ArrayDeque<>();  // [value, currentMin]

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

Monotonic Stack (Next Greater Element): 

public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // indices
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

Deep Dive: Queue Applications

BFS (Level Order Traversal): 

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Priority Queue (Min/Max Heap): 

// Min heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Deep Dive: Deque (Double-Ended Queue)

ArrayDeque is faster than Stack and LinkedList for both stack and queue operations. 

Deque<Integer> deque = new ArrayDeque<>();
// As stack
deque.push(1); deque.pop();
// As queue
deque.offer(1); deque.poll();
// As deque
deque.offerFirst(1); deque.offerLast(2);
deque.pollFirst(); deque.pollLast();

Common Interview Questions
  • Valid Parentheses
  • Min Stack
  • Implement Queue using Stacks
  • Implement Stack using Queues
  • Next Greater Element (Monotonic Stack)
  • Daily Temperatures
  • Evaluate Reverse Polish Notation
  • Sliding Window Maximum (Monotonic Deque)