最近集中把栈和队列的OJ题过了一遍从最简单的模板题栈的基本操作、链式队列入队与出队一路刷到变形题合法出栈序列判定、循环队列设计、表达式求值踩了不少坑也总结出一套审题和写代码的思路。这篇就当一份做题报告把每个考点怎么拆、代码怎么写不容易错、OJ上常见的Runtime Error和超时怎么排查一次性整理出来。不管你是刚开始学数据结构还是已经在为面试刷题栈和队列都绕不开。它们表面上看就是两种线性结构但几乎所有更复杂的算法题——单调栈、滑动窗口、表达式解析、消息队列的设计——底层都能落到这两个结构上。后面接触所谓全栈项目、线程池的阻塞队列、消息队列重复消费问题根源也在这里。所以这份报告我会直接按做题的顺序来写从最简单的模板题开始逐步拔高。1. 做题前先想清楚栈和队列到底在考什么很多同学一上来就刷题看到“栈”就想到先进后出看到“队列”就想到先进先出然后直接写代码。这个习惯其实很危险因为OJ考的不是你能不能背出定义而是你能不能识别出题目背后要用的数据结构。1.1 栈的核心特性与OJ最常见考察角度栈就一个特性后进先出LIFO。但就是这个特性能延伸出一堆考法。我在刷题时归纳了一下OJ里关于栈的题目大致可以分成四类第一类是基础操作题比如“栈的基本操作”给你一串入栈、出栈指令让你模拟。这种题基本就是送分题但要注意输入的空白字符和输出格式稍不注意就Presentation Error。第二类是括号匹配类题目。这种题考的是“最近匹配”的思想遇到左括号入栈遇到右括号判断栈顶是不是匹配的左括号。它用到栈的原因很直观——最后一个未匹配的左括号一定最先被匹配。这个思路做熟了后面做HTML标签配对、函数调用栈分析都能用上。第三类是单调栈类题目典型的有“每日温度”“下一个更大元素”。这类题目表面上你看不出栈的影子但本质是在维护一个单调递减或单调递增的栈用来快速找到左边或右边第一个比当前元素大或小的元素。我第一次做“每日温度”的时候用双重循环暴力解小数据能过大数据直接超时后来才知道要用单调栈把时间复杂度从O(n^2)降到O(n)。第四类是表达式求值类题目比如中缀表达式转后缀表达式或者直接用栈计算后缀表达式。这里有个热词叫“栈div除法”其实就是用栈做算术表达式求值时遇到除号要特别注意操作数的顺序。因为栈是后进先出弹出的时候第一个弹出来的是右操作数第二个才是左操作数很多人在这里把除数和被除数写反导致WA。1.2 队列的核心特性与OJ最常见考察角度队列的特性是先进先出FIFO对应到现实场景就是排队。OJ里队列的题目其实比栈要更“实用”一些因为它往往不只是考队列本身而是考你怎么在队列的基础上做文章。最简单的就是“链式队列入队与出队”这种模拟题让你实现一个队列然后给一串操作。这种题重点考察的是链表头和链表尾的操作特别是入队用尾插、出队用头删不要把方向搞反。再往上一个台阶是“循环队列设计”。循环队列考的其实是一个工程问题怎么用数组模拟队列同时避免“假溢出”。我第一次做循环队列的时候判空和判满的条件老是写不准确后来发现关键就两个一个是留一个空位来区分空队列和满队列另一个是取模操作要小心(rear 1) % capacity front才是满的条件。还有一类是单调队列比如“滑动窗口最大值”。这类题和单调栈类似但维护的是一个双端队列队列里保存的是有可能成为当前窗口最大值的元素下标。题目看起来很难但理解了“过期元素出队”和“新元素入队前先淘汰队尾小于它的元素”这两个操作代码其实很短。除了这些队列还有一个方向是“用队列模拟栈”和“用栈模拟队列”。这类题在面试里特别常考因为它们考的是你对两种结构本质的理解。用两个栈可以实现先进先出用两个队列也可以实现后进先出做题的关键是确定“辅助结构”的角色。2. 模板题和基础变形题从数组模拟到进阶设计刷栈和队列的OJ我强烈建议先把模板题老老实实写一遍哪怕你觉得很简单。因为模板题能帮你熟悉输入输出格式、边界条件、数组下标的习惯用法。这些基本功不扎实后面做复杂题会频频出现低级错误。2.1 栈的基本操作模板数组模拟和链表模拟OJ里栈的基本操作输入一般是这样的先给一个n表示有n个操作然后每行是一个指令比如push 5、pop、top、empty。这种题用数组模拟栈最简单定义一个数组stack和一个栈顶指针top注意top初始化为-1表示空栈。这里我给出一个用数组模拟栈的模板#include stdio.h #include string.h #define MAXN 100005 int stack[MAXN]; int top -1; // 栈顶指针-1表示空栈 void push(int x) { stack[top] x; } int pop() { return stack[top--]; } int isEmpty() { return top -1; } int peek() { return stack[top]; } int main() { int n, x; char op[10]; scanf(%d, n); while (n--) { scanf(%s, op); if (strcmp(op, push) 0) { scanf(%d, x); push(x); } else if (strcmp(op, pop) 0) { printf(%d\n, pop()); } else if (strcmp(op, top) 0) { printf(%d\n, peek()); } else if (strcmp(op, empty) 0) { printf(%s\n, isEmpty() ? true : false); } } return 0; }这段代码有几个细节要注意top初始化为-1那么压栈时就是stack[top] x先移动指针再赋值出栈时return stack[top--]先返回值再移动指针。这是最经典的写法不要记反。如果题目要求用链表模拟栈那就定义一个单链表每次在头部插入节点删除也从头部删除。这里我就不展开代码了因为实际OJ中数组模拟已经完全够用链表模拟更多是为了让你理解链表操作。2.2 链式队列入队与出队的实现细节链式队列是OJ里很喜欢考的一种基础题很多人觉得它比顺序队列复杂但其实只要抓住两个指针就够front指向队头节点rear指向队尾节点。入队就是在rear后面挂新节点然后把rear移动到新节点上出队就是把front指向的节点摘下来然后front后移。链式队列入队的核心代码大致是这样的#include stdio.h #include stdlib.h typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; void initQueue(LinkQueue *q) { q-front q-rear (QNode *)malloc(sizeof(QNode)); q-front-next NULL; } void enQueue(LinkQueue *q, int x) { QNode *s (QNode *)malloc(sizeof(QNode)); s-data x; s-next NULL; q-rear-next s; q-rear s; } int deQueue(LinkQueue *q, int *x) { if (q-front q-rear) { return 0; // 队列为空出队失败 } QNode *p q-front-next; *x p-data; q-front-next p-next; if (q-rear p) { q-rear q-front; // 队列中只剩一个节点时出队后修改rear } free(p); return 1; }我最初写链式队列时忽略了出队后只剩一个节点的情况结果rear还指向已经释放的节点下一次入队时直接把数据写进野指针程序直接崩溃。这个Bug很经典你在OJ上会表现为Runtime Error而且不好排查因为不是每次都能复现。所以每次出队后最好检查一下front-next是否为空如果为空说明队列已经空了应该让rear也重新指回头节点。2.3 设计题循环队列的判空判满循环队列是顺序队列的升级版。顺序队列用数组实现时如果rear已经到数组末尾即使前面有空位也无法继续插入这就是“假溢出”。循环队列通过取模运算让rear从头开始从而复用空间。设计循环队列时我建议留一个空位来区分空和满。如果不留空位空队列和满队列都可能是front rear会陷入二义性。具体的结构体可以这样设计typedef struct { int *data; int front; // 队头下标 int rear; // 队尾下标指向下一个插入位置 int capacity; // 数组容量实际存储元素最多 capacity - 1 个 } MyCircularQueue;初始化时front 0rear 0。判断满的条件是(rear 1) % capacity front判断空的条件是rear front。入队时先把元素写到rear位置然后执行rear (rear 1) % capacity出队时先取出front位置的元素然后执行front (front 1) % capacity。我在写循环队列的时候经常犯的一个错误是把取模运算加错了位置。比如入队时写成rear然后判断if (rear capacity) rear 0这样和取模是等价的。但如果你写成rear (rear) % capacity那就是先赋值后自增值就错了。我一般统一用rear (rear 1) % capacity这样语义清晰不容易出错。3. 经典OJ题目的实战复盘模板题写完之后就可以进入真正的实战环节了。这里我挑几道经典题目按从易到难的顺序来讲每道题我都会带上我当时踩过的坑和最终写出来的思路。3.1 括号匹配看似简单却总在边界上翻车括号匹配是我心目中“入门必刷”的题目。题目会给一个只包含(、)、[、]、{、}的字符串让你判断括号是否合法。解题思路是遇到左括号就入栈遇到右括号就判断栈顶是不是对应的左括号如果是就弹出否则直接判定不合法。遍历完整个字符串后还要检查栈是否为空如果栈不为空说明有左括号没有被匹配也不合法。代码我写了一个比较简洁的版本#include stdio.h #include string.h #include stdlib.h #define MAXN 10005 char stack[MAXN]; int top -1; int match(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } int isValid(char *s) { int len strlen(s); top -1; for (int i 0; i len; i) { if (s[i] ( || s[i] [ || s[i] {) { stack[top] s[i]; } else { if (top -1) return 0; // 右括号先出现不匹配 if (!match(stack[top], s[i])) return 0; top--; } } return top -1; } int main() { char s[MAXN]; scanf(%s, s); printf(%s\n, isValid(s) ? valid : invalid); return 0; }这个题目看着简单边界条件却非常多。我刷的时候遇到一个比较隐蔽的情况如果字符串里面有空格或者其他字符需要在判断前过滤掉有些OJ不会明确告诉你输入中是否有空白所以最好用fgets读取整行再手动剔除空白字符。3.2 合法出栈序列判定一个模拟栈吃透入栈出栈过程“合法出栈序列判定”是一道质量很高的题目。它给出一个入栈序列比如1 2 3 4 5再给出一个出栈序列比如4 5 3 2 1让你判断这个出栈序列是否合法。也就是说在入栈过程中你可以随时把栈顶元素弹出来问最终能否形成给定的出栈序列。这个题的做法非常巧妙用一个指针j指向出栈序列的第一个元素然后依次遍历入栈序列。每遍历到一个元素就把它压入栈中然后循环判断栈顶元素是否等于出栈序列中j指向的元素如果相等就弹出并且j后移一位。遍历完入栈序列之后如果栈为空说明出栈序列合法否则不合法。这里的关键点是每压入一个元素后要不断循环弹出能匹配的栈顶元素而不是只判断一次。因为可能弹出栈顶之后下一个栈顶又能和出栈序列的下一个元素匹配。我当时就在这里栽了跟头。我写了一个if而不是while导致类似“入栈1 2 3出栈2 1 3”这种情况判断错误。后来想明白了栈顶在弹出后可能会变大因为原本压在下面的元素露出来了所以必须用循环。这个方法其实就是用栈来模拟整个入栈出栈过程时间复杂度是O(n)空间复杂度是O(n)。我做题时的习惯是优先把这类“模拟过程”的题写清楚因为它的逻辑框架非常通用后面很多栈的应用题都能复用。3.3 表达式求值与栈div除法的两个坑表达式求值是栈的经典应用常见的形式是给你一个中缀表达式比如3 4 * 2 / (1 - 5)让你计算结果。这类题目我在OJ上刷过好几个版本有几个从初版到最终版踩过的坑值得单独说一说。第一个坑是中缀转后缀。正常做法是用两个栈一个存操作数一个存运算符。但有些题目直接给你后缀表达式让你计算这时候只需要一个栈就够了遇到数字就压栈遇到运算符就弹出两个操作数先弹出的是右操作数后弹出的是左操作数计算完再压回去。第二个坑就是热词里提到的“栈div除法”。计算除法时如果表达式里的除法是整数除法你直接写a / b没有问题但要注意弹栈顺序。假设后缀表达式是5 3 /那么应该先弹出3再弹出5结果是5 / 3。如果你写成先弹出5后弹出3再算3 / 5结果就完全是错的。这种错误在OJ上的典型表现是小数据碰巧能过数据一旦复杂答案差得离谱。第三个坑是除数为0。OJ的测试数据里经常藏这种边界你可能觉得题目不会那么变态结果它就在某个测试点给你放一个/0。所以每做一次除法都要判断右操作数是否为0如果是按题目要求输出错误或者返回特殊值。我在写表达式求值的时候还会顺手把运算符优先级用数组存好比如(: 1, -: 1, *: 2, /: 2)这样代码会比一堆if-else清晰很多。这个习惯后来做全栈项目、解析模板语法的时候也用得上。4. 顺序vs链式、内存与OJ报错排查刷OJ到一定量之后你会发现影响AC率的往往不是算法本身而是一些工程细节。比如你用顺序还是链式、数组开多大、局部变量定了多少个这些都可能造成编译错误、超时、栈溢出。4.1 顺序实现和链式实现怎么选顺序栈和链式栈从功能上说是等价的但OJ场景下我几乎无脑选顺序栈。原因很简单顺序栈用的是数组随机访问快而且没有频繁的内存分配和释放不管是时间还是空间上都更可控。链式结构最大的问题是每次malloc和free都有开销数据量大的时候这些开销会被放大。换到队列也一样如果题目给定的容器大小上限是已知的比如n 10^5那么优先用数组模拟开一个固定大小的数组用两个下标分别表示队头和队尾。但有一个例外如果题目要求支持动态扩容或者你必须实现一个“不限定容量”的队列那链式队列是更合适的方案。我在一些模拟类的OJ题里遇到过这种情况输入数据里面会出现非常多的连续push数组模拟的队列如果不提前扩容就会越界。所以我的选择标准是题目给了数据范围用数组模拟题目没说数据范围或者明确要求不设上限用链式。4.2 C语言实现中栈空间和内存管理容易忽视的细节热词里有一条很扎心“c语言局部变量越少 所占栈空间越小”。这个说法来自函数调用栈。每个函数执行时都会在栈上分配一块空间用来存放局部变量、参数、返回地址。如果函数里定义了一个很大的数组比如int a[1000000]这个数组就会直接占用调用栈空间。OJ的栈空间通常有限一不小心就栈溢出了。我自己有一次写递归深搜的题函数里定义了一个int[1000][1000]的二维数组作为辅助空间结果每次递归都复制一份很快就把栈炸了OJ直接报Segmentation Fault。后来我把这个大数组改成全局变量问题立刻解决。所以我在C/C刷题时一般遵循几个原则大数组尽量定义成全局变量或者在函数外用static修饰避免占用函数栈空间。递归深度大的时候优先考虑改为迭代或者显式用栈模拟。使用malloc之后记得free虽然OJ程序退出时会回收内存但如果你在一个长循环里反复malloc而不释放内存会一直涨最后超过OJ的限制。结构体按值传参时如果结构体很大最好传指针减少栈空间的拷贝。4.3 OJ常见错误类型与排查技巧刷OJ最痛苦的不是算法想不到而是代码明明本地跑得好好的提交上去却报错。这里我整理了一个常见错误速查表是我自己踩坑总结的错误类型可能原因排查方法Compilation Error语法错误、头文件缺失、函数名拼写错误查看编译器报错信息特别注意C和C的标准差异Runtime Error数组越界、野指针、除数为0、栈溢出检查所有数组下标范围检查递归深度检查每次除法操作Time Limit Exceeded算法复杂度过高、死循环计算时间复杂度检查循环是否有跳出条件Wrong Answer思路错误、边界条件没处理、初始化缺失构造边界测试数据加打印观察中间值Presentation Error输出格式不对比如多了空格或空行仔细比对输出样例重点看空格、换行、大小写我最常犯的是Runtime Error里的数组越界。有时候是因为在循环里写了 n多访问了一次数组边界有时候是top--之后忘记判断栈是否已经空。我的排查方法很简单先在本地用最大数据范围的数据跑一遍如果本地没问题再把代码里的数组大小调大一倍重新提交很多时候问题就消失了。另外很多OJ支持在代码里加#define DEBUG输出中间结果本地测试时保留提交时注释掉。我一般会在循环里输出关键的栈顶指针、队列头尾下标这样能很快定位是哪一步的状态不对。5. 刷题节奏、题目清单与复盘方法最后这部分分享一下我的刷题节奏和题目规划。栈和队列这个主题范围不大但是如果只看不做或者只做不总结效率会非常低。我把自己的做法整理出来你们可以直接参考。5.1 值得反复做的题目清单附平台如果只是想快速掌握栈和队列我建议按下面的顺序刷题题目类型代表性题目建议平台栈的基本操作栈的基本操作、栈的压入弹出序列东方博宜OJ、洛谷队列的基本操作链式队列入队与出队、约瑟夫问题东方博宜OJ、杭电OJ括号匹配有效的括号、括号生成LeetCode、洛谷循环队列设计循环队列LeetCode、OJ题库合法出栈序列栈的压入弹出序列、出栈序列合法性各类OJ单调栈每日温度、下一个更大元素ILeetCode单调队列滑动窗口最大值LeetCode表达式求值后缀表达式求值、中缀转后缀各类OJ比如热词里提到的“东方博宜OJ答案1065”“东方博宜OJ答案1168”我当时刷这类题目的时候其实不太建议大家直接找答案。这些题往往把入队、出队、统计队列长度、访问队首队尾元素全揉在一起一次操作错一个字符就凉了。最好的做法是自己搭好一个模板然后反复提交用OJ的评测结果当反馈。杭电OJ的1002、1020、1096也是很多新手会遇到的题虽然不全是栈和队列主题但它们是用来熟悉OJ输入输出格式的好素材。毕竟如果你连多组输入的while (scanf(...) ! EOF)都搞不定后面做题会非常痛苦。5.2 我的复盘方法一题多解与复杂度分析我做栈和队列的题目时很少只写一种解法。比较典型的例子是“用两个栈实现队列”我一开始写的是“入队时直接压入stack1出队时如果stack2为空就把stack1的所有元素倒进stack2”。后来我会再想有没有可能优化成摊还代价更低的方式如果题目允许一个栈专门存队尾元素一个栈专门存队头元素性能会不会更好这种一题多解的训练对面试尤其有用。复杂度分析也不能只看大O要具体到操作次数。比如用数组模拟栈时每次push是O(1)但用链表模拟栈时每次malloc也有常数开销。在数据量达到百万级的时候这两个常数差异会非常明显。我在复盘时还会做一张表记录每道题的“关键点”和“陷阱”。比如循环队列的关键点是判满和判空陷阱是取模运算写错合法出栈序列的关键点是循环弹出陷阱是只判断一次表达式求值的关键点是弹栈顺序陷阱是除数为0和整数除法截断。这张表在考前刷一遍比重新做十道题都有效。最后一个复盘技巧是故意写错代码然后看OJ会报什么错。比如把循环队列的判满条件故意改错提交一次发现WA把malloc的结果不判断是否为空提交一次发现Runtime Error。这样错误信息和代码特征之间就建立了关联下次看到报错很快就能定位到问题。这种方法比较刺激但确实有效。我个人在实际操作中的体会是栈和队列的OJ题其实是一个“熟能生巧”的过程。你不需要过人的天赋只需要把每一道经典题的代码反复写到“肌肉记忆”的程度然后不断总结边界条件和易错点。尤其是链式队列出队时对rear的特殊处理、循环队列中那个被浪费的空位、合法出栈序列判定里的while循环这些细节只要踩过一次坑就再也不会忘。希望这份做题报告能帮你在刷题的路上少走几步弯路早日把栈和队列变成自己的“舒适区”。