栈与队列专题：从双栈模拟到单调队列的算法思维

1. 今天到底练了什么：专题2的题目地图与核心目标

1.1 专题1没说完的事：从"认识工具"到"理解工具"

代码随想录算法训练营走到第11天，栈和队列专题进入第二天。第一天我们做的事其实很朴素：搞懂栈是后进先出、队列是先进先出，学会C++里stack和queue的基本API，然后拿它们去解几道模板题。坦白说那时候的状态就是"知道这玩意儿怎么用了"，但没到"遇到问题能想到用它"的程度。

专题2的定位就是补上这个差距。它不再满足于让你调用stack和queue，而是安排了一连串"表面上看根本不像栈和队列题"的题目：用栈去实现队列、用队列去实现栈、判断括号字符串、删除字符串里的相邻重复项、计算逆波兰表达式、求滑动窗口最大值、统计前K个高频元素。看到这份题单的第一反应可能会懵：栈和队列还能折腾出这么多花样？

这就是专题2的价值所在。第一天讲的是"数据机构的定义和基本操作"，第二天练的是"数据结构作为算法思维的一部分"。同样一个栈，它可以是容器、是缓冲、是撤销栈、是表达式计算的辅助结构；同样一个队列，它可以是任务调度队列、是单调队列、是优先级队列的底层载体。把这些用法一个个过完，你对"栈和队列到底擅长解决什么问题"才会有体感。

1.2 专题2的完整题目地图

我把这一天涉及的题目按训练营常见的安排梳理成了一张表，方便对照检查自己的完成情况：

前五题是"栈和队列解决经典问题"，后两题是"基于栈/队列思想的自定义数据结构"。我的建议是不要因为它们看起来不相关就分开对待，它们是一条线：前三题让你看懂栈的"抵消"能力，中间一题让你看懂栈的"延迟计算"能力，最后两题让你学会在标准容器不能满足需求时自己造一个带规则的结构。

1.3 一个贯穿全天的核心视角：把数据结构当零件

如果你跟过几天的训练营，会发现优秀的解法通常不是靠灵光一现，而是脑子里有一个"零件库"：遇到匹配问题想到栈，遇到先进先出想到队列，遇到最值问题想单调结构，遇到Top K想堆。专题2的所有题目都在帮你往这个零件库里补货。

所以我在做这天的题时给自己定了一个小目标：不满足于AC（通过），每个题都要能说出"为什么用栈/队列而不是别的东西"。比如有效括号那题，为什么不能用三个计数器分别统计小中大括号？因为计数只能校验数量，校验不了顺序。所有这些"为什么"想清楚了，后面的滑动窗口和前K个高频元素就不会觉得是突然冒出来的难题，它们只是同一套思维的延伸。

2. 用栈实现队列、用队列实现栈：两道题吃透"底层互转"的逻辑

2.1 用栈实现队列：两个栈倒一手，核心在"全量倒"

用栈实现队列，第一反应是"这怎么可能"。栈后进先出，队列先进先出，方向明明相反。但方向相反不代表不能转换——只需要"反转两次"。如果你把一串元素压入一个空栈，再从这个栈依次弹出并压入另一个空栈，第二个栈顶就变成了原来的第一个元素。这就是双栈模拟队列的全部原理。

具体写法是维护两个栈：stIn负责入队，stOut负责出队。push时直接压入stIn，pop时如果stOut为空，就把stIn的所有元素一次性全部倒入stOut，然后取stOut的栈顶。这里有个特别容易踩的细节：为什么是"一次性全部倒完"而不是"倒一个就用一个"？因为stIn栈顶是最后入队的元素，如果你只倒一个，那这个元素到了stOut栈顶，下一次pop时它依然不是最早入队的那个。只有把整个stIn反转过来，stOut的栈顶才是真正的队头。

