栈与队列

栈：后进先出（LIFO）

栈是一种受限的线性数据结构，只允许在同一端（栈顶）进行插入和删除操作。

压栈（push）：    弹栈（pop）：
     +---+              +---+
     | 5 | ← top  top → | 5 |  → 弹出 5
     +---+              +---+
     | 3 |              | 3 |
     +---+              +---+
     | 1 |              | 1 |
     +---+              +---+

Java 中推荐用 Deque 接口（ArrayDeque 实现）代替 Stack 类：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);         // 压栈
stack.push(3);
stack.push(5);
int top = stack.peek(); // 查看栈顶，不弹出：5
int val = stack.pop();  // 弹出：5
boolean empty = stack.isEmpty();

栈的典型应用：括号匹配

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();  // 栈空说明全部匹配
}

栈的典型应用：函数调用栈

程序的函数调用正是用栈来实现的：调用新函数时，当前上下文压栈；函数返回时，弹出恢复上下文。递归本质上就是依赖调用栈，所以"递归转迭代"通常就是"用显式栈模拟递归调用"。

单调栈

单调栈是处理"下一个更大/更小元素"问题的神器，将暴力 O(n²) 优化至 O(n)。

核心思路：维持栈从底到顶单调递减/递增，当新元素破坏单调性时，弹出栈顶并记录结果。

// 下一个更大元素：对每个元素，找到其右侧第一个比它大的元素
// 时间 O(n)，空间 O(n)
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);  // 默认没有更大元素
    Deque<Integer> stack = new ArrayDeque<>();  // 存索引

    for (int i = 0; i < n; i++) {
        // 栈顶元素比当前元素小，当前元素就是栈顶的"下一个更大元素"
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

nums = [2, 1, 5, 3, 6]
i=0: push 0, stack=[0]
i=1: nums[0]=2 > nums[1]=1，不弹；push 1, stack=[0,1]
i=2: nums[1]=1 < 5，弹1，result[1]=5；nums[0]=2 < 5，弹0，result[0]=5；push 2
i=3: nums[2]=5 > 3，不弹；push 3，stack=[2,3]
i=4: nums[3]=3 < 6，弹3，result[3]=6；nums[2]=5 < 6，弹2，result[2]=6；push 4
结果：[5, 5, 6, 6, -1]

记忆口诀：从左到右扫，栈存"还没找到答案的候选人"，新来的比栈顶大时，栈顶终于找到了答案（新来的就是它的下一个更大值），弹出结算。

队列：先进先出（FIFO）

队列只允许在尾部插入（入队）、从头部取出（出队）。

Queue<Integer> queue = new LinkedList<>();
// 或者：Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);        // 入队（推荐用 offer 而非 add，失败时返回 false 而非抛异常）
queue.offer(2);
int head = queue.peek();  // 查看队头：1
int val = queue.poll();   // 出队：1

队列的典型应用：BFS

广度优先搜索（BFS）用队列实现，保证按层扩展：

void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();  // 当前层的节点数
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 处理当前节点
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        // 一层处理完毕
    }
}

优先队列（堆）

优先队列不是普通的 FIFO 队列，而是每次取出优先级最高的元素。Java 中的 PriorityQueue 默认是小顶堆（最小元素优先）。

// 小顶堆：每次 poll() 弹出最小元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll();  // 返回 1（最小）

// 大顶堆：传入反转比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 或：new PriorityQueue<>((a, b) -> b - a);

典型应用：Top K 问题

找数组中最大的 K 个元素：维护大小为 K 的小顶堆。

// 找前 K 个最大元素，时间 O(n log k)，空间 O(k)
int[] topKFrequent(int[] nums, int k) {
    // 统计频次
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);

    // 小顶堆，按频次排序，保持堆大小为 k
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();  // 弹出频次最小的
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = heap.poll()[0];
    return result;
}

为什么用小顶堆而不是大顶堆？
小顶堆的堆顶是堆中最小的。维护大小为 K 的小顶堆遍历所有元素时，若新元素比堆顶大，就换掉堆顶（弹出最小的，加入新的更大的），这样最终堆里留下的就是最大的 K 个——用"最小"哨兵来淘汰更小的候选者。

双端队列（Deque）

Deque（Double-Ended Queue）支持两端的插入和删除，可以模拟栈和队列：

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);   // 头部入队
deque.offerLast(2);    // 尾部入队
deque.pollFirst();     // 头部出队
deque.pollLast();      // 尾部出队

典型应用：滑动窗口最大值

用单调双端队列（从大到小），维护窗口内的最大值。

// 时间 O(n)，空间 O(k)
int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // 存索引，保持队头最大

    for (int i = 0; i < n; i++) {
        // 移除不在窗口内的队头
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // 维护单调递减：比新元素小的从队尾移除
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        // 窗口填满后，队头即为最大值
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

用栈实现队列 / 用队列实现栈

这是经典架构问题，考查对两种数据结构特性的理解。

用两个栈实现队列

class MyQueue {
    Deque<Integer> inStack = new ArrayDeque<>();   // 入队用
    Deque<Integer> outStack = new ArrayDeque<>();  // 出队用

    void push(int x) { inStack.push(x); }

    int pop() {
        if (outStack.isEmpty()) {
            // 倒置：把 inStack 全部转移到 outStack（顺序反转，变为 FIFO）
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.pop();
    }

    int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.peek();
    }

    boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); }
}

每个元素最多从 inStack 移动到 outStack 一次，所以 pop/peek 的摊销时间复杂度是 O(1)。

小结