企业官网建设流程全解析

第一次在在线判题系统里看到“oj3335 数据结构实验之栈与队列八：栈的基本操作”这个题目时，我其实没怎么当回事。栈嘛，初始化、入栈、出栈、取栈顶，翻来覆去就那点东西，心里想着十分钟就能收工。结果真正动手写才发现，这道题完全不是“背一遍代码”就能过的。它是那种看着基础、做起来全是细节的题，把栈的实现方式、边界处理、输入输出规范、甚至函数传参的写法全搅在一起，稍微有一个地方没想过，就是段错误或者格式错误等着你。

这篇文章就把我当年做这道题时踩过的坑、最后整理出来的实现方式、以及对“栈的基本操作”这道题背后考察意图的理解一起写出来。不管你是刚学数据结构的学生，还是准备面试想快速过一遍栈的底层的开发者，这篇应该都能给你一些实在的东西。

1. 初见这题：题面很短，陷阱不少

1.1 题面信息与核心考点提取

题目名称里写着“栈的基本操作”，标签里带“栈与队列”，实际内容就是模拟一个栈，执行若干条指令，输出对应结果。不同OJ上题面细节会有点差别，我做过的那一版大概是这样的：先输入一个整数 n，表示后面有 n 条操作指令，指令分成四种：push x代表把整数 x 压入栈，pop代表弹出栈顶元素，top代表查看栈顶元素的值，empty代表判断栈是否为空。

听上去很简单是不是？但你要真是只会照着教材敲一个栈，这道题大概率过不了。因为实验课后面的 OJ 题，从来不是只考“你会不会写栈”，而是考“你能不能在不崩、不漏、不越界的前提下把这个栈用对”。它隐含的考点至少有三个：栈顶指针的表示方式、空栈边界操作如何处理、以及多组测试数据下栈状态要不要重置。这三个点看起来不起眼，实际上就是AC和WA的分界线。

1.2 操作类型与边界条件解读

把指令拆开看，核心操作就三类：写入（push）、删除（pop）、读取（top/empty）。这里面的坑在于：当你对一个空栈执行 pop 或 top 时，程序到底该怎么表现？有的题面要求输出一行“error”，有的可能要求什么都不输出。这直接决定了你代码里返回值的设计，不能抱着“反正不会出现这种输入”的侥幸心理，测试数据里一定会给你塞几条空栈操作的。

再看题目的小标题，“数据结构实验之栈与队列八”，不难猜到这是某个系列实验课的第八题。这种系列题的特点是：前面几道多半是顺序表、链表，到了栈这里开始强调 ADT（抽象数据类型）层面的操作规范。也就是说，老师真正想让你练的，是用代码把“后进先出”这个逻辑完整实现出来，而不是让你写一个能跑就行的死循环。理解了这层，就不难明白为什么很多学校的实验题会专门规定“不允许直接调用 STL 里的 stack 容器”了。

2. 数组栈还是链式栈：OJ场景下的选型逻辑

2.1 数组栈：为什么绝大多数OJ题首选它

实现栈有两条主路：数组栈和链式栈。先说数组栈，它的原理是用一块连续内存加一个栈顶指针。top 指向当前栈顶元素的位置（或者下一个空位，两种写法都可以），入栈就把数据写进 top 指的地方再调整 top，出栈就把 top 往回退。整个过程时间复杂度 O(1)，代码四五行，逻辑一目了然。

在 OJ 场景下，数组栈还有一个隐形优势：内存是预分配的，不会频繁调用动态内存分配函数。别小看这一点，在线判题系统跑数据的时候，栈操作可能达到十万甚至百万次，如果每次 push 都去 malloc 一个节点，那时间开销和内存碎片问题都会跳出来。就算题目数据量不大，预分配的数组也能让程序行为更稳定，不容易出幺蛾子。

2.2 链式栈：什么场景下才值得用

链式栈也有它的地盘。它的优点是不用提前规定容量，内存按需分配，数据规模不确定或者变化很大的时候更灵活。“栈的容量到底有多大”这个问题在数组栈里是个隐患，在链式栈里根本不存在的。

但代价也很明显：每个节点都要额外存一个指针，代码量会膨胀一截，而且节点申请和释放的时机只要没处理好，就是内存泄漏或者悬空指针。对实验课的 OJ 题来说，判题系统一般会限制时间，但真正卡住你的一般不是时间而是正确性。链式栈实现时容易出现“函数内改了指针但外面没变”的问题，我在后面会详细讲。所以我的建议是：OJ 题里没有明确考“链式栈实现”的时候，优先写数组栈；只有在题目本身要求掌握链式结构，或者你明知道数据量会撑爆固定数组时才考虑链式栈。

