Core Data Structures

Stacks & Queues

A stack is last-in-first-out (LIFO); a queue is first-in-first-out (FIFO). Both are O(1)-per-operation abstract data types with array- or linked-backed implementations — and a Deque (double-ended queue) does the job of both at once.

Stack: push/pop/peek at one end only — think call stack, undo history, matching-brackets validation
Queue: enqueue at the back, dequeue from the front — think task scheduling, BFS (Graph Traversal Bfs Dfs)
A circular-array Deque (Java's ArrayDeque) supports O(1) amortized push/pop/peek at both ends and is the right default for both roles
Recursion implicitly uses the call stack; converting recursion to an explicit stack is how you avoid StackOverflowError on deep inputs
Never use java.util.Stack in new Java code — it extends Vector and is legacy-synchronized; use ArrayDeque as a stack instead

Balanced-brackets validation — the canonical stack use

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();   // ArrayDeque used as a stack
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();
}

ADT operations and their ArrayDeque method names
Role	Add	Remove	Peek
Stack (LIFO)	`push` (= `addFirst`)	`pop` (= `removeFirst`)	`peek` (= `peekFirst`)
Queue (FIFO)	`offer`/`add` (= `addLast`)	`poll`/`remove` (= `removeFirst`)	`peek` (= `peekFirst`)

Every recursive algorithm implicitly maintains a stack — the JVM call stack, one frame per pending call. Converting a recursive traversal to an explicit iterative one with a Deque<> as the stack is the standard technique for avoiding StackOverflowError on deep or adversarial input (a linked list of 100,000 nodes recursed over will blow the default stack; a while loop with an explicit Deque will not, because the heap — not the fixed-size call stack — bounds it).

Recursive vs. explicit-stack depth-first traversal

// Recursive: elegant, but O(depth) call-stack frames — risks StackOverflowError
static void dfsRecursive(Node n) {
    if (n == null) return;
    visit(n);
    for (Node child : n.children) dfsRecursive(child);
}

// Explicit stack: identical traversal order, heap-bounded instead of stack-bounded
static void dfsIterative(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        if (n == null) continue;
        visit(n);
        for (int i = n.children.size() - 1; i >= 0; i--) stack.push(n.children.get(i));
    }
}