专题 06栈与队列：先进后出与先进先出

6.1栈：后进先出的「撤销」思想

栈（Stack）的核心性质是 LIFO（Last In, First Out，后进先出）：最后压进去的元素，最先被弹出来。 生活里最像栈的是一摞盘子——你只能从顶上放、从顶上取，底下的最晚动。

为什么算法里老用栈？因为很多问题的结构本身就是「最近匹配 / 回退」：

• 括号匹配：遇到右括号，要找的是「离它最近的、还没匹配的左括号」——典型的栈顶操作；
• 撤销（Undo）：文本编辑器按 Ctrl+Z，撤销的是「最近一次」操作；
• 函数调用：程序运行时的调用栈，后调用的函数先返回；
• 深度优先搜索：递归本质就是系统帮你维护了一个栈。

Java 里怎么写栈

重点：不要用老旧的 Stack 类。它是早期 Collection 框架的边角，方法都 synchronized（线程安全但拖慢速度），而且继承了 Vector，设计上有缺陷。 Java 官方推荐用 Deque（双端队列）来当栈：

// 推荐写法：用 ArrayDeque 当栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // 入栈（= addFirst）
stack.push(2);
int top = stack.peek(); // 看栈顶但不弹出 = 2
int x = stack.pop();    // 弹出栈顶 = 2，栈里剩 1
boolean empty = stack.isEmpty();

Deque 既能当栈（push/pop/peek）又能当队列（offer/poll/peek），一个接口两种用法，本章和 专题 07 都靠它。

队列：先进先出的「排队」思想

队列（Queue）的核心是 FIFO（First In, First Out，先进先出）：最早进来的最早出去，像食堂排队，先来的先打饭。 它解决的问题结构刚好和栈相反——「按出现顺序依次处理，且处理最早发生的」：

• 层序遍历二叉树：一层一层从左到右处理，先遇到的节点先展开它的孩子；
• 广度优先搜索（BFS）：从起点一圈圈扩散，先发现的点先探索；
• 消息队列 / 任务调度：先提交的任务先执行。

Java 里队列同样用 Deque（或 LinkedList）实现，不要用 LinkedList 直接当 Queue 时混用 List 方法，保持接口纯粹更好：

// 用 ArrayDeque 当队列（推荐）
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);          // 入队（从尾进）
queue.offer(2);
int head = queue.peek(); // 看队首 = 1，不弹出
int x = queue.poll();    // 出队（从头出）= 1，剩下 2

6.2有效的括号（简单，力扣 20）

简单 核心：栈顶匹配最近左括号

题意：判断字符串里的括号是否合法配对。例："()[]{}" → true；"(]" → false；"([)]" → false。 合法意味着：每类括号左右数量相等、且嵌套/相邻顺序正确。

思路推导

暴力想：数三类括号各有多少对，相等就 true？不对——"(]" 数量也对，但顺序错。 真正要判断的是「最近没匹配的左括号，要和下一个右括号同类型」，这正是栈的活。

从左往右扫：

• 遇到左括号：压栈（记下来，等它的右括号来配）；
• 遇到右括号：它应该和「栈顶那个左括号」配对。弹出栈顶看类型对不对：
  • 栈空？说明右括号没人配，直接 false（比如一上来就是 ')'）；
  • 类型不对？比如栈顶是 '(' 却来了 ']'，false；
• 扫完：栈必须空才合法（所有左括号都配对完，没剩）。

参考代码

class Solution {
    public 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)：最坏全是左括号，栈高 n。 为什么最后要判 isEmpty()？因为 "(((" 扫完栈不空，说明左括号多出来了，不合法。

6.3最小栈（中等，力扣 155）

中等 核心：辅助栈同步保存最小值

题意：设计一个栈，除了正常的 push/pop/top，还要能在 O(1) 时间内返回当前栈里的最小值。 例：依次 push 3,2,1,4，getMin() 依次返回 3,2,1,1。

思路推导

普通栈的 pop 把元素丢了，可万一丢的正是最小值，下次 getMin 问谁去？ 所以光存数据不够，得随时知道「此刻的最小值」。

办法是用第二个栈（辅助栈）和数据栈同步进出，辅助栈里存「到当前位置为止的最小值」：

• push(x)：数据栈压 x；辅助栈压 min(x, 辅助栈栈顶)——也就是「之前的最小值和 x 取更小」；
• pop：两个栈一起弹，辅助栈弹出的正是「对应这次的最小值」，数据栈恢复后，新的栈顶就是剩余部分的最小值；
• getMin：直接看辅助栈栈顶，O(1)。

为了「辅助栈空时也能压」，空栈压入就直接压 x 当最小值。