2.3 STL的stack也能用，但这不是这道题的目的

很多人一开始会直接#include <stack>，然后stack<int> st;一套带走。你要说能不能过，那在部分OJ上确实能过，但如果实验题明确说“要求实现栈的基本操作”，这个做法本质上是绕过了考察点。数据结构实验的目标是让你把栈的内部结构亲手搭一遍，理解栈顶指针是怎么移动的、判断空栈到底是判断什么。

我自己当年做的时候，先老老实实用 C 语言手写了一个数组栈，AC 之后又尝试着用 STL 里的 stack 实现了一遍，两相对比，体会特别深。STL 版本十几行就写完了，但手写版本让我真正想明白了一个问题：top == -1和top == 0到底差在哪里。

3. 手写一个能一次通过的数组栈：完整代码与逐段拆解

3.1 结构体设计与top指针的两种初始化

数组栈的结构体可以这样定义：

#define MAXSIZE 100000 typedef struct { int data[MAXSIZE]; int top; } Stack;

这里的MAXSIZE怎么定，需要结合题目给的数据范围。如果题目没明说n的上限，就按常见的 1e5 或者 1e6 去开。有的同学喜欢把数组开得特别大，比如 10000000，结果 MLE 了，这也是经验不足的表现。稳妥的做法是预估栈的深度最多跟操作数一致，操作数多大，栈数组就开多大。

top 的初始化有两种常见风格，很多人混着用就出问题了。第一种是top = -1，表示栈里没有元素，top 永远指向当前栈顶元素的位置。入栈时先top++再写入data[top]，判断空栈的条件是top == -1，判断满栈的条件是top == MAXSIZE - 1。第二种是top = 0，表示 top 指向下一个空位。入栈写成data[top++] = x，判断空栈条件是top == 0，满栈条件是top == MAXSIZE，而栈顶元素是data[top - 1]。两种都行，但写的时候必须从头到尾贯穿同一种约定，别这里用 -1，那里又用 0，最后边界一塌糊涂。

3.2 push、pop、top的返回值设计

栈的底层代码调通之后，接下来要决定一件事：操作失败时怎么让外层知道。比如栈满了，push 要不要报错？栈空了，pop 能不能执行？这时候一个很自然的方案是让 push、pop、top 都返回int类型的成功标记。

int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAXSIZE - 1; } int push(Stack *s, int x) { if (isFull(s)) { return 0; } s->data[++s->top] = x; return 1; } int pop(Stack *s, int *val) { if (isEmpty(s)) { return 0; } *val = s->data[s->top--]; return 1; } int getTop(Stack *s, int *val) { if (isEmpty(s)) { return 0; } *val = s->data[s->top]; return 1; }

这里有几个容易写错的地方。第一，pop 和 getTop 都要通过指针参数把值带出去，如果你直接int pop(Stack *s)然后 try 返回栈顶值，那当栈是空的时候你拿什么告诉调用者“这次失败了”？返回 -1 其实不可靠，因为栈里可能真的装有 -1。所以用返回值表示成功与否、用指针参数带回数据，是这段逻辑的核心。第二，pop 和 getTop 的差异在于 pop 要移动 top，getTop 只读不移动。这个差异看着小，写代码时一旦搞混，后面所有操作都会跟着错。

3.3 完整可提交的代码参考

把上面这些组装起来，再加上主函数的指令分发逻辑，一份完整的参考代码大概长这样：

#include <stdio.h> #include <string.h> #define MAXSIZE 100000 typedef struct { int data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAXSIZE - 1; } int push(Stack *s, int x) { if (isFull(s)) return 0; s->data[++s->top] = x; return 1; } int pop(Stack *s, int *val) { if (isEmpty(s)) return 0; *val = s->data[s->top--]; return 1; } int getTop(Stack *s, int *val) { if (isEmpty(s)) return 0; *val = s->data[s->top]; return 1; } int main() { int n, x; char op[10]; Stack st; while (scanf("%d", &n) != EOF) { initStack(&st); for (int i = 0; i < n; i++) { scanf("%s", op); if (strcmp(op, "push") == 0) { scanf("%d", &x); push(&st, x); } else if (strcmp(op, "pop") == 0) { int val; if (pop(&st, &val)) { printf("%d\n", val); } else { printf("error\n"); } } else if (strcmp(op, "top") == 0) { int val; if (getTop(&st, &val)) { printf("%d\n", val); } else { printf("error\n"); } } else if (strcmp(op, "empty") == 0) { printf(isEmpty(&st) ? "yes\n" : "no\n"); } } } return 0; }