cpp复制class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;

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

    int pop() {
        // 只有stOut空了才需要重新倒盘
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    int peek() {
        // 复用pop，再压回去即可
        int result = this->pop();
        stOut.push(result);
        return result;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

我在这一题上第一次提交就栽在了peek上：想当然地直接返回stOut.top()，没考虑到stOut可能是空的。后来改成复用pop再压回，代码短了，逻辑也更不容易错。这个小模式值得记下来——很多容器模拟题里，"取队头但不删除"都可以用"先pop再压回"实现。

2.2 用队列实现栈：一个队列也能完成，关键在于"旋转"

用队列模拟栈的思路方向相反。队列是先进先出，想让最后进来的元素先出去，办法是每次pop时把队列"转"一圈：将队头的元素依次搬到队尾，直到原来的最后一个元素成为队头。我采用的方式是保持队列的顺序始终等于"栈底到栈顶"，那么队尾就是栈顶，pop时把前面的size-1个元素全部搬到队尾，再弹出队头。

cpp复制class MyStack {
public:
    queue<int> q;

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

    int pop() {
        int size = q.size() - 1;
        while (size--) {
            q.push(q.front());
            q.pop();
        }
        int result = q.front();
        q.pop();
        return result;
    }

    int top() {
        return q.back(); // 队尾就是栈顶
    }

    bool empty() {
        return q.empty();
    }
};

这个写法里push是O(1)，pop是O(n)。如果面试官追问复杂度，可以换一种"push时旋转"的实现：每次push后把前面的元素全部搬到新元素后面，这样pop就是O(1)。两种方案都可行，关键是理解旋转的本质——用队列的顺序性来模拟栈的反向性。

2.3 两道题对照看：顺序反转层的两种策略

拿栈模拟队列，本质是"反转两次等于不反转"；拿队列模拟栈，本质是"用旋转修正方向"。这两个结论看着简单，但很多人在讲解时会混淆。我自己的记忆方法是：

• 栈到队列：方向相反，反转两次即可，所以双栈。关键是"全量倒"。
• 队列到栈：队列本身没有反转能力，只能靠旋转"把队头送到队尾"，直到目标元素到队头。关键是"转size-1次"。

如果你做这组题只是为了AC，AC之后建议再手写一遍源码。我后来在面试里被问过不止一次"你如何用一个数组实现栈和队列"，本质就是这两道题的变体。想清楚双栈的倒盘时机、单队列的旋转次数，这类问题就只是换层皮。

3. 括号匹配与相邻字符消除：栈的"抵消"模型

3.1 括号匹配：为什么不是数三个计数器

有效的括号是一个经典的"看着简单但容易想错"的问题。最容易想到的错误方案是用三个计数器分别统计三类括号的数量，最后检查是否都为0。这方案对"()[]{}"这种简单用例有效，但对"([)]"这种恶意嵌套就直接翻车——三个计数器都是2，最终平衡，但实际括号顺序错得离谱。

问题就出在括号不仅是数量问题，更是顺序问题。最近的右括号必须匹配最近未闭合的左括号，这种"最近匹配"的语义天然对应栈的LIFO特性：遍历字符串时，遇到左括号就压栈，遇到右括号就检查栈顶是不是对应的左括号，匹配则弹出，不匹配直接返回false。栈顶保存的永远是"最近的未闭合左括号"。

代码里有个值得借鉴的小技巧：不要存左括号本身，而是遇到左括号时把"期待出现的右括号"压入栈。这样遇到右括号时只需要比较栈顶是否相同，省掉了左括号与右括号的映射判断分支。

cpp复制class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) return false;
        stack<char> st;
        for (char c : s) {
            if (c == '(') st.push(')');
            else if (c == '[') st.push(']');
            else if (c == '{') st.push('}');
            else if (st.empty() || st.top() != c) return false;
            else st.pop();
        }
        return st.empty();
    }
};

