栈和队列OJ刷题全攻略：从基础操作到单调栈实战

1. 刷题前的思路梳理为什么我选择集中刷栈和队列说实话栈和队列这俩数据结构在OJ上属于看着简单、做起来百转千回的类型。很多人觉得它们不就是先进后出和先进先出吗但真正刷起来才发现从括号匹配到表达式求值从单调栈到滑动窗口题目的变体多到让人怀疑人生。我最近集中刷了一批栈和队列的OJ题目从简单的链式队列入队出队到复杂的合法出栈序列判定、循环队列设计再到单调栈压轴题前前后后做了几十道。这篇文章就是一份完整的做题报告把题型的套路、代码实现的取舍、以及那些不写进教科书里的坑一次性讲清楚。先说说这次刷题的整体思路。栈和队列的OJ题其实可以按照底层操作和算法思想两个维度来划分。底层操作就是基本的push、pop、入队、出队通常考察的是实现细节比如循环队列怎么判满、链式队列的指针怎么指、C语言里用数组模拟栈时栈顶指针的初始值到底是-1还是0。算法思想层面则更上一层楼比如用栈实现表达式求值、用队列实现BFS、用单调栈解决下一个更大元素、用单调队列解决滑动窗口最大值这些题的难点不在数据结构本身而在于什么时候用栈、什么时候用队列、怎么维护单调性。我的选题策略也很明确先覆盖基础操作题再挑战经典算法题最后刷几道综合题来串联知识点。具体来说基础操作题大概占了四分之一包括栈的基本操作、链式队列入队与出队、循环队列设计算法题占了一半多包括合法出栈序列判定、中缀转后缀、单调栈类的柱状图最大矩形和接雨水、单调队列类的滑动窗口最大值剩下的是一些变体题比如两个栈实现队列、两个队列实现栈、最小栈、用栈模拟递归等。这个结构的合理性在于栈和队列本质上是受限的线性表它们的核心考察点就是限制带来的特性以及如何利用这些特性解决特定问题。所以刷题时如果你只盯着API调用那基本学不到东西必须从底层实现到上层应用全部过一遍才能真正理解为什么递归要用系统栈、为什么消息队列能削峰填谷、为什么线程池的阻塞队列要选有界队列。这也是我在做题报告里一直强调的思路每道题做完都要反问一句这个场景在真实工程里对应什么。另外我特别想说一点栈和队列在OJ里经常被放到线性表这一章来考但各大OJ的出题风格差异很大。比如杭电OJHDU和华为OJOD机试更偏向输入输出格式的坑洛谷和力扣更注重算法思维的深度而东方博宜这类学校的OJ则常常拿基础操作题来考代码熟练度。所以如果是新手上路建议先在一个固定平台上把基础题刷透不要反复横跳。我在这次刷题过程中就深有体会同一道循环队列设计力扣上只需要实现类方法而在某些OJ上还要自己处理多组输入输出细节完全不同。2. 栈的OJ核心题型从基本操作到合法出栈序列判定2.1 栈的基本操作数组模拟与链表模拟的取舍栈的基本操作题说白了就是考你push、pop、top、isEmpty这几个动作怎么实现。很多OJ上的第一道栈题都是这个套路。用数组模拟栈是最常见的做法一个一维数组加一个栈顶指针就搞定了。但这里有个特别容易被忽视的细节栈顶指针的初始值。如果你用C语言写栈顶指针top初始化为-1那么push的时候要先top再赋值如果初始化为0那就要先赋值再top。这两种写法在OJ上都能过但很容易因为混淆而出bug。我个人习惯用top -1的写法因为这样栈空的判断条件就是top -1逻辑上更直观而且后续如果要实现获取栈中元素个数直接返回top 1就行不用再额外处理偏移。还有一个选择是用链表模拟栈。链表栈的好处是没有大小限制不会出现栈满的情况但代价是每个节点要额外存储一个next指针。OJ做题时我一般优先用数组模拟因为数组的随机访问效率高而且不会因为频繁malloc/free带来性能抖动。但如果是遇到那种内存限制特别严格的题数组模拟反而更可控因为链表节点本身还有内存对齐的开销。不过数组模拟栈有一个致命问题栈满溢出。在OJ上题目通常会给一个相对宽松的栈大小上限但如果你在解题时没有预先估算最大深度很容易出现数组越界。比如某些模拟题数据范围是10^5但你只开了10^4的数组提交后就是Runtime ErrorRE。我踩过这个坑后来养成了习惯凡是模拟栈数组大小至少开数据范围上限加5宁可浪费一点空间也不要越界。2.2 合法出栈序列判定不光会模拟还得会推理合法出栈序列判定是我认为栈这章里最有意思的一道题。题目描述很直接给定入栈序列1到n再给一个出栈序列判断这个出栈序列是否合法。最经典的解法就是用一个辅助栈模拟入栈和出栈的过程用一个指针指向出栈序列的当前位置遍历入栈序列每次把一个元素压入辅助栈然后检查辅助栈栈顶是不是等于当前出栈元素如果相等就弹出并且出栈指针后移注意这里要用while循环因为可能连续弹出多个元素。最后检查辅助栈是否为空且出栈指针是否已经走完整个出栈序列。我当时做这道题的时候一开始想的是直接判断是否存在逆序对之类的数学性质后来发现模拟法才是最稳妥的。不过模拟法的时间复杂度是O(n)空间复杂度是O(n)存储辅助栈对于10^5规模的数据完全没问题。但在OJ上提交时我发现有一个隐藏考点如果出栈序列中有重复元素还能不能简单地用上面的模拟法答案是如果题目保证入栈序列和出栈序列都是排列即1到n各出现一次那模拟法没问题但如果允许重复元素就需要更复杂的判定方法了。好在绝大多数OJ上这道题都是排列版本模拟法就够用了。这道题还有一个常见的变体已知入栈序列求所有可能的出栈序列个数这其实是个卡特兰数问题n个元素的出栈序列总数是卡特兰数C(2n, n)/(n1)。如果不理解这个公式可以想象成每个元素必须先进后出且出栈序列必须满足某种括号匹配的约束。这个变体虽然不常直接考代码但很多判断合法出栈序列的证明题都会用到这个思想。我当时在做完这道题之后顺手做了一道同类型的题给定一个字符串判断它是否是某个合法出栈序列的结果比如abc入栈后合法出栈序列有abc、acb、bac、bca、cba但不包括cab。这种题其实就是同一个模拟思路但出题人把背景包装成了字符串操作一开始很容易被绕晕。我给的建议是不管题目怎么包装看到入栈出栈序列相关字样第一反应就应该是辅助栈模拟。2.3 中缀表达式转后缀与表达式求值栈在计算器里的经典应用表达式求值是栈的又一个经典考题。常见的有两种考法一种是让你把中缀表达式转成后缀表达式逆波兰式另一种是直接给一个后缀表达式让你求值。两个过程都依赖栈的核心性质操作符的优先级和括号匹配。中缀转后缀的规则不复杂但细节多。它的核心思路是用一个栈保存操作符遍历中缀表达式遇到操作数直接输出遇到操作符时如果栈顶操作符的优先级大于等于当前操作符就把栈顶弹出并输出然后重复这个过程直到栈顶优先级小于当前操作符或栈为空再把当前操作符压入栈遇到左括号直接压栈遇到右括号则不停弹出栈顶并输出直到遇到左括号再把左括号弹出不输出。最后把栈里剩下的操作符全部弹出。这个算法我在书上看过无数次但真正在OJ上动手写的时候还是踩了不少坑。第一个坑是负数问题比如-35这种表达式如果直接把-当作减号处理会出问题。处理办法有两种一是在转换之前先判断当前字符是不是负号并且它的前一个字符是操作符或左括号如果是就把负号和后面的数字一起当作一个操作数二是把中缀表达式做预处理在负号前补一个0把-3变成0-3。我推荐第二种因为实现起来不容易漏。第二个坑是数字可能是多位数甚至带小数点。OJ题里如果只给单数字0-9那处理起来很简单但如果是12345这种就要注意解析连续数字。我的做法是用一个循环读取连续的数字字符或小数点组成完整的操作数之后再进行后续处理。这看起来简单但忘记处理的话写出来的代码会错误地输出1 2 3 4 5而不是123 45 。后缀表达式求值就简单多了遇到操作数压栈遇到操作符就弹出两个操作数然后根据是加减乘除还是乘方进行运算最后把结果压回去。这里有个特别容易出错的地方减法和除法的顺序问题。弹出的是b和ab先弹出、a后弹出那么做减法时应该计算a - b做除法时应该计算a / b。我一开始没有注意直接把b - a了结果怎么调都错最后把两个出栈变量的名字改成a和b、再往算式里一填才恍然大悟。2.4 单调栈从下一个更大元素到接雨水、柱状图最大矩形单调栈是栈这个数据结构在算法层面的高光时刻。所谓单调栈就是栈内元素从栈底到栈顶保持严格单调递增或递减。它最经典的应用场景是找到数组中每个元素左边或右边第一个比它大或小的元素时间复杂度是O(n)。我想用一个热词里提到的每日温度题来说明。给定一个数组temperatures返回一个数组answeranswer[i]是指对于第i天下一个更高温度出现在几天后。如果不存在就为0。用单调栈的做法是维护一个从栈底到栈顶递减的栈遍历数组的时候如果当前元素大于栈顶元素就说明栈顶元素找到了右边第一个比它大的元素此时答案就是当前索引减栈顶索引然后弹出栈顶继续比较如果当前元素小于等于栈顶元素就把当前索引入栈。这个等号不入栈的细节很关键因为题目问的是严格更高温度所以相等的天数不能算。做单调栈题目时我建议先在纸上演算一遍再写代码。比如柱状图中最大的矩形这道题思路是用单调栈维护一个递增序列对于每个柱子以它作为高度能延伸到的最左和最右边界分别由左边第一个比它矮的柱子和右边第一个比它矮的柱子决定。如果不用单调栈暴力法是O(n^2)n是10^5就直接TLE了用了单调栈时间复杂度降到O(n)空间复杂度O(n)。接雨水也是同样的套路只是换了个方向每个位置能接的雨水量由左边最高的柱子和右边最高的柱子中较小的那个减去当前柱子的高度决定。用单调递减栈来维护当遇到一个比栈顶高的柱子时就可以计算栈顶位置能接的雨水了。这道题如果在OJ上看到我建议先别急着看题解自己用纸笔模拟一遍4,2,0,3,2,5这个数组你会明白单调栈为什么能在弹出时同时确定左右边界。2.5 最小栈与双栈实现队列设计题里藏着编程思维最小栈是一道很有意思的设计题。题目要求实现一个栈除了常规操作外还要能O(1)的时间获取栈中最小元素。最经典的解法是用两个栈一个正常存数据另一个栈存当前的最小值。每次入栈时把当前元素与辅助栈的栈顶比较如果当前元素更小就把当前元素压入辅助栈否则就把辅助栈栈顶再压一遍。这样两个栈的高度始终一致pop的时候同步弹出即可。但也有一种空间优化方案辅助栈中不需要存重复的当前最小值只有在遇到比当前最小值更小的元素时才压入pop的时候如果弹出的元素等于辅助栈栈顶就把辅助栈也弹出一个。这个优化能把空间复杂度从最坏O(n)降到最好O(1)如果数据都是递增的。OJ上两种写法都能过但后者如果处理相等元素不好会出现bug——比如连续入栈两个相同的最小值第二次pop时辅助栈栈顶已经被弹掉了再pop时就会出错。所以我建议新手先用最朴素的同步栈写法稳。两个栈实现队列这道题基本是面试必考题。思路是用一个输入栈和一个输出栈入队时直接push进输入栈出队时如果输出栈为空就把输入栈的所有元素依次弹出并压入输出栈然后从输出栈弹出栈顶。这样做的原理是两次栈的后进先出操作抵消之后数据的顺序就变回了先进先出。这里有个容易忽略的性能细节只有当输出栈为空时才做搬运操作可以均摊时间复杂度达到O(1)。我试过如果不做这个优化、每次出队都先把输入栈全清空再搬回来那性能会退化到O(n)。3. 队列的OJ核心题型从链式队列入队出队到滑动窗口最大值3.1 链式队列入队与出队指针操作是重灾区链式队列是许多学校OJ的基础题特别是那些强调C语言指针的OJ。题目会让你定义一个链表节点结构体然后实现初始化队列、入队、出队、判断队列是否为空等函数。看起来简单但很多人死在尾指针上。链式队列的经典结构是一个头指针front指向队头节点一个尾指针rear指向队尾节点。入队时需要创建一个新节点然后把当前尾节点的next指向新节点再让rear指向新节点。这里有一个非常容易漏掉的细节如果队列原本为空front和rear都指向NULL入队时front也要指向新节点否则后续出队时front仍然为空程序就会崩溃。出队时就更麻烦了。首先要把队头节点保存下来怎么保存很多新手会写成free(front)然后把front front-next。问题是front-next在free之后已经变成野指针了你怎么还能访问它正确做法是先用一个临时指针temp保存要出队的节点让front向后移再free(temp)。另外出队后如果队列变为空要把rear也置为NULL否则rear会变成一个悬空指针后续再次入队时会出现队尾指针指向已释放内存的问题。我做一个形象的比喻链式队列的front和rear就像是两个一前一后的游标front负责消费出队rear负责生产入队两者必须时刻保持同步。如果rear没有在队列为空时跟front一起移动就好比生产线的入口标记还停留在已经被拿走的空箱子上下一批货物进来时工艺就会错乱。3.2 循环队列判空判满的四种哲学循环队列是为了解决顺序队列假溢出问题而设计的。所谓假溢出就是数组前面还有空间但因为rear已经指向数组末尾导致无法继续入队。循环队列通过取模操作让rear和front在数组范围内绕圈把数组当作一个环形缓冲区。实现循环队列时最大的坑是如何判断队列是空还是满。因为环形结构里front rear既可以是空也可以是满。常见的解法有四种第一种牺牲一个存储单元。让rear指向最后一个元素的下一个位置当(rear 1) % capacity front时判定为满当front rear时判定为空。这是最经典的写法缺点是浪费了一个数组空间。第二种增加一个size变量记录当前队列中元素个数。入队时size出队时size--判断空就是size 0判断满就是size capacity。这种办法最直观也不浪费空间但需要额外维护一个变量。第三种增加一个flag标记记录上一次操作是入队还是出队。当front rear时如果上一次是入队则为满如果上一次是出队则为空。第四种使用计数器或时间戳。我在OJ上写循环队列的时候默认选择第一种浪费一个空间的写法因为代码最简洁而且我可以提前把数组开大一位来抵消浪费。但如果是那种严格限制容量的题目就要用第二种size变量法。还有一点需要注意取模运算在C/C里对于正负数的行为如果数组下标可能为负记得先加capacity再取模不然很容易出现负数下标越界。3.3 单调队列与滑动窗口最大值单调栈的孪生兄弟队列的算法题里最高频的应该是滑动窗口最大值经典题Sliding Window Maximum。给定一个数组和一个窗口大小k窗口每次向右滑动一位要求输出每个窗口内的最大值。暴力法是O(n*k)在OJ上10^5的数据就直接超时。标准解法是用单调递减队列队头到队尾递减。实现思路是用一个双端队列deque存数组的下标不是值。遍历数组时每到一个新元素先检查队头是否已经滑出窗口范围如果滑出就弹出然后从队尾开始把所有小于等于当前元素的下标全部弹出因为那些元素不仅比当前元素旧值还比当前元素小它们在后续窗口里永远不可能成为最大值最后把当前下标压入队尾。这样队头始终是当前窗口最大值的下标直接取对应值即可。这道题和单调栈很像但有一个本质区别单调栈是永不回头的处理完一个元素之后就再也不会用到而单调队列是有过期概念的队头元素会因为窗口滑动而失效。所以我在做这道题时特别容易忘记判断队头是否还在窗口内这一步导致用过期的最大值输出。排查的方法很直接看答案是逐位右移的如果某一步答案突然变小了十有八九就是队头过期没清理。这里我推荐一下双端队列deque。虽然也可以用数组模拟一个dequehead指针加tail指针但要同时支持头尾的弹出比较麻烦。C的std::deque或者Python的collections.deque都能直接完成任务。3.4 两个队列实现栈与层序遍历队列的另类应用两个队列实现栈和两个栈实现队列是一对镜像题目。两个队列实现栈的思路是入栈时把元素压入非空的那个队列出栈时把非空队列的前n-1个元素依次出队并入队到另一个队列然后把最后一个元素出队。也就是说每次出栈都要倒腾一次队列。如果题目额外要求top操作就需要注意用一个变量记录最后一个入队的元素top操作直接返回这个变量即可不必倒腾队列。队列在二叉树层序遍历BFS里的应用也是OJ高频题。用队列做层序遍历的思路特别朴素先把根节点入队然后循环处理取出队头节点访问它把它的左孩子和右孩子依次入队。这样每一层的节点都是按顺序被访问的而且队列天然起到了分层缓冲区的作用。如果题目要求按层输出通常会在循环里记录当前队列的大小size然后连续出队size次这样就能把每层的节点一次处理完。我在做题报告里把两个队列实现栈和BFS层序遍历放在一起是因为它们的共同点在于用队列的先进先出特性来改变或维持数据顺序。前者是利用队列的FIFO来模拟LIFO后者是利用FIFO来保证同层节点的相对顺序。理解了这个本质后续遇到生产者消费者模型、消息队列削峰填谷之类的工程问题时思路会通畅很多。4. 实战过程从读题到AC的完整流程拆解4.1 审题与数据规模评估拿到一道栈或队列的OJ题我从来不直接上手写代码。我会先把题读三遍把输入输出样例在纸上亲手跑一遍然后判断数据规模。这一步在很大程度上决定了这道题的解法到底是模拟还是上算法。举个例子如果题目说n 1000那O(n^2)的暴力法完全可行如果n 10^5你就必须考虑O(n)或O(n log n)的解法否则必然TLE。栈与队列的题目通常n在10^5上下所以单调栈、单调队列这种O(n)算法基本是默认解。另外还要注意输入输出方式如果数据量很大C的cin/cout记得关闭同步ios::sync_with_stdio(false); cin.tie(0);否则输入就卡掉很多性能。还有一点容易被忽略栈和队列的题内存限制往往比较严格。比如链式队列如果每个节点都malloc一次在循环里频繁分配释放容易造成内存碎片在极端情况下可能导致超出内存限制。所以我在OJ上如果可以选择数组模拟就优先用数组模拟。实测下来数组模拟比链表实现不仅代码短而且Bug少。4.2 核心代码实现以滑动窗口最大值为例的完整解析我拿滑动窗口最大值这道题来完整走一遍代码实现。以C为例使用deque存储下标#include bits/stdc.h using namespace std; vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标维护队头到队尾递减 vectorint ans; for (int i 0; i nums.size(); i) { // 弹出滑出窗口的下标 if (!dq.empty() dq.front() i - k) { dq.pop_front(); } // 从队尾弹出所有 当前值的下标 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 从第k-1个位置开始窗口形成 if (i k - 1) { ans.push_back(nums[dq.front()]); } } return ans; }这里有几个地方值得说明。首先是if (!dq.empty() dq.front() i - k)这一步队头元素如果已经不在窗口内也就是下标小于等于i-k必须弹出。注意这里用的是而不是因为下标为i-k的元素恰好是窗口左边界前一个元素已经滑出。其次是后面的while循环把所有小于等于当前值的下标全部弹出确保严格递减这样队头必然是当前窗口最大值。最后i k-1时才输出因为前k-1个元素还没凑够一个窗口。我当时的代码一开始没写而写了导致窗口左边界元素没被清理干净提交后WA了两次。排查的过程也很有意思我打印出deque的所有内容发现里面出现了窗口外的下标这才意识到是边界条件的问题。所以刷这种含下标计算的题强烈建议在本地手动模拟一遍把下标写出来逐一验证。4.3 空间换时间的思维辅助栈、辅助队列的正确打开方式栈和队列题目中许多优化都建立在空间换时间的基础上。比如最小栈里那个辅助栈比如队列实现栈时的两个队列比如单调栈里的存储下标——本质上都是用一个额外的空间结构来记录历史信息。我在做题过程中观察到很多初学者会陷入一个误区总想着能不能不用额外空间结果把代码写得极其复杂最后还是没有AC。实际上OJ做题卡的是时间复杂度和空间复杂度上限在大多数题目里O(n)的额外空间完全在允许范围内不用刻意节省。真正应该在意的是你的解法能不能在限制内跑完。空间换时间是一种非常成熟的工程思路栈和队列本身就是数组或链表的限制版再加一个辅助结构是很自然的事情。但我也会区分纯冗余空间和算法必要空间的区别。比如用数组模拟栈时数组的大小通常需要开满数据规模那是必要的但如果你的辅助栈里存了一堆永远用不到的元素那就需要考虑优化。以最小栈为例同步辅助栈写起来简单但数据如果全递增辅助栈里全是重复的最小值空间白白浪费优化成只在更小值出现时入栈、只在弹出元素等于栈顶时出栈空间效率会好很多。这类看起来简单但其实有优化空间的题目正是OJ题目的魅力所在。4.4 递归转栈系统栈的替代方案在栈的OJ题里偶尔会遇到一种用栈模拟递归的题比如用非递归方式实现二叉树的前序/中序/后序遍历。这类题的本质是把系统为递归调用维护的调用栈手动用栈来模拟。以前序遍历为例非递归写法非常简单先压入根节点然后循环弹出栈顶并访问接着先压入右孩子、再压入左孩子因为栈是LIFO先压右孩子出栈时左孩子先被处理。这个顺序背后的原理是访问根节点后下一步想要访问左子树所以左孩子必须后进栈但先出栈。中序遍历就稍微复杂一点因为要先访问左子树再访问根再访问右子树。常见做法是用一个指针cur沿着左子树一路走下去沿途把节点入栈当cur为空时弹出栈顶并访问然后cur指向弹出节点的右孩子。这个过程本质上就是在模拟递归函数压栈后继续深入到底后再逐层返回并访问的完整流程。如果对递归的调用栈有深刻理解写这个非递归版本会非常顺畅反过来写多了非递归版本也会对系统栈这个概念有更深入的认识。我印象很深的一道题是二叉树的后序遍历非递归版它是最容易写错的。因为在后序遍历中必须等到左右子树都访问完之后才能访问根节点所以你需要在节点里标记是否已经访问过右子树。我当时的做法是用两个栈实现或者用一个栈加一个lastVisited指针。如果只是想AC两个栈的做法最简单第一个栈按根、右、左的顺序压入和先序遍历镜像再把第一个栈的内容依次弹出压入第二个栈最后从第二个栈弹出得到左右根的后序遍历顺序。这个方法虽然多用了空间但逻辑极清晰不容易错。5. 做题中的高频问题编译错误、运行错误与超时全排查5.1 Runtime ErrorRE数组越界和栈溢出在栈和队列题目中RE最常见的原因就是数组越界尤其是数组模拟栈和队列时。比如栈顶指针在pop时没有判空直接top或top--就很可能越界。另一个常见原因是递归深度过大导致的系统栈溢出比如某些树上递归DFS题目如果递归深度超过系统限制就会爆栈。我记得有一道树的中序遍历要求非递归实现我一开始偷懒用了递归结果n是10^5的链状树直接把系统栈压爆了OJ返回RE而不是TLE。从那以后我凡是遇到深度不确定的递归都先考虑改用栈模拟。在OJ提交时如果出现RE最快的排查方式是在本地用同样的数据规模跑一遍加入断言或打印定位是哪一行越界。但更推荐的做法是在写代码的时候就把判空边界写在前面防患于未然。5.2 Time Limit ExceededTLE为什么暴力过不了TLE是栈和队列题里最常见的惩罚。如果你写的是两层循环遍历而数据规模是10^5那几乎是必挂的。手感很重要一般OJ的时间限制是1秒约等于10^8次简单运算。O(n^2)在n10^5时是10^10次运算妥妥超时O(n)在n10^6时只有10^6次稳过。我做的接雨水那道题第一时间想到的就是对每个位置向左右分别扫描找最大高度这是O(n^2)。本地测试用n1000的数据没有问题但OJ后台的测试点直接给了10^5提交就TLE了。后来我切换到双指针解法时间降到了O(n)秒过。TLE之后不要急着优化常数而是先想清楚复杂度是不是量级上的问题。如果复杂度已经最优了才考虑IO优化、减少无用的vector拷贝等技术细节。5.3 Wrong AnswerWA边界条件和相等元素怎么处理WA的原因多种多样但栈和队列题出错最多的地方是边界条件。比如合法出栈序列判定中如果出栈序列还没遍历完但入栈序列已经全部压完此时栈顶不等于出栈指针所指元素就应直接判定为非法。这个提前返回的逻辑如果漏写就会导致死循环或错误输出。另一个经典WA来源是相等元素的处理。比如单调栈里如果允许小于等于与小于的区别没注意答案就会偏差。还是以每日温度为例如果题目问的是下一个温度更高那么相等的温度就不能算数所以while循环里要严格使用temperatures[i] temperatures[st.top()]如果你写成了相等温度的日子就会被错误地计入答案。解决这个问题的办法很简单做题时把题目中的严格大于大于等于小于这些词全部圈出来代码里对应写清楚。5.4 编译错误OJ平台与本地环境的差异有时候本地编译通过复制到OJ上却编译错误。最常见的原因是头文件和语法标准不同。老OJ平台用C98不支持C11的新特性比如auto、unordered_map、std::stoi等新OJ平台普遍支持C17反而要注意某些老式写法如gets已经移除。另外如果你用bits/stdc.h在部分OJ上可能无法编译因为它不是标准C头文件。我到外地某个学校的OJ刷题时就遇到过这个问题最后老老实实改成独立头文件才过。还有一个小坑是变量名。在本地用left、right、data这些作为变量名没问题但有些OJ的全局变量或者系统头文件里可能已经定义了同名符号就会编译冲突。我的经验是做题时变量名尽量加前缀比如stk、que、pCur既清楚又安全。5.5 栈和队列OJ常见错误速查表问题类型常见原因排查与解决建议RE数组模拟栈/队列越界push/pop前先判满/判空数组大小开上限5RE递归深度过大爆栈改用栈模拟递归或显式增大栈空间若OJ允许TLEO(n^2)暴力过大数据改用单调栈/单调队列/双指针等O(n)算法TLE输入输出太慢C关闭同步、用scanf/printf代替cin/coutWA边界条件没处理检查队列空/满、栈空/满、窗口未形成时的情况WA比较符号用错严格大于/大于等于/小于等于按题目原文字面写WA相等元素处理不一致单调栈/队列的出栈条件需明确写清楚CE使用了不兼容的头文件或语法换成标准头文件避免bits/stdc.h注意C版本CE变量名与系统宏冲突用有前缀的变量名如stkTop、queFront说实话这张表里我最想强调的还是那一行比较符号用错。我后来统计过自己刷的五十多道栈和队列题WA的原因里有三分之一都是这种差一个符号的问题。不是不会是真的不细心。后来我养成了一个习惯写完代码之后把题目里的比较条件用中文写在注释里再对着代码逐一核对错题率立刻降了不少。6. 做题心得与实践建议栈和队列在数据结构里看起来是最简单的部分但它就像是大楼的地基任何复杂的算法最终都可能在某个环节用到这两个受限的线性表。刷完这一批OJ题我有几点体会想分享给后来者。第一别只看题解视频一定要动手敲。我做合法出栈序列判定的时候以为看懂了模拟过程就会了结果在OJ上写的时候还是卡了很久尤其是while循环连续弹出这一步代码里少写一个while根本意识不到。只有自己写出了AC代码这个题的思维才算真正建立起来。第二重视时间复杂度和空间复杂度的分析。栈和队列题特别容易让初学者产生我能用数组和链表做出来就行的想法但OJ判题器不会惯着你。每做一道题都问自己三个问题这个解法最坏情况下复杂度是多少数据规模巅峰时跑得动吗有没有更优的解法这三个问题能帮你从写出代码进步到高效解题。第三画图永远是排错的第一利器。栈的弹出顺序、队列的入队出队、单调栈的逐步收敛在纸上画一遍比盯着代码发呆高效十倍。我到现在遇到复杂一点的单调栈题目还是先在草稿纸上把下标和值写成一列再模拟入栈和出栈差不多能一次AC。第四刷题要有总结。我在做题报告里会把每道题的解法思路、代码模板、常犯错误整理成笔记。比如单调栈有两种写法找左边更大/更小的用递增栈找右边更大/更小的用递减栈注意方向这样的模板句关键时候能救命。做OJ题目到底是什么它不只是刷题而是在锤炼你建模、分析和优化的能力。栈与队列这两块恰恰是这些能力的绝佳训练场。把这些基础打扎实后面再看AVL树、跳表、哈希表甚至工程里的消息队列和线程池思路都会顺很多。