企业官网建设流程全解析

最近集中把栈和队列的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 = 0，rear = 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最痛苦的不是算法想不到，而是代码明明本地跑得好好的，提交上去却报错。这里我整理了一个常见错误速查表，是我自己踩坑总结的：

我最常犯的是Runtime Error里的数组越界。有时候是因为在循环里写了<= n，多访问了一次数组边界；有时候是top--之后忘记判断栈是否已经空。我的排查方法很简单：先在本地用最大数据范围的数据跑一遍，如果本地没问题，再把代码里的数组大小调大一倍重新提交，很多时候问题就消失了。

另外，很多OJ支持在代码里加#define DEBUG输出中间结果，本地测试时保留，提交时注释掉。我一般会在循环里输出关键的栈顶指针、队列头尾下标，这样能很快定位是哪一步的状态不对。

5. 刷题节奏、题目清单与复盘方法

最后这部分分享一下我的刷题节奏和题目规划。栈和队列这个主题范围不大，但是如果只看不做，或者只做不总结，效率会非常低。我把自己的做法整理出来，你们可以直接参考。

5.1 值得反复做的题目清单（附平台）

如果只是想快速掌握栈和队列，我建议按下面的顺序刷题：

比如热词里提到的“东方博宜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循环，这些细节只要踩过一次坑，就再也不会忘。希望这份做题报告，能帮你在刷题的路上少走几步弯路，早日把栈和队列变成自己的“舒适区”。