奇数长度的字符串直接返回false，这个剪枝虽然微不足道，但能避免后面的无谓遍历。还有一个容易被忽略的点：字符串遍历完后栈必须为空，因为可能存在"((()"这种只有左括号的输入。

3.2 删除字符串中的所有相邻重复项：把字符串本身当栈用

"abbaca"经过一次删除变成"caaca"，再删变成"ca"。这类题有个形象的名字叫"消消乐"：从左往右扫描，当前字符如果和上一个保留的字符相同，就把上一个也删掉；如果不同，就暂时保留，等待后面的字符来"抵消"它。

栈是天然的数据结构，因为每一步都只关心"最近保留的字符"。但真正实现时我建议直接拿string当栈用：result.back()表示栈顶，result.push_back()表示入栈，result.pop_back()表示出栈。这样省掉了最后把栈里元素翻转回字符串的额外开销。

cpp复制class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char c : s) {
            if (!result.empty() && result.back() == c) {
                result.pop_back();
            } else {
                result.push_back(c);
            }
        }
        return result;
    }
};

这个"匹配就抵消、不匹配就暂存"的模型在后续题目里反复出现。字符串解码、删除有效括号的子串、简化Unix路径等等，底层都是同样的栈顶交互逻辑。这一题虽然简单，但它是后面很多"栈应用题"的基本功，值得多写两遍形成肌肉记忆。

4. 逆波兰表达式求值：为什么后缀表达式天然适合栈

4.1 中缀、前缀、后缀：三种写法谁最"计算机"

我们平时写"3 + 4 * 2"是中缀表达式，运算符在两个操作数中间，需要知道乘法的优先级高于加法，还得处理括号。但计算机和人不一样，它不擅长"全局观察优先级"，它适合"从左到右、一步步执行"。这就引出了后缀表达式（逆波兰表达式）：操作数在前，运算符在后，"3 4 2 * +"。

后缀表达式求值有一个极其简洁的规则：从左到右扫描，遇到数字就压栈，遇到运算符就从栈顶弹出两个操作数，运算后把结果压回栈。扫描结束，栈顶就是最终结果。整个过程不需要考虑优先级，也不需要括号，因为后缀表达式的书写顺序已经把优先级隐含进去了。

举个具体例子，"3 4 + 5 "对应的中缀是"(3 + 4) * 5 = 35"。计算时：3入栈，4入栈，遇到+，弹出4和3得7压栈，5入栈，遇到，弹出5和7得35。每一步都只依赖栈顶的两个元素，这就是栈"延迟计算"能力的体现——操作数先躺在栈里，等运算符来了才被取用。

4.2 求值过程的两个经典坑：出栈顺序与除法的方向

看上去如此顺滑的算法，实现时却有两个容易中招的细节。

第一个坑是操作数顺序。假设栈里从栈底到栈顶依次是a、b，遇到减号时，先弹出的是b（右操作数），后弹出的是a（左操作数），真正计算的是a - b而不是b - a。除法和减法一样敏感，用"3 4 -"验证一下就知道，如果顺序写反结果就错了。

cpp复制class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int num1 = st.top(); st.pop(); // 右操作数
                int num2 = st.top(); st.pop(); // 左操作数
                if (token == "+") st.push(num2 + num1);
                else if (token == "-") st.push(num2 - num1);
                else if (token == "*") st.push(num2 * num1);
                else st.push(num2 / num1);
            } else {
                st.push(stoi(token));
            }
        }
        return st.top();
    }
};

第二个坑是负数和C++除法的截断方向。tokens里可能出现"-2"这种字符串，std::stoi可以直接转换。而两个负数相除时，C++的整数除法向零截断（-7 / 2 = -3），有些语言是向下取整（-7 / 2 = -4）。如果题目没有明确说明，建议在调试时专门写好负数用例，避免看不见的数学语义差异。

4.3 从函数调用到逆波兰：栈无处不在