这里我写的empty输出是yes/no，具体到你的题目里可能是true/false，也可能是1/0，务必以题面输出要求为准。还有一个重点是：不同版本的题目里，pop 成功后到底要不要输出弹出来的值，这也不完全一样。有的题目只要求“弹走”，不要求输出任何东西；有的要求像 top 一样输出。拿不准的时候就去看样例输出，样例里必然有所暗示。

3.4 主流程的控制逻辑：多组输入与指令分发

主函数的写法也是典型考点。头一行while (scanf("%d", &n) != EOF)是为了应对“多组输入，处理到文件尾”的题目要求。有些同学第一次见到这种写法会犯嘀咕：为什么只在主函数里写一次initStack不行？因为下一组测试的栈应该是空栈，如果你不重新初始化，上一组残留的数据就会污染这一组结果。

指令分发部分，最常见的是用字符串strcmp去比对。这时候有个隐藏问题：char op[10]这个数组开多大？如果题目指令是push、pop、top、empty，最长是 5 个字符，开 10 绰绰有余。但如果你访问了op[10]或者用gets去读，那就要小心缓冲区的问题。scanf 配合%s会自动跳过空白字符，遇到空格换行都会自动处理，这在这个场景下是最省事的读法，不需要自己手动去吃掉多余的空格。

当指令是push时，后面还跟着一个整数，所以要先读一下字符串，判断是 push 之后再scanf("%d", &x)。这里要注意读取顺序，如果把scanf("%d", &x)写在strcmp之前，那 pop、top、empty 这些指令也会多读一个整数，输入流立马就乱了。

4. 刷OJ最容易翻车的几个点：从段错误到格式错

4.1 指针传参问题：为什么你的栈永远是空的

这道题我印象最深的一个坑，是函数传参。很多初学者会把栈本身作为形参传进函数里，比如写成：

void push(Stack s, int x) { s.data[++s.top] = x; }

这样写，函数内部确实把数据塞进了s.data，但问题是这个s是实参的一份拷贝。函数返回后，主函数里的st一点没变，top 还是原来的 top。结果就是：你老是觉得栈是空的，top 一查，还在栈底。排查这种问题，不要瞎猜，先在 push 和 pop 里各自打印一下调用前后的s.top，如果内部变了、外部没变，那十有八九是传了值而不是传了指针。

修复方式就是统一改成Stack *s，用指针操作原对象：

void push(Stack *s, int x) { s->data[++s->top] = x; }

这个点看起来基础，却是动手写栈时高频出现的问题，尤其当栈结构体较大时，传值复制带来的性能浪费还是次要的，逻辑错误才是真正致命的。

4.2 空栈操作的返回值：选错就只能看着WA发愣

接着就是“空栈操作返回什么”的问题。如果你的 pop 函数返回 0 表示失败、返回 1 表示成功，那在判空栈的yes/no输出里，直接用isEmpty去判断逻辑上最顺。但有人会图省事，让 pop 失败时返回一个魔术数，比如返回 -999999，这在数据范围里未必不会出现，属于给自己埋雷。

正确的做法我在代码里已经演示过：pop 和 getTop 都返回布尔语义，成功为 1，失败为 0，真正的值通过指针带出来。这样在调用层，你只需要判断返回值来决定是打印栈顶值还是打印error。而且这种设计有个附带的好处：push 失败（栈满）时也能用同样的套路处理，虽然这道题里栈满的情况不一定出现，但写代码时保持一致的风格总是好事。

另外提醒一下，很多题目的empty查询指令跟top/pop一样，都是操作序列中的一行。如果你偷懒没有实现empty，或者只是写了注释“此处略”，那题目里的所有查询都会无人应答，WA 是必然的。哪怕是最基础的栈，四个操作一个都不能少。

4.3 输出格式：空格与换行的折磨

OJ 题经常因为格式问题把人折磨到自闭，这道题也不例外。第一种常见的格式坑是“指令输出的行尾要不要换行”。我上面给的代码全都是printf("%d\n", val)，因为大多数题面会明确说“每个输出占一行”。如果你的题目并没有这个说明，但样例输出看起来是一行一个值，那就按样例来。

第二种坑是“多组输出之间要不要空行”。有些题会要求每组输出结束后加一个空行，这个要求通常隐藏在题面最后一句：“每组输出后跟一个空行。”如果用我的代码，你只会看到连续的行输出，这时候就得单独加一个标记。比如在处理完一组 n 条指令后printf("\n")。这属于和样例对答案的环节，不能光靠想象。

还有第三种情况是输出里同时混数字和英文单词。比如空栈时输出error，非空时输出数字。这种混合输出往往容易在复制样例时少打一个字母。务实建议：把样例输出逐字符复制到本地文件，挨个对比，比肉眼强一百倍。

