栈和队列OJ刷题全攻略：从括号匹配到单调队列的套路总结

1. 为什么栈和队列是每套OJ题库都绕不开的"基本盘"

如果你翻过杭电OJ、东方博宜、洛谷或者LeetCode的入门题单，大概率会发现一个规律：早期题目里总会有一批挂着"栈和队列"标签的题。我最初刷的时候也不理解，觉得这不就是俩数据结构嘛，一个后进先出一个先进先出，能有啥花活。直到我把一套题从模拟实现一路刷到单调栈、单调队列，才意识到这两个结构在OJ里的地位根本不是"基础知识点"那么简单——它们是算法复杂度从O(n²)降到O(n)的常见杠杆，也是后续学习树、图、搜索时绕不过去的前置工具。

这篇做题报告，我就把自己在栈和队列OJ题目上踩过的坑、总结出来的套路、还有那些"题型一变就卡壳"的应对方案，一次性写清楚。适合正在学数据结构、准备应对笔试机考、或者刚起步刷OJ想建立解题框架的同学参考。

先说结论：栈和队列的OJ题，刷的不是"能不能实现"而是"边界条件处理得够不够干净"。同样是"括号匹配"，有人一次AC，有人反复TLE和WA，差的不是语法熟练度，而是对空栈、容量、下标这些细节的敏感度。这篇报告后面会逐项拆开讲。

1.1 栈和队列在OJ题库里的三种典型身份

根据我在多个OJ平台上的刷题观察，栈和队列题目大致分三类：

1. 纯模拟类：让你用数组或链表手动实现栈/队列，然后做入栈出栈、入队出队操作，考察基本功。代表题型：循环队列容量判断、双栈模拟队列。
2. 结构应用类：栈用来解决"最近匹配"问题，队列用来解决"顺序调度"问题，题目背景一般都包装成某种现实场景。
3. 算法优化类：把栈包装成单调栈、把队列包装成单调队列，本质是借助结构特性做状态压缩，把暴力枚举优化掉一个维度。

这三类难度是递进的。很多同学卡在第二类到第三类的过渡期——不是不会写栈，而是想不到"什么时候该用栈"。我的经验是，看到题目里有"最近""相邻""回溯""依赖之前的某个状态"这些关键词时，优先考虑栈；看到"连续""滑动窗口""按顺序处理且要淘汰旧状态"时，优先考虑队列。

1.2 刷这类题之前，建议先把这7个基础操作刻进脑子里

不管你用C语言手写、用C++的STL、用Java的Deque还是Python列表，栈和队列的OJ题最终都会落到这几个操作上：

操作	栈语义	队列语义	OJ中的高频坑
入栈/入队	push(x) 加到栈顶	enqueue(x) 加到队尾	入栈前通常不用判满（动态结构），入队前要判满（循环队列）
出栈/出队	pop() 移除栈顶	dequeue() 移除队头	pop/出队前必须判空，这是WA重灾区
取顶/取队头	top() 返回栈顶元素	front() 返回队头元素	很多题只要求取值不出队，别顺手pop了
判空	empty()	empty()	C手写时容易忘记重置head/tail
尺寸	size()	size()	有些题要求输出队列长度，别忽略
清空	重置top指针	重置front/rear	多组测试数据之间不清干净，结果全错
遍历	从栈顶往下访问	从队头往后访问	注意访问方向和输出顺序

我在刷题时发现一个很实用的习惯：把每次的"栈空判断"和"队空判断"写成独立函数，不要每次都在逻辑里写if嵌套。因为调试的时候，你可以单独打日志看某一步的栈状态，排查问题快很多。

2. 栈类题目最常考的四个方向：从括号匹配到单调栈

栈在OJ里最经典的应用方向，我总结下来就四个。这也是做题报告里值得单独写的一部分，因为每个方向代表一套独立的解法套路。

2.1 括号匹配类：关键不是栈本身，而是"匹配失败"的边界

括号匹配大概是栈的入门第一题。大多数人的第一版代码长这样：

// 有效括号判断，C语言版核心逻辑 bool isValid(char* s) { int n = strlen(s); char stack[n]; int top = 0; for (int i = 0; i < n; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack[top++] = s[i]; } else { if (top == 0) return false; // 右括号来了但栈空 -> 不匹配 char left = stack[--top]; if (!match(left, s[i])) return false; } } return top == 0; // 遍历完栈还非空 -> 左括号没闭合 }

