Stacks in Action: Brackets and the Next Warmer Day

Matching brackets

In { [ ( ) ] } the bracket opened last must be closed first – that's LIFO, so a stack fits perfectly. Push every opener; for a closer, the top of the stack must be its partner:

import java.util.ArrayDeque;

public class Main {
    static boolean balanced(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if (c == ')' && open != '(') return false;
                if (c == ']' && open != '[') return false;
                if (c == '}' && open != '{') return false;
            }
        }
        return stack.isEmpty();          // nothing left open
    }

    public static void main(String[] args) {
        System.out.println(balanced("{[()()]}"));
        System.out.println(balanced("([)]"));
        System.out.println(balanced("(("));
    }
}

Output

true
false
false

A stack that stays in order

For each price, what is the next bigger price to its right? Checking every later price is O(n²). Instead keep a stack of items still waiting for a bigger value. When a big value arrives, it answers everyone smaller on top of the stack:

import java.util.ArrayDeque;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] price = {4, 2, 5, 3, 1, 6};
        int[] nextBigger = new int[price.length];
        Arrays.fill(nextBigger, -1);
        ArrayDeque<Integer> waiting = new ArrayDeque<Integer>();   // indexes
        for (int i = 0; i < price.length; i++) {
            while (!waiting.isEmpty() && price[waiting.peek()] < price[i]) {
                nextBigger[waiting.pop()] = price[i];              // found their answer
            }
            waiting.push(i);
        }
        System.out.println(Arrays.toString(nextBigger));
    }
}

Output

[5, 5, 6, 6, 6, -1]

Each index is pushed once and popped at most once, so it's O(n). The stack's values always go down from bottom to top – that's why it's called a monotonic stack.

Think of it like this: People in a queue for a concert, looking for the first taller person ahead of them. A tall person arriving answers everybody shorter who's still waiting.