push 3:  数据[3]    辅助[3]      min=3
push 2:  数据[3,2]  辅助[3,2]    min=2   (min(2,3)=2)
push 4:  数据[3,2,4]辅助[3,2,2]  min=2   (min(4,2)=2，辅助栈顶仍是2)
pop:     数据[3,2]  辅助[3,2]    min=2

参考代码

class MinStack {
    private Deque<Integer> stack;     // 数据栈
    private Deque<Integer> minStack;  // 辅助栈：存「当前最小值」

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);            // 更小或相等，压入新最小
        } else {
            minStack.push(minStack.peek()); // 否则复制当前最小，保持同步高度
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();                 // 同步弹出
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();         // 栈顶即当前最小
    }
}

复杂度

四个操作都是 O(1) 时间。空间 O(n)，多了一个辅助栈。 为什么辅助栈每次都压（哪怕不是新最小也压旧值）？为了让它和数据栈高度永远一致， pop 时一起弹，getMin 永远对应「此刻栈状态」的最小值，不用算。

省空间变体（了解即可）

如果链表很长、重复值很多，同步压法会存大量重复的「旧最小」。优化版：只有 val ≤ 当前最小才压辅助栈， 并且 pop 时判断「弹出的数据是不是正好等于辅助栈顶」——是才把辅助栈也弹一下。这里用 ≤ 而不是 < 很关键： 若连续压两个相同的最小值（如 push 2, push 2），必须用 ≤ 让第二个 2 也进辅助栈， 否则第一次 pop 2 时辅助栈顶也被弹掉，第二次 pop 2 时辅助栈就已经丢了「还有一个 2 是最小」的信息。 这个边界是省空间写法最容易翻车的地方，所以面试首推同步压法，稳。

6.4用栈实现队列（简单，力扣 232）

简单 核心：双栈互相倒

题意：只给你两个栈，实现队列的 push/pop/peek/empty。 栈是后进先出，队是先进先出，怎么用反的模拟正的？

思路推导

一个栈不够——栈顶是「最后进的」，可队列要出「最先进的」。妙招是两个栈：

• in 栈：push 时直接压进它（新元素都在 in 顶）；
• out 栈：要 pop/peek 时，如果 out 空，就把 in 里的元素全部倒进 out。

「倒一次」会发生什么？in 里 [1,2,3]（1 在底、3 在顶），倒进 out 后 out 变成 [3,2,1]（out 顶是 1）。 1 正好是「最先入队的」，现在在 out 顶，弹出它就是队的先进先出！

push 1,2,3  → in=[1,2,3](顶3)，out=[]
pop 时 out 空，把 in 倒进 out：
  out = [3,2,1](顶1)，in=[]
  弹出 out 顶 = 1  （正是最早进队的）✓
再 pop → out 顶=2 ✓（不用再倒，in 还空着）
push 4 → in=[4]
pop → out 顶=3 ✓；pop → out 顶=4... 

参考代码

class MyQueue {
    private Deque<Integer> in;   // 入队栈
    private Deque<Integer> out;  // 出队栈

    public MyQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }

    public void push(int x) {
        in.push(x);              // 入队只压 in
    }

    private void drain() {       // 把 in 倒进 out（仅当 out 空）
        while (!in.isEmpty()) {
            out.push(in.pop());
        }
    }

    public int pop() {
        if (out.isEmpty()) drain();
        return out.pop();
    }

    public int peek() {
        if (out.isEmpty()) drain();
        return out.peek();
    }

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

复杂度

时间：摊还 O(1)。单次 pop 看似可能倒 n 个，但每个元素一辈子只被「倒一次」（从 in 到 out）， 平均下来每次操作代价是常数。空间 O(n)。 为什么叫「摊还」？因为最坏一次 O(n)，但 n 次操作总共 O(n)，平摊每次 O(1)。

直觉检验：为什么「倒一次」就够了

有人会担心：如果 push、pop 交错很多次，会不会有元素卡在 in 里一直倒不出来？不会，原因在于顺序的单调性： in 栈里元素从底到顶是「早进 → 晚进」，而 out 栈需要的是「早进的在顶」。只要 out 还没空，说明「比当前更早进队的元素」都还在 out 里排着， in 里压根轮不到被弹出——新来的元素必须等 out 清空才能轮到它出队。所以「out 空才倒」既正确又最优， 每个元素一生只经历一次 in→out 的搬运。可以拿 push 1, push 2, pop, push 3, pop, pop 在纸上推一遍验证。

6.5每日温度（中等，力扣 739）

中等 核心：单调栈首次登场

题意：给每天温度，对每一天回答「还要等几天才出现更高的温度」。例： [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]。 最后两天之后没有更热，答案是 0。

思路推导

