Stack

// ── Stack basic usage: ───────────────────────────────────────────────
Stack<Integer> stack = new Stack<>();

// Push elements:
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack);     // [10, 20, 30] — bottom to top

// Peek — view top without removing:
System.out.println(stack.peek());    // 30 — top of stack
System.out.println(stack.size());    // 3 — unchanged

// Pop — remove and return top:
System.out.println(stack.pop());     // 30
System.out.println(stack.pop());     // 20
System.out.println(stack.pop());     // 10

// empty():
System.out.println(stack.empty());   // true

// pop() on empty — throws EmptyStackException:
try {
    stack.pop();
} catch (EmptyStackException e) {
    System.out.println("Stack is empty");
}

// ── The design problem — inherited List operations break abstraction: ──
Stack<String> s = new Stack<>();
s.push("bottom");
s.push("middle");
s.push("top");

// These make no sense for a stack:
s.add(1, "inserted-in-middle");  // insert at index 1 — violates LIFO!
s.remove(0);                      // remove bottom element — violates LIFO!
String arbitrary = s.get(0);      // access by index — violates LIFO!

// search() — 1-based from top:
s = new Stack<>();
s.push("a"); s.push("b"); s.push("c");
System.out.println(s.search("c"));  // 1 — top
System.out.println(s.search("b"));  // 2 — one below top
System.out.println(s.search("a"));  // 3 — bottom
System.out.println(s.search("z"));  // -1 — not found

// ── ArrayDeque as a stack — the modern replacement for Stack: ────────
Deque<Integer> stack = new ArrayDeque<>();  // declared as Deque

stack.push(10);    // addFirst — O(1)
stack.push(20);
stack.push(30);

System.out.println(stack.peek());   // 30 — view top, no removal
System.out.println(stack.pop());    // 30 — remove top
System.out.println(stack.pop());    // 20
System.out.println(stack.isEmpty());// false — 10 remains

// pop() on empty — throws NoSuchElementException (not EmptyStackException):
stack.pop(); // removes 10
try {
    stack.pop();
} catch (NoSuchElementException e) {
    System.out.println("Stack is empty");
}

// Null-safe alternative — returns null on empty:
Integer top = stack.pollFirst();  // null if empty — no exception

// ── Practical: balanced parentheses checker: ──────────────────────────
public static boolean isBalanced(String expression) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : expression.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

System.out.println(isBalanced("({[]})"));  // true
System.out.println(isBalanced("({[})"));   // false

// ── Practical: reverse a string using a stack: ───────────────────────
public static String reverse(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) stack.push(c);

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.toString();
}

System.out.println(reverse("Hello"));  // olleH

// ── Stack vs Deque — why Deque is preferred: ─────────────────────────
//
//                Stack (legacy)    Deque/ArrayDeque (modern)
// ────────────── ───────────────   ─────────────────────────
// Extends         Vector            (uses composition)
// Thread safe     Yes (slow)        No (add sync if needed)
// Exposes List?   Yes (bad design)  No (clean interface)
// Performance     Slow              Fast
// Recommended?    Legacy only       Always for new code

// ── Simulate recursion with explicit stack — DFS tree traversal: ──────
public static void dfsIterative(TreeNode root) {
    if (root == null) return;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.value);

        // Push right first so left is processed first (LIFO):
        if (node.right != null) stack.push(node.right);
        if (node.left  != null) stack.push(node.left);
    }
}

// ── Undo/Redo system: ─────────────────────────────────────────────────
public class TextEditor {
    private final StringBuilder text   = new StringBuilder();
    private final Deque<String>  undo  = new ArrayDeque<>();
    private final Deque<String>  redo  = new ArrayDeque<>();

    public void type(String chars) {
        undo.push(text.toString());   // save current state
        redo.clear();                  // typing clears redo history
        text.append(chars);
    }

    public void undo() {
        if (undo.isEmpty()) return;
        redo.push(text.toString());    // save for redo
        text.setLength(0);
        text.append(undo.pop());       // restore previous state
    }

    public void redo() {
        if (redo.isEmpty()) return;
        undo.push(text.toString());
        text.setLength(0);
        text.append(redo.pop());
    }

    public String getText() { return text.toString(); }
}

TextEditor ed = new TextEditor();
ed.type("Hello");
ed.type(" World");
System.out.println(ed.getText());  // Hello World
ed.undo();
System.out.println(ed.getText());  // Hello
ed.undo();
System.out.println(ed.getText());  // (empty)
ed.redo();
System.out.println(ed.getText());  // Hello

// ── Monotonic stack — next greater element: ──────────────────────────
public static int[] nextGreaterElement(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);               // default: -1 (no greater element)
    Deque<Integer> stack = new ArrayDeque<>();  // stack of indices

    for (int i = 0; i < n; i++) {
        // Pop indices whose elements are smaller than arr[i]:
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

int[] arr = {4, 5, 2, 10, 8};
System.out.println(Arrays.toString(nextGreaterElement(arr)));
// [5, 10, 10, -1, -1]
// 4's next greater is 5, 5's is 10, 2's is 10, 10 and 8 have none