这个代码本身不难，但OJ题会不断加条件。比如：

• 要求输出第一个不匹配的位置，那你就不能只返回布尔值，得记录下标。
• 要求栈里存的不是括号字符，而是下标，最后用下标差计算闭合区间长度。
• 要求支持多种括号嵌套且必须同类型闭合，这就要注意match函数别写错。

我当初在这类题上WA过两次，都是因为遍历结束后忘了判断栈是否为空。比如输入"((()))"这种，遍历完栈正好空，返回true；但输入"((()"，遍历完栈里还剩一个'('，如果你不看栈直接返回true，就必然WA。这个细节后来成了我检查所有栈类提交的第一道工序。

2.2 表达式求值与后缀转换：两个栈协作的经典写法

中缀表达式转后缀表达式，或者直接求值，是栈类题目里"模拟型"和"应用型"结合得最好的一类。核心思路是用运算符栈暂存运算符：

• 遇到数字，直接输出/压操作数栈。
• 遇到运算符，与栈顶运算符比较优先级：当前优先级高则入栈，否则弹出栈顶运算符并处理后继续比较。
• 遇到左括号直接入栈；遇到右括号，不断弹出直到匹配左括号。

// 中缀转后缀核心逻辑（C++示意） // 优先级：'+' '-' < '*' '/' < '(' for (char ch : expr) { if (isdigit(ch)) { output += ch; } else if (ch == '(') { opStack.push(ch); } else if (ch == ')') { while (!opStack.empty() && opStack.top() != '(') { output += opStack.top(); opStack.pop(); } opStack.pop(); // 丢弃 '(' } else { while (!opStack.empty() && priority(opStack.top()) >= priority(ch)) { output += opStack.top(); opStack.pop(); } opStack.push(ch); } } while (!opStack.empty()) output += opStack.pop();

