栈 Stack

public class ArrayStack<E> {
    private E[] data;
    private int top = -1;

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        data = (E[]) new Object[capacity];
    }

    public void push(E e) {
        if (top == data.length - 1) throw new IllegalStateException("栈满");
        data[++top] = e;
    }

    public E pop() {
        if (top == -1) throw new NoSuchElementException("栈空");
        E e = data[top];
        data[top--] = null;
        return e;
    }

    public E peek() {
        if (top == -1) throw new NoSuchElementException("栈空");
        return data[top];
    }

    public boolean isEmpty() { return top == -1; }
}

public class LinkedStack<E> {
    private Node<E> top;
    private int size = 0;

    private static class Node<E> { E val; Node<E> next; Node(E v) { val = v; } }

    public void push(E e) {
        Node<E> node = new Node<>(e);
        node.next = top;
        top = node;
        size++;
    }

    public E pop() {
        if (top == null) throw new NoSuchElementException();
        E v = top.val;
        top = top.next;
        size--;
        return v;
    }
}

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        if ("+-*/".contains(t) && t.length() == 1) {
            int b = stack.pop(), a = stack.pop();
            switch (t) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(a / b); break;
            }
        } else {
            stack.push(Integer.parseInt(t));
        }
    }
    return stack.pop();
}

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

class TextEditor {
    Deque<String> undo = new ArrayDeque<>();
    Deque<String> redo = new ArrayDeque<>();
    String text = "";

    void edit(String change) {
        undo.push(text);
        text = change;
        redo.clear();
    }

    void undo() {
        if (undo.isEmpty()) return;
        redo.push(text);
        text = undo.pop();
    }
}

// 递归版本
void dfs(Node u) {
    if (u == null) return;
    visit(u);
    dfs(u.left);
    dfs(u.right);
}

// 显式栈版本（避免栈溢出）
void dfsIterative(Node root) {
    if (root == null) return;
    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node u = stack.pop();
        visit(u);
        if (u.right != null) stack.push(u.right);
        if (u.left != null) stack.push(u.left);
    }
}

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

    public void push(int x) {
        int min = stack.isEmpty() ? x : Math.min(stack.peek()[1], x);
        stack.push(new int[]{x, min});
    }

    public void pop() { stack.pop(); }
    public int top() { return stack.peek()[0]; }
    public int getMin() { return stack.peek()[1]; }
}

class MyQueue {
    Deque<Integer> in = new ArrayDeque<>();
    Deque<Integer> out = new ArrayDeque<>();

    public void push(int x) { in.push(x); }

    public int pop() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.pop();
    }

    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }

    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}