Stack

LIFO

• A stack is Last-In, First-Out: push adds to the top, pop removes the top, peek/top reads without removing.
• java.util.Stack extends Vector — synchronized, old, and an awkward List. New code should use Deque (ArrayDeque).
• The Deque stack API: push / pop / peek (or addFirst / removeFirst / peekFirst).

import java.util.ArrayDeque;
import java.util.Deque;

public class StackBasics {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek()); // 3
        System.out.println(stack.pop());  // 3
        System.out.println(stack);        // [2, 1] (ArrayDeque toString is not a promise)
    }
}

Stack vs Deque vs Vector

When interviews want a stack

• Matching brackets, undo, DFS, next-greater-element, evaluating postfix, call-stack simulation.
• If they say “use Stack”, Deque st = new ArrayDeque<>(); is the modern answer — mention why.

Complexity and pitfalls

• ArrayDeque push/pop are amortized O(1). It grows like an array (circular buffer).
• Stack.empty() vs isEmpty() — Deque uses isEmpty(). Stack.search is 1-based from the top — rarely useful.
• pop/removeFirst on empty ArrayDeque throws NoSuchElementException. pollFirst returns null — that is why null elements are banned.
• Do not use Stack.get(i) just because Stack is a List. That is not stack thinking.

Balanced parentheses

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class Balanced {
    static boolean balanced(String s) {
        Map<Character, Character> closeToOpen = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> st = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (closeToOpen.containsValue(c)) {
                st.push(c);
            } else if (closeToOpen.containsKey(c)) {
                if (st.isEmpty() || st.pop() != closeToOpen.get(c)) return false;
            }
        }
        return st.isEmpty();
    }

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