4.4 段错误与数组越界的排查链路

段错误（Segmentation Fault）在刷题时经常和白屏挂钩。这道题里出现段错误，常见原因集中在三处：第一，数组开小了，push 很多次之后越过data[MAXSIZE-1]；第二，scanf("%s", op)读入的字符串长度比op数组容量还大；第三，某个函数里用了空指针，比如传进来的栈指针是 NULL。

我给一个实际的排查链路，照着走一遍基本能锁定问题。第一步，本地编译时加-g -Wall，用调试器跑一遍，看崩溃栈指向哪个函数哪一行。第二步，如果是数组越界，检查你的top是否可能超过 MAXSIZE-1，在 push 之前打印top和MAXSIZE - 1对比。第三步，如果崩溃点在strcmp，回去看op数组长度和题目里最长指令的长度，是不是差了一个字符。第四步，如果前几步都正常，考虑是不是多组输入时initStack没写在循环里，导致上一组数据把 top 抬到极高位置，下一组 push 几回就直接越界。

这四步走下来，绝大多数段错误都能定位到根因。记住一个原则：段错误不是靠猜的，是靠打印和对比查出来的。

5. 一道基础题背后的进阶方向：从栈的变体到实际应用

5.1 单调栈的思维起点

把这道题AC之后，如果你只停在“我会写栈了”，那收获确实有限。栈的基本操作，是整个数据结构课里性价比最高的一章。因为它的应用范围极广，往深走几乎立刻就能碰到单调栈。

单调栈的核心思想是：在入栈的时候，把破坏单调性的那些元素从栈顶弹出去。比如维护一个从栈底到栈顶递增的栈，遇到一个新的元素时，只要栈顶元素比它大，就一直弹出，然后再把新元素压进去。这样做的效果是，每个元素能“看到”的左右边界信息都被压缩在栈里了，常见的问题是“下一个更大元素”和“柱状图中的最大矩形”。

从这道题移植过去非常顺，因为你已经清楚栈的 pop 和 push 都是 O(1)，也清楚栈顶指针怎么移动。单调栈不过是把“无条件压栈”改成了“有条件的先弹后压”，底层操作跟基础题完全一样。所以我说，做实验题最大的价值，就是先把肌肉记忆练出来，后面学变体时才不会卡在基础动作上。

5.2 括号匹配与表达式求值

栈的应用里，还有两个绕不开的经典场景：括号匹配和后缀表达式求值。括号匹配的思路是把左括号依次入栈，遇到右括号时，弹出一个栈顶元素检查类型是否匹配。这里对你的基础代码提出了一个细化要求：栈里存的可能不再是整数，而是一个符号字符。这意味着结构体里的data类型要从int改成char，或者进一步改成通用类型。你可以体会一下，当需要适配多种类型时，手写栈的代码结构是否依然清晰，这其实是对“栈的基本操作”更深一层的检验。

表达式求值则是把中缀表达式转成后缀表达式，再用一个栈来扫描后缀表达式。扫描到操作数就入栈，扫描到运算符就弹出两个操作数运算，再把结果压回去。这两个场景都要求你灵活调用 push、pop、getTop，而不是只在一个简单主函数里跑一遍。所以刷完这道实验题，建议立刻找几道括号匹配和表达式求值的题来巩固，效果比反复看教材好得多。

5.3 从“会写栈”到“会用手写栈”

最后聊聊认知层面的进阶。我发现很多同学做完这道题之后，会陷入一个误区：“既然 STL 有 stack，自己手写还有什么用？”其实手写栈的收获远不止于“学会一个容器”。它让你理解，任何栈的底层都不过是一个线性序列加一个指针，而这个指针的移动规则就是那些看起来枯燥的++top、--top。当你真正理解这一点之后，以后看复杂的栈结构、看递归调用栈、看运行时栈帧，都会有更加亲切的感觉。

面试的时候，当面手写一个栈的实现，其实不只是考记忆，更考你边界处理、API 设计思路，以及出错时的排查思路。我曾经和一个同学讨论过他的实现，他第一版代码在执行pop时没有判空，我心里就知道这道题他还差一截，第二版加上判空之后再问“为什么返回值和指针参数要分开”，他明显卡住了。这不是什么冷门问题，而是基础知识的延伸。

所以我的建议是，做完 oj3335 这道题之后，别急着关掉浏览器，再花半小时做三件事：第一，试着把全代码改成 top 初始化为 0 的风格，逼自己把每个边界条件重新推算一遍；第二，写一个括号匹配的程序，复用现在这套栈；第三，把 push/pop 失败时的打印信息统一约定好，为自己以后的代码风格定一个基准。这些事情做完，这道“栈的基本操作”才算真正吃透了。