逆波兰表达式求值看起来是道算法题，但它揭示的其实是编译器处理表达式的通用思路。你在代码里写的每个嵌套函数调用，运行时都会变成一摞栈帧：调用函数时压入栈帧，函数返回时弹出栈帧，调用栈回溯就是逆向遍历这些帧。这和"把操作数压栈、遇到运算符弹栈"本质上是同一套模型。

我推荐把这题背后"栈帧"的概念简单地了解一下，不用深入汇编层，只需知道每个栈帧保存了函数的局部变量、返回地址和上一层调用关系。理解了这一点，再看"backtrace栈回溯""中断栈帧"这些工程概念就不会觉得和算法训练脱节。表达式求值题练的不是这十几行代码，而是"程序执行过程中状态如何被保存和恢复"的直觉。

5. 滑动窗口最大值：为什么大顶堆在这道题里会翻车

5.1 从暴力法开始：窗口每次移动都要重新找最大值

求"3 1 -1 -3 5 3"在窗口大小3时的滑动最大值，最直接的写法是每移动一次窗口，就遍历窗口内k个元素找最大。代码三行就能写完，但时间复杂度是O(nk)。当k接近n时，这个算法会退化到O(n²)，在LeetCode上直接超时。

暴力法的问题不在于找最大值本身，而在于"每次都在重复扫描旧的元素"。相邻两个窗口之间有k-1个元素是重叠的，上一轮的最大值明明对下一轮还有参考价值，却被浪费掉了。我们要设计的是一个"移动窗口时能以O(1)左右代价获得当前最大值"的数据结构。

5.2 大顶堆的尴尬：能拿到最大值，却删不掉过期元素

很多人第一反应是用大顶堆：堆顶就是最大值，取它O(1)。但窗口滑动的关键动作不只是取最大，还要"移除离开窗口的元素"。大顶堆只保证堆顶是全局最大，不保证你能精准地删除任意元素——堆中元素的位置和窗口的"过期"状态没有任何对应关系。

当然你可以用懒删除：堆里同时存值和下标，每次取堆顶时检查下标是否还在窗口内，不在就弹出继续找。这个方案可行，但堆的操作和删除逻辑叠加在一起，代码量并不少。而且如果窗口里出现重复最大值，你还要小心"删了一个但还有另一个"的状态维护。能用，但不优雅。

5.3 单调队列：一个维护"候选最大值"的滑动窗口

真正简洁的方案来自一个反直觉的想法：与其每轮在窗口里找最大值，不如维护一个队列，让队头永远是当前窗口的最大值。这个队列内部必须保持单调递减——从队头到队尾，元素值越来越小。

怎么维护？窗口向右滑动时做两件事：

1. 队头元素的下标如果小于当前窗口的左边界，说明它已经过期，从队头弹出。
2. 新元素入队前，从队尾开始弹出所有比它小（或等于）的元素，然后新元素入队。

第二点的理由值得多说两句：一个旧元素，如果它既比新元素小（或相等），位置又比新元素靠前，那么只要新元素还在窗口里，旧元素就永远不可能是最大值。既然它已经"失去了未来"，留着只会拖累队列，直接弹掉。这个过程保证了队列里的元素从队头到队尾是"值递减、下标递增"的候选名单。