印象最深的一题是带负数的表达式求值。负数最坑的地方在于：负号可以在一开始出现，也可以在左括号后出现，这种情况下负号是"单目运算符"，优先级处理跟减号完全不一样。我当时自己加了判断：如果负号的前一个字符是(、-、+、*、/或者位置在表达式开头，就把负号当作数字符号处理，而不是运算符。这种题目你光背模板调不过，必须理解表达式解析的语义。

2.3 合法出栈序列判定：卡特兰数之前，先学会模拟

"合法出栈序列判定"是我个人认为最能区分"会写栈"和"真懂栈"的题目。题目长这样：给定入栈序列1,2,3,...,n和一个出栈序列，判断出栈序列是否合法。

很多人第一反应是套卡特兰数公式算数量，但题目问的是"这个具体序列合不合法"，公式帮不上忙。正确做法是模拟入栈出栈全过程：

1. 用一个指针i指向当前要出栈的元素。
2. 遍历入栈序列的元素，依次压入栈中。
3. 每次压入后，循环检查：如果栈非空且栈顶等于出栈序列当前指向的元素，则弹出，i++。
4. 最后看是否所有出栈元素都匹配上。

// 合法出栈序列判定核心（C++） bool checkValidPopSequence(vector<int>& push, vector<int>& pop) { stack<int> st; int j = 0; for (int x : push) { st.push(x); while (!st.empty() && st.top() == pop[j]) { st.pop(); j++; } } return j == pop.size(); }

这个解法看起来简单，但我在做题时一开始写成了"先全部入栈再判断"，结果显然不对。关键点是 while 循环必须放在每次 push 之后，而不是所有 push 完了再一次性 pop。因为出栈序列是动态的，你必须在每个入栈时机都尝试"尽可能多地满足出栈需求"。这个"随时尝试匹配"的思路，放到其他模拟类题目里也通用。

2.4 单调栈：用空间换时间，一次遍历干掉一类题

单调栈是栈类题目里含金量最高的部分，也是从"模拟应用"跨越到"算法优化"的一道门槛。核心定义很简单：维护一个栈，保证栈内元素按某种单调性排列（单调递增或单调递减），每次新元素入栈时把破坏单调性的元素弹出。

经典题目比如"每日温度"：给定每日温度数组，返回每天需要等几天才能等到更高温度。暴力法是每个位置往后扫描，O(n²)。单调栈解法是：

// 每日温度：单调递减栈（栈内存下标，不是温度值） vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); stack<int> st; // 存下标，温度单调递减 for (int i = 0; i < n; i++) { while (!st.empty() && temperatures[st.top()] < temperatures[i]) { int idx = st.top(); st.pop(); ans[idx] = i - idx; } st.push(i); } return ans; }

我在这个模板上犯过的最大错误是单调性方向搞反。找"右边第一个比当前温度高的"，要维护的是栈顶到栈底递减；找"左边第一个比自己小的"，要维护的是递增。每次写题我都得在心里过一遍：当前元素来了之后，哪些栈内元素"等到了"答案，它们要被弹出。弹出的条件就是"当前元素比它们更优（更大或更小）"。

单调栈的典型应用还有"柱状图中最大矩形""接雨水""去除重复字母"等。同一个模板换几个条件就是一道新题，这也是为什么我建议把单调栈当成"见到就刷三遍"的核心模板——第一遍理解思路，第二遍手写调试，第三遍改条件换题目检验。

3. 队列类题目：循环队列的空间玄机与滑动窗口的单调性

队列在OJ里的直接出场率不如栈高，但一旦出场，就往往是"循环队列""双端队列""单调队列"这些变体。这一节我把最常考的三类拆开说。

3.1 循环队列：满和空都是front==rear，你用什么区分

循环队列用数组模拟时，最关键的问题是：队空和队满时front和rear都相等。你必须选一种策略来区分。常见做法有三种：

1. 牺牲一个存储单元：当(rear+1) % capacity == front时认为队满。队空条件仍是front == rear。有效容量是capacity-1。这是最推荐的，实现简单。
2. 使用size计数器：维护一个size，入队时size++，出队时size--，size==0为空，size==capacity为满。代价是多维护一个变量。
3. 增加flag标记：用flag记录最后一次操作是入队还是出队。最绕，不推荐。

// 循环队列核心：牺牲一个位置的写法 #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front, rear; } CircularQueue; int empty(CircularQueue* q) { return q->front == q->rear; } int full(CircularQueue* q) { return (q->rear + 1) % MAX_SIZE == q->front; } // 入队：先判满 int enqueue(CircularQueue* q, int x) { if (full(q)) return 0; // 失败 q->data[q->rear] = x; q->rear = (q->rear + 1) % MAX_SIZE; return 1; } // 出队：先判空 int dequeue(CircularQueue* q) { if (empty(q)) return 0; q->front = (q->front + 1) % MAX_SIZE; return 1; }

我第一次手写循环队列时，入队和出队都用了++而不是取模运算，结果队列绕一圈之后越界越到怀疑人生。循环队列的入队出队，rear和front的移动必须取模，这个低级错误在OJ里特别容易犯，因为小规模测试数据根本测不出来，一旦数据容量接近队列上限就原形毕露。

3.2 链式队列与双端队列：挑根指针还是挑哨兵结点

用链表实现队列时，有一个细节很多教材没强调：队列需要同时维护front和rear两个指针，而且出队时要特别注意"队列只剩一个元素"的情况——如果front == rear，出队操作后不仅要移动front，还要让rear也指向空（否则rear变成悬空指针）。

// 链式队列出队，注意只剩一个结点的边界 int dequeue(LinkedQueue* q, int* out) { if (q->front == NULL) return 0; Node* temp = q->front; *out = temp->data; q->front = q->front->next; if (q->front == NULL) { q->rear = NULL; // 关键！不写这行就悬空了 } free(temp); return 1; }

这个"出队后rear也要更新"的坑，我在做某道模拟打印机队列的OJ题时踩过，差一个测试用例没过，查了半小时才发现是链表尾部指针没重置。

至于双端队列（deque），在OJ里通常出现在"滑动窗口需要从两端删除元素"的场景。C++的std::deque、Java的ArrayDeque、Python的collections.deque都是现成的，但出题人如果要求你手写双端队列，一般是为了考察你能否同时管理头尾。我的经验是不管用现成容器还是手写，先把"允许从两端插入删除"这个特性在草稿纸上画一遍，避免把push_front/pop_back搞混。

3.3 单调队列与滑动窗口：一个模板吃透"连续区间最值"

单调队列是队列方向的压轴知识点，经典题目是"滑动窗口最大值"。给定数组和一个大小为k的窗口，窗口每次右移一位，输出每个窗口内的最大值。暴力法是O(nk)，单调队列解法是O(n)。

核心思路：队列里存的是数组下标，且下标对应的数组值从队头到队尾单调递减。每次窗口移动，做两件事：

1. 淘汰过期元素：队头下标小于等于当前窗口左边界时，弹出队头。
2. 保持单调性：从队尾开始，把所有值小于等于当前元素的下标全部弹出，然后把当前下标压入队尾。

// 滑动窗口最大值单调队列模板（C++） vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 存下标，值递减 vector<int> ans; for (int i = 0; i < nums.size(); i++) { // 移除窗口之外的旧下标 while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 保持队列单调递减：移除所有比当前元素小的队尾 while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); // 窗口完整后才开始记录答案 if (i >= k - 1) ans.push_back(nums[dq.front()]); } return ans; }

这个模板我写错过三次，三次原因各不相同：第一次是忘写i >= k-1这个窗口完整判断，导致窗口没满就开始输出；第二次是队头和队尾的弹出条件写反；第三次是忘了更新队列里元素的"过期检测"，把窗口边界写成硬编码。这里强烈建议把模板理解透再背，否则换个题型必死。

单调队列的变种应用还包括"滑动窗口最小值""最长连续子数组长度"等，思路完全一样，就是把单调递减改成单调递增。

4. 做题报告中最常见的六个翻车点，每一个我都踩过

刷OJ和做课后习题最大的区别在于：OJ绝大多数时候不给你样例输出，出错只有WA或TLE两个结果，你得自己定位。下面是这一轮栈队列刷题中我用WA和TLE换来的经验，建议直接收藏。

4.1 数组越界与栈空误判：直接错两三个用例是常态

手写栈/队列的OJ题，WA的第一大根因就是越界和空结构误判。比如入栈前没检查是否满了，出栈前没检查是否空了，或者循环队列取模时忘记加capacity导致负数下标。我给自己定的规矩是：每道手写结构体的题，动手写代码前先在草稿纸上画出空、满、单元素三种状态下的front/rear值分布。这个步骤看着慢，但能省掉至少两轮调试。

4.2 多组输入与EOF处理：辛辛苦苦写的逻辑全栽在输出格式上

很多OJ平台（尤其是杭电OJ这类ACM风格的），题目要求处理多组输入直到EOF。C语言里要用while(scanf("%d",&n)!=EOF)，C++里用while(cin>>n)，Java里用while(scanner.hasNext())。这三种写法是基础，但真正的坑是：

• 有的题目要求每组输出之间有空行，最后一组后面没有；
• 有的题目要求每行末尾不能有多余空格；
• 有的题目输入行可能包含空行，你用gets/getline容易把空行读进去。

我的经验是：提交之前先把样例输入复制本地跑一遍，再手动构造一组"输入末尾多一个回车"的数据测试。很多WA不是算法错了，是输出格式差了那么一个换行。

4.3 递归栈溢出与手动栈替代方案

OJ里的"栈"不只有数据结构意义上的栈，还有系统调用栈。有些题你会用递归写，比如树的遍历、深度优先搜索，但部分OJ平台的栈空间限制很死（有的只有1MB或8MB），递归深度一大就爆栈，表现不是WA而是Runtime Error。

这时候有两个选择：一是把递归改成迭代，用显式的std::stack模拟系统栈；二是把递归改成尾递归或循环（如果语言支持）。我在做"二叉树中序遍历"的题时，用递归在本地跑完美，提交到某OJ直接RE，查了错误提示才发现是栈溢出。如果题目里出现"n最大10^5"这类规模提示，优先考虑迭代实现。

4.4 用错容器导致TLE：双端队列不是银弹

语言内置的容器选择会直接影响TLE（超时）与否。举个具体例子：Python里list.pop(0)是O(n)操作，如果你用它模拟队列，数据量大时必TLE。应该用collections.deque，它的popleft()才是O(1)。

C++里则要小心std::queue默认底层是std::deque，如果你频繁在队头操作，直接使用std::deque可能更合适。还有一个经验是：如果题目明确要求"手写队列"别用STL，你就老老实实数组模拟，有些OJ会禁用STL或者故意卡STL的常数。

4.5 不要忽略编译器的C++标准差异

有些OJ的古早编译器还不支持std::deque的某些新写法，或者一些在线评测平台的C++环境是C++03标准。写代码时尽量只用最基础的语法，比如stack<int>、queue<int>、vector<int>这些，别一上来就C++17的特性。我见过有同学因为用了结构化绑定，在OJ上古编译器上报编译错误。做题之前花30秒看一下OJ的编译器版本和语言选项，是高手和新手的习惯差距之一。

4.6 构造测试用例的能力，比刷题量更值钱

栈队列的题，AC与否往往取决于边界数据。我在刷完一轮之后意识到，与其一个劲刷新题，不如把做过的每一题总结出对应的"杀手用例"。比如括号匹配的杀手用例是")("和"(()"；合法出栈序列的杀手用例是1 2 3配3 1 2（不合法，因为3弹出后不可能先弹1）；滑动窗口最大值的杀手用例是数组全相等。

当你脑子里积累了一批这样的"反例库"，你写代码时会自动去检查这些case，AC率会肉眼可见地提高。这也是做题报告里最值得记录的部分——你不是在刷题，你是在采集反例标本。

5. 从OJ题目到真实项目：栈和队列在工程里的落地位置

刷OJ的时候，我一直提醒自己别把栈和队列当成"考试专用的抽象玩具"。它们在实际开发和面试中是真真切切在用的，而且用的形式和OJ题不完全一样。

5.1 调用栈、消息队列、阻塞队列：工程里的三种栈队列形态

先说调用栈。每个函数的局部变量、返回地址都存在系统调用栈上，递归深了会爆栈，这就是4.3节提到的OJ RE在真实世界的映射。不少后端故障排查里用的"backtrace栈回溯"技术，本质上就是打印调用栈的内容，跟OJ题里"遍历栈输出所有元素"没有本质区别，只不过工程里栈里的元素是函数帧。

再说队列。消息队列可能是最常被提到的工程应用——你往队列里扔任务，消费者按顺序处理。消息队列重复消费问题（热词里高频出现）映射到OJ题上，其实就是"多个消费者同时从队列里取数据时如何保证不重复不遗漏"，这比OJ里的单线程队列多了一层并发控制，但底层还是队列那个先进先出的契约。

还有线程池里的阻塞队列：当任务数超过线程池核心线程数时，多余任务会放进阻塞队列里等待。LinkedBlockingQueue、ArrayBlockingQueue、SynchronousQueue这些选择，对应到OJ题就是"你选链式队列、数组循环队列还是无缓冲队列"的工程版。你在OJ里手写过的循环队列，理解线程池参数时会比别人快很多。

5.2 把OJ题里的单调队列思维迁移到业务代码

我一直觉得单调队列是那种"OJ里学完，工程里一直用"的知识。比如实时监控系统里要统计最近5分钟的流量峰值，数据持续到达，窗口不断滑动——这不就是"滑动窗口最大值"吗？用暴力法每5分钟扫一遍数组，数据量大了必挂；用单调队列把复杂度压到O(n)，几百毫秒变几毫秒。

再比如股票行情里的"过去N天最高价"，或者直播弹幕系统的"最近N条消息里点赞最高的内容"，全是同一套模板。很多业务性能问题，不是你需要引进多牛的框架，而是你手里有没有单调队列这个思维工具。

我还有一个体会是，做了栈和队列的OJ题之后，你写代码会更在意"状态是否积压"这件事。比如IO事件处理、网络请求回调、前端渲染管线，本质上都是队列模型，而"排队是否合理""过期数据是否剔除"就是单调队列里那两行pop语句的工程复现。

最后说一句我个人做这套题的真实体会：栈和队列的OJ题是所有数据结构里投入产出比最高的。它们不像图论和DP那样需要大量前置知识加持，你只要把边界条件处理干净、把两个单调模板练熟，就能稳定拿分。做完一轮之后回头看，最大的收获反而不是AC数量，而是养成了"先画状态图、再写代码、最后造边界用例"的做题习惯——这个习惯，对后续刷任何算法题都有用。