暴力：对每天往后扫找第一个更大的，O(n²)，n 大就超时。怎么优化？

核心洞察：栈里存的是「还没找到答案的那些天的下标」。我们维护一个栈，保持栈底到栈顶温度递减（单调栈）。 从左往右走：

• 当前温度 t 比栈顶那天的温度高 → 说明栈顶那天「等到了」它的更热天，就是今天！ 算出间隔 i − 栈顶下标，弹出栈顶；
• 不断重复，直到栈顶温度 ≥ t（或栈空），再把今天下标压栈。

那些一直没被弹出的（比如最后两天），永远等不到更热，答案保持默认 0。

温度: 73 74 75 71 69 72 76 73
下标:  0  1  2  3  4  5  6  7

i=0: 栈空，压0       栈[0]
i=1: 74>73(栈顶0) → ans[0]=1-0=1，弹0；压1   栈[1]
i=2: 75>74(栈顶1) → ans[1]=2-1=1，弹1；压2   栈[2]
i=3: 71<75 → 压3                           栈[2,3]  (递减)
i=4: 69<71 → 压4                           栈[2,3,4]
i=5: 72>69(4)→ans[4]=1; 72>71(3)→ans[3]=2; 压5  栈[2,5]
i=6: 76>72(5)→ans[5]=1; 76>75(2)→ans[2]=4; 压6   栈[6]
i=7: 73<76 → 压7                           栈[6,7]
结束，栈里剩的[6,7]答案0。

参考代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];                 // 默认 0，没找到的保持 0
        Deque<Integer> stack = new ArrayDeque<>(); // 存「下标」
        for (int i = 0; i < n; i++) {
            // 当前温度更高，说明栈顶那天等到了答案
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = i - idx;             // 间隔天数
            }
            stack.push(i);                      // 今天入栈，等它自己的答案
        }
        return ans;
    }
}

复杂度

时间 O(n)：每个下标最多入栈一次、出栈一次，while 里弹出的是别的天的，总弹出次数 ≤ n。 空间 O(n)：栈最坏存全部下标。为什么存「下标」不存「温度」？因为答案要的是间隔天数，得用下标相减。

怎么一眼认出单调栈题

单调栈不是背出来的，是「认」出来的。当你读题时脑子里冒出下面这些话，就可以往单调栈想：

• 「对每个元素，找它左边/右边第一个比它大/小的」——这是最典型的信号，如每日温度、下一个更大元素、柱状图最大矩形；
• 「不能双重循环，否则超时」——数据量 n 到 10⁵ 还让你「比较每个元素和周围」，O(n²) 必超时，需要把某些比较「跳过」；
• 「答案和‘顺序’有关」——比如接雨水要算左右边界、股票价格算等待天数，本质都是「找某个方向的第一个越界点」。

反过来说，如果你发现自己写的是「对每个 i，内层再 for j 往后找」，先别急着交——想想能不能用单调栈把那些「永远不可能再被需要」的元素提前踢掉。 每日温度里，一旦遇到更高的温度，前面那些更低的就「被答案了结」，再也不用管，这就是单调栈省掉内层循环的根本原因。

6.6单调栈模板总结

每日温度只是单调栈的「求右侧第一个更大」一种。把「更大/更小」「下一个/上一个」四个方向组合，能覆盖一大类题：

一个完整例子：套模板算一遍

拿 nums = [2, 1, 2, 4, 3] 跑一遍「求右边第一个更大」的模板，把每一步栈和结果写出来，你会发现规律特别整齐：

i=0 值2: 栈空，压0            栈[0]
i=1 值1: 1<2(栈顶) 压1        栈[0,1]
i=2 值2: 2>1(栈顶1)→res[1]=2; 2==2(栈顶0)不弹; 压2   栈[0,2]
i=3 值4: 4>2(2)→res[2]=3; 4>2(0)→res[0]=3; 压3      栈[3]
i=4 值3: 3<4(3) 压4          栈[3,4]
结束: 栈里[3,4]没被弹 → res[3]=res[4]=-1
结果: [3, 2, 3, -1, -1]
含义: 2右边第一个更大是下标3的值4; 1右边第一个更大是下标2的值2; 4和3右边没有更大 → -1。

多跑几遍这种小例子，比背模板管用——你会真正「看见」栈是怎么帮你跳过那些不可能再被需要的元素的。

一套通用骨架（以「求每个元素右边第一个更大的下标」为例）：

// 通用模板：求每个元素「右边第一个更大」的下标（没有则 -1）
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);                  // 默认没有更大的
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = i;                  // 当前 i 是 idx 右边第一个更大
        }
        stack.push(i);
    }
    return res;
}

6.7本专题常见坑

6.8自测题