cpp复制class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq; // 存下标
        for (int i = 0; i < nums.size(); i++) {
            // 移除窗口外过期的队头
            if (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }
            // 从队尾弹出比新元素小或相等的下标
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
            // 窗口形成后，队头就是当前窗口最大值
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

注意队列里存的是下标而不是值，原因是为了判断过期：只有拿到下标，才能知道它是否小于左边界。如果只存值，判断过期还得另想办法，凭空增加逻辑复杂度。

5.4 复杂度与那个"<="的细节

单调队列算法每个元素最多入队一次、出队一次，整体复杂度是O(n)，空间O(k)。但有个细节值得单独说：弹出条件用"<= nums[i]"还是"< nums[i]"，两种写法功能上都正确，但效果不同。用"<="时，新元素会把更早的那些相等值挤掉，让队列里保留的下标更新。如果连续出现相同最大值且窗口滑动，保留更新下标会让过期判断更精确，队列也更短。我在练习中统一用"<="。

这道题是栈和队列专题2里的分水岭：前几道题是"使用现成的栈和队列"，这道题开始挑战你"根据需求定制数据结构的状态维护规则"。单调队列的核心不是队列本身，而是"什么时候弹出、什么时候替换"的淘汰策略。把这个策略想明白，之后很多滑动窗口类问题都能沿同一套路。

6. 前K个高频元素：小顶堆的优雅与priority_queue用法

6.1 一个看似顺理成章的误答：先建大顶堆再弹K个

题目要求返回数组里出现频率最高的K个元素。常规思路分两步：第一步哈希表统计每个数字的频率；第二步按照频率排序，取前K个。如果拿大顶堆把所有元素都塞进去，再弹K次堆顶，确实能得到正确结果。这个方案很容易想出来，也是很多人的第一版提交。

但它不够好。把所有元素都建堆再逐个弹出，时间复杂度是O(n log n)。当n是百万级，K很小比如2或者3时，这个方案做了大量无用功——我们只关心频率最高的那么几个，却给所有低频元素都排了一次序。

6.2 反向思维：固定大小K的小顶堆

正确做法是维护一个大小为K的小顶堆。遍历哈希表时，每个元素先跟堆顶比较：如果堆的大小还没到K，直接入堆；如果堆已满，且当前元素频率大于堆顶，就把堆顶弹出、当前元素入堆；否则跳过。

堆顶始终是"当前K个候选里频率最小的那个"。因为是从小到大排列，新元素只有比"最弱候选"更强时才有资格进入前K名。遍历结束后，堆里的K个元素就是频率最高的K个。这个过程的时间复杂度是O(n log k)，当k远小于n时优势非常明显，空间也只有O(k)。

cpp复制class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;

        // priority_queue 默认是大顶堆，传 greater 变成小顶堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (auto& [num, cnt] : freq) {
            pq.push({cnt, num});
            if (pq.size() > k) pq.pop();
        }

        vector<int> result;
        while (!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
};

所以整体思路是：先用哈希做频率统计，再用小顶堆做Top K筛选。关键要点是pair的元素顺序——把{cnt, num}放进pq，这样比较时优先按频率（cnt）大小排序，堆顶就是频率最小的。如果你想按数字大小排序，换一下pair顺序就行。这个细节面试时容易被追问，priority_queue的默认比较逻辑是"先比较first，再比较second"，用好它能省不少自定义比较函数的功夫。

6.3 Top K问题的家族套路

前K个高频元素其实属于更大的一类问题：Top K。数组第K大、最小的K个数、出现频率最高的K个元素、流数据里的动态Top K，背后都是同一个套路："容器 + 固定大小堆"。只不过这里的容器可能是哈希表、可能是原始数组，堆的排序依据可能是值、可能是频率、可能是距离。

掌握这道题最大的收获，是学会"小顶堆当筛子"的思路。很多人被"找最大"困住，第一反应总是大顶堆；但加上"只看前K个"这个条件后，小顶堆反而更优。它像一个严格的守门员：新来的选手只有比门内最弱的强，才能把最弱的挤出去。这类"保留Top K"的思想在实时排行榜、限流白名单、热门商品统计里都用得上。

7. 交作业之外的提醒：几个被低估的坑和面试延伸

7.1 我自己提交时踩过的三个细节坑

第11天的题虽然都是模板题，但提交几次后你会发现，错误往往不在思路而在细节。

第一个坑是C++里stack的pop不返回值。很多用Java或C++的新手会写出int x = st.pop();这种代码，编译直接报错，因为STL的pop是void。正确写法是先int x = st.top(); st.pop();。这个问题在逆波兰表达式求值那题里体现得淋漓尽致——每弹一个数都要写两行。

