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

1. 为什么栈和队列是每套OJ题库都绕不开的基本盘如果你翻过杭电OJ、东方博宜、洛谷或者LeetCode的入门题单大概率会发现一个规律早期题目里总会有一批挂着栈和队列标签的题。我最初刷的时候也不理解觉得这不就是俩数据结构嘛一个后进先出一个先进先出能有啥花活。直到我把一套题从模拟实现一路刷到单调栈、单调队列才意识到这两个结构在OJ里的地位根本不是基础知识点那么简单——它们是算法复杂度从O(n²)降到O(n)的常见杠杆也是后续学习树、图、搜索时绕不过去的前置工具。这篇做题报告我就把自己在栈和队列OJ题目上踩过的坑、总结出来的套路、还有那些题型一变就卡壳的应对方案一次性写清楚。适合正在学数据结构、准备应对笔试机考、或者刚起步刷OJ想建立解题框架的同学参考。先说结论栈和队列的OJ题刷的不是能不能实现而是边界条件处理得够不够干净。同样是括号匹配有人一次AC有人反复TLE和WA差的不是语法熟练度而是对空栈、容量、下标这些细节的敏感度。这篇报告后面会逐项拆开讲。1.1 栈和队列在OJ题库里的三种典型身份根据我在多个OJ平台上的刷题观察栈和队列题目大致分三类纯模拟类让你用数组或链表手动实现栈/队列然后做入栈出栈、入队出队操作考察基本功。代表题型循环队列容量判断、双栈模拟队列。结构应用类栈用来解决最近匹配问题队列用来解决顺序调度问题题目背景一般都包装成某种现实场景。算法优化类把栈包装成单调栈、把队列包装成单调队列本质是借助结构特性做状态压缩把暴力枚举优化掉一个维度。这三类难度是递进的。很多同学卡在第二类到第三类的过渡期——不是不会写栈而是想不到什么时候该用栈。我的经验是看到题目里有最近相邻回溯依赖之前的某个状态这些关键词时优先考虑栈看到连续滑动窗口按顺序处理且要淘汰旧状态时优先考虑队列。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和一个出栈序列判断出栈序列是否合法。很多人第一反应是套卡特兰数公式算数量但题目问的是这个具体序列合不合法公式帮不上忙。正确做法是模拟入栈出栈全过程用一个指针i指向当前要出栈的元素。遍历入栈序列的元素依次压入栈中。每次压入后循环检查如果栈非空且栈顶等于出栈序列当前指向的元素则弹出i。最后看是否所有出栈元素都匹配上。// 合法出栈序列判定核心C bool checkValidPopSequence(vectorint push, vectorint pop) { stackint 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²)。单调栈解法是// 每日温度单调递减栈栈内存下标不是温度值 vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint 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 循环队列满和空都是frontrear你用什么区分循环队列用数组模拟时最关键的问题是队空和队满时front和rear都相等。你必须选一种策略来区分。常见做法有三种牺牲一个存储单元当(rear1) % capacity front时认为队满。队空条件仍是front rear。有效容量是capacity-1。这是最推荐的实现简单。使用size计数器维护一个size入队时size出队时size--size0为空sizecapacity为满。代价是多维护一个变量。增加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)。核心思路队列里存的是数组下标且下标对应的数组值从队头到队尾单调递减。每次窗口移动做两件事淘汰过期元素队头下标小于等于当前窗口左边界时弹出队头。保持单调性从队尾开始把所有值小于等于当前元素的下标全部弹出然后把当前下标压入队尾。// 滑动窗口最大值单调队列模板C vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标值递减 vectorint 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(cinn)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环境是C03标准。写代码时尽量只用最基础的语法比如stackint、queueint、vectorint这些别一上来就C17的特性。我见过有同学因为用了结构化绑定在OJ上古编译器上报编译错误。做题之前花30秒看一下OJ的编译器版本和语言选项是高手和新手的习惯差距之一。4.6 构造测试用例的能力比刷题量更值钱栈队列的题AC与否往往取决于边界数据。我在刷完一轮之后意识到与其一个劲刷新题不如把做过的每一题总结出对应的杀手用例。比如括号匹配的杀手用例是)(和(()合法出栈序列的杀手用例是1 2 3配3 1 2不合法因为3弹出后不可能先弹1滑动窗口最大值的杀手用例是数组全相等。当你脑子里积累了一批这样的反例库你写代码时会自动去检查这些caseAC率会肉眼可见地提高。这也是做题报告里最值得记录的部分——你不是在刷题你是在采集反例标本。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数量而是养成了先画状态图、再写代码、最后造边界用例的做题习惯——这个习惯对后续刷任何算法题都有用。