第二个坑是括号题的"奇数长度剪枝"。我第一次提交时只写了完整的扫描逻辑，忽略了奇数长度这条快速失败路径。虽然不剪枝也能过，但剪枝后代码的行为更清晰：遇到奇数长度，它绝对不可能合法，无需浪费栈操作。

第三个坑是滑动窗口题里队列存下标还是存值。我不知道你有没有试过存值的版本，反正我当时为了图省事直接存值，结果每次移动窗口都要额外判断"这个值是不是过期的"，代码复杂度直线上升。改成存下标后，过期判断一句搞定：dq.front() < i - k + 1。这个经验可以推广：凡是涉及"元素会过期/需要按位置淘汰"的问题，优先考虑存下标或者"值+下标"，别只存值。

7.2 从STL底层看：stack和queue为什么默认容器是deque

专题2里大量使用deque（双端队列），尤其是单调队列那道题。这也让我忍不住去翻了翻STL源码逻辑：C++里std::stack和std::queue默认的底层容器都是std::deque，而不是vector。

原因是deque支持双端插入删除，两端操作都是O(1)，恰好吻合stack和queue的需求：stack只需要在一端操作，queue需要一端进一端出。vector在尾部操作是O(1)，但在头部插入删除是O(n)，所以不适合作为queue的底层。这也解释了为什么单调队列问题里直接用deque写很方便——它天然支持"队尾弹出、队头弹出、两端查看"这些操作，而这些操作恰好是单调队列需要的。

如果你手头没有工程经验，可能觉得这些底层知识无所谓。但面试问到"为什么STL里queue的底层是deque"时，一句"因为deque两端操作都是O(1)"就能拉开差距。算法题不只是刷过，把容器特性顺手了解一下，性价比很高。

7.3 从算法题到工程：阻塞队列、消息队列里都藏着队列的魂

做题做久了容易陷进一个误区，觉得栈和队列只是面试货。实际上它们在工程里的存在感比任何数据结构都强。消息队列里的"生产者-消费者"模型，本质上就是一条队列：生产者把消息放到队尾，消费者从队头取消息；阻塞队列则是给这条队列加上了"满时等待""空时等待"的规则。线程池里也用有界阻塞队列来缓存待执行的任务，队满策略直接关系到系统的背压行为。

这些都是"栈和队列专题2"内容的自然延伸。做题时多想想"这个数据结构在真实系统里扮演什么角色"，对理解算法题和工程架构之间的桥梁很有帮助。比如阻塞队列的"满等待"和滑动窗口的"过期淘汰"，抽象到底都是"队列的边界规则"——算法题里你定义这些规则，工程系统里框架帮你内置好了这些规则。

7.4 给同样在刷这一天的你一点节奏建议

如果你也在跟训练营的进度，我建议这一天别追求一天之内七道题全AC就翻篇。栈和队列专题有个特点：前几道题的代码都很短，但背后的模型需要反复回味。我的做法是分成两轮：第一轮当天做完，第二轮隔一天再做"用栈实现队列""滑动窗口最大值"这两道，不带任何提示地重新写一遍。

重写时你会发现自己到底真的理解了，还是只是记住了答案。单调队列那道题我第一遍写出来靠的是背模板，第二遍默写时才真正想明白"为什么队尾要弹掉较小元素"。这种感觉只有重做才能获得。这个"隔一天重写"的方法，比连续刷十道新题管用得多。

我个人在实际操作中还有个偏好：所有用到栈的题，都先在草稿纸上画两三步"入栈-出栈"的过程，再落代码。特别是单调队列，光靠脑子转容易漏掉边界条件，画出队头和队尾的变化后，代码几乎是一次过。这个习惯我从第11天开始养成，后面刷二叉树、回溯算法时也一直在用。