1. 项目概述：这道实验题到底在考什么

我第一次在在线评测系统（OJ）上看到“数据结构实验之栈与队列八：栈的基本操作”这道题时，题号是3335，心里想：这还不简单？栈的基本操作嘛，push、pop、top，几分钟就能写完。结果第一次提交就被打脸了，不是编译错误就是答案错误，最后查了半天，问题居然出在命令字符串读取上，而不是栈本身。从那时候起我就明白了一个道理：OJ上的实验题，越基础越考验细节。

后来我把这道题前前后后重做了好几遍，发现它非常适合用来检验一个人“代码到底写明白了没有”。题目本身不大，但完整的实验流程里该有的坑它都有：多组数据、字符串命令解析、边界条件、输出格式、内存管理。只要你是刚开始学数据结构的学生，或者准备考研正在复习栈这一章，再或者自学编程想补算法基础的人，这道题都值得认真做一遍。做完之后，你对栈的理解就不再是“背概念”，而是能真正写代码实现它。

1.1 栈的核心特性：后进先出的直觉

栈是一种操作受限的线性表。普通数组可以在任意位置插入和删除元素，而栈只能在栈顶操作。你可以把它想成一摞盘子：后放上去的盘子永远在最上面，要拿盘子也只能从最上面拿。这就是“后进先出”（LIFO, Last In First Out）。在代码层面，栈只需要两个关键信息：一个用来存元素的数组，一个用来记录栈顶位置的下标。入栈就是往栈顶放一个元素，出栈就是从栈顶拿走一个元素，取栈顶就是只看看栈顶是什么但不拿走。

很多刚开始接触数据结构的人会觉得栈太简单了，不就是操作一个数组吗？但栈真正重要的不是那几行代码，而是“操作受限”带来的抽象能力。函数调用的时候，系统要用调用栈来保存返回地址；浏览网页的时候，浏览器要用历史记录栈来实现后退功能；写算法的时候，括号匹配、表达式求值、深度优先搜索统统离不开栈。可以说，栈是所有后续复杂算法的一块重要地基。

1.2 为什么“基本操作”是后续内容的根基

有人问过，既然栈这么简单，为什么还要单独拿一道实验题来考？原因在于，很多人对栈的“感觉”是建立在背概念上的，而不是建立在代码实现上的。只有亲手把初始化、入栈、出栈、判空、取栈顶这些函数一个个写出来，踩过几个边界条件的坑，你才会真正理解栈顶指针为什么会移动、栈空时为什么不能取元素、栈满时为什么不能继续压入。

如果这些基本操作没练扎实，后面学二叉树遍历、图的深度优先搜索时，会遇到更抽象的问题：树的中序遍历非递归写法里，为什么左子树要先全部入栈？图的DFS里，为什么某个节点出栈之后还要检查邻接点？这些问题本质上都在考察栈的行为。所以“oj3335”这类实验题不是在难为你，而是在逼你把最底层的东西练到位。

2. 实验需求拆解：做题前先看题面

2.1 理解输入格式与多组数据

OJ题和平时自己写小程序最大的不同，就是输入输出有严格约定。虽然不同教学平台的题面可能略有差异，但这类“栈的基本操作”题目大多数遵循同一类模式：第一行给两个整数，一个表示后续操作次数，另一个表示栈容量上限；接下来若干行是命令，命令可能是push、pop、top、empty等。

这里最关键的一点是，题面经常写着“多组输入，处理到文件末尾”。意味着不能只读一次数据，而是要一直读到EOF为止。很多人只写一次读入，样例过了就觉得万事大吉，结果第二组测试数据一出，栈里还残留着第一组的东西，输出全都乱了。正确写法是while (scanf("%d%d", &n, &m) != EOF)，把整个处理过程放进循环里。

还有一个细节容易踩坑：读完数字之后再读字符串命令，如果用scanf("%s", cmd)，它会自动跳过空白字符，包括换行和空格，所以问题不大。但如果你混用了gets，比如前面scanf读完数字后没有清掉缓冲区里的换行，gets会直接把那个换行读成一个空串，后续命令全都对不上号。这个坑我帮不少同学排查过，典型症状就是“第一行命令永远执行错，后面的又正常了”。

2.2 明确边界操作的行为约定

栈空时pop或top应该输出什么？栈满时push应该输出什么？这两个问题必须在写代码之前搞清楚，否则必然会在“答案错误（WA）”里挣扎。常见的约定是输出“error”或者“empty”，也有题目要求什么都不输出，甚至还有要求输出“栈空”之类的中文提示的。

我见过有的题面写“栈空时无法取出元素，输出error”，也见过写“输出EMPTY”，大小写不同。最稳妥的做法是先看题面给出的样例输出，用样例反推行为约定，不要凭感觉敲。为了保险，可以在草稿纸上列一张表，对照题面逐行确认：push x时栈满怎么办，pop时栈空怎么办，top时栈空怎么办，empty判断之后到底输出哪个单词。把这张表放在旁边，写代码时一条条对照，能省下很多反复提交的时间。

2.3 字符串命令解析的常见失误

命令解析看起来简单，其实很容易翻车。最稳的写法是用strcmp逐字比较，比如strcmp(cmd, "push") == 0。有些同学为了省事，只判断cmd[0]，于是“push”和“pop”都会走进同一个分支里，还得再加一层判断第二个字符。这种写法也不是不行，但一旦命令变多，比如出现“print”“peek”“popall”，代码就会变成一团乱麻。

在“栈的基本操作”这道题里，命令数量很有限，直接strcmp一行一个分支最合适。每个分支里不要再写复杂的嵌套逻辑，读一个数字就处理，处理完就回到主循环读下一条命令。这样写出来的代码不仅清晰，而且调试时能很快定位问题——只要printf一下cmd的内容，就能看出是读错了还是判断错了。

3. 顺序栈与链栈：两种实现的核心代码

3.1 顺序栈：数组加下标，最直观的写法

顺序栈是用一块连续的数组空间来存储元素，用一个整型下标指向栈顶位置。下标初始化为0表示空栈；入栈时，先把x放进data[topIndex]，然后让topIndex加1；出栈时先把topIndex减1，再把对应位置的元素取出来；取栈顶时取的是data[topIndex - 1]。这个设计的好处是简单、直观、访问速度快，而且调试时只要看topIndex的值，就能知道栈里有多少个元素。

下面的完整示例代码，用SqStack结构体封装了数据数组和栈顶下标，每个操作都封装成独立函数，main函数只负责命令分发。这种模块化的写法虽然比“全写在main里”多几行，但可读性强很多，后续想扩展命令也不用大改。

#include <stdio.h> #include <string.h> #define MAXSIZE 1000 typedef struct { int data[MAXSIZE]; int topIndex; } SqStack; void initStack(SqStack *s) { s->topIndex = 0; } int isEmpty(SqStack *s) { return s->topIndex == 0; } int isFull(SqStack *s) { return s->topIndex == MAXSIZE; } int push(SqStack *s, int x) { if (isFull(s)) { return 0; } s->data[s->topIndex++] = x; return 1; } int pop(SqStack *s, int *x) { if (isEmpty(s)) { return 0; } *x = s->data[--s->topIndex]; return 1; } int getTop(SqStack *s, int *x) { if (isEmpty(s)) { return 0; } *x = s->data[s->topIndex - 1]; return 1; } int main() { int n, m; char cmd[20]; while (scanf("%d%d", &n, &m) != EOF) { SqStack st; initStack(&st); while (n--) { scanf("%s", cmd); if (strcmp(cmd, "push") == 0) { int x; scanf("%d", &x); if (!push(&st, x)) { // 栈满时按题目要求输出 } } else if (strcmp(cmd, "pop") == 0) { int x; if (pop(&st, &x)) { // 按题目要求决定是否输出弹出的值 } else { // 栈空时按题目要求输出 } } else if (strcmp(cmd, "top") == 0) { int x; if (getTop(&st, &x)) { // 按题目要求输出栈顶元素 x } else { // 栈空时按题目要求输出 } } else if (strcmp(cmd, "empty") == 0) { // 按题目要求输出栈是否为空 } } } return 0; }

代码里的注释位置，就是需要根据题面确认输出格式的地方。有时候题目要求pop时输出弹出的元素，有时候又不要求输出，这一点直接决定你是写printf还是不写。这类“看起来不起眼”的约定，恰恰是WA最集中的地方。

3.2 链栈：动态内存，不用预分配

链栈就是把链表当成栈来用，栈顶就是链表头。入栈时用头插法创建新节点，出栈时删除头节点。相比顺序栈，链栈最大的好处是不用预先指定容量，只要内存足够，就可以一直执行push操作。代价是代码量稍微大一些，而且每个节点申请后必须记得释放，否则会造成内存泄漏。

链栈的节点结构只需要两个成员，一个是整数数据域，一个是指向下一个节点的指针，另外再定义一个结构体保存栈顶指针就行了。虽然比顺序栈多了一层嵌套，但逻辑上很清楚：top指针指向的永远是当前栈顶节点，所有操作都在链表头部完成。入栈的顺序一定不能搞反：先让新节点的next指向当前的top，再让top指向新节点。出栈时则要先保存要删除的节点指针，再移动top，最后才free掉旧节点。很多人写链栈出栈时直接free(top)，结果top已经指向了下一个节点，被free的却是新栈顶，内存直接悬空。

3.3 命令分发主流程的设计

不管用顺序栈还是链栈，主流程都一样：循环读命令，比较字符串，执行对应操作。我强烈建议不要把栈操作直接写在main的一大堆if里，那样代码会越改越长，最后自己都看晕了。封装成独立函数之后，每个函数可以单独测试：先写initStack和push，写个小测试连续push三次，打印一下栈里的元素，确认没问题再写pop和top。

这种模块化测试的方式，比“全写完再从头查”要高效得多。尤其是对于新手，一次函数只做一件事，出了错误也能快速定位到具体函数。如果题目要求增加一个“show”之类的命令，只需要在main里加一个else if分支，然后调用一个显示函数，完全不影响现有逻辑。

3.4 初始化、传参与销毁的几个易错点

在实际写代码的过程中，最容易犯的错有三个。第一是忘记初始化。定义了SqStack st之后直接操作，topIndex是随机值，push到随机下标，运行结果完全不可控。所以定义变量之后必须调用initStack，而且在多组数据场景下，每组数据都要重新初始化一次。

第二是函数传参写成了传整个结构体。有人写push(SqStack s, int x)，以为是传入栈了，实际上函数内部操作的只是形参的一份拷贝，函数返回后原栈不会有任何变化。调试的时候会发现，栈永远都是空的，元素永远进不去。这种情况必须传指针，写作push(SqStack *s, int x)。

第三是销毁不彻底。顺序栈如果用malloc给数组base分配过堆空间，程序结束前要记得free；链栈则要循环释放所有节点。OJ平台一般不会因为你少free就报错，但代码审查看的是工程习惯，内存管理这个基本功还是得养成。

4. 常见问题排查与调试实录

4.1 OJ返回结果的含义

做OJ题，首先得看得懂返回结果。Accepted是通过，Wrong Answer是答案错误，Runtime Error是程序运行崩溃，Presentation Error是输出格式错误，Compile Error是编译错误。很多人看到WA就急着改输出内容，却忽略了格式问题。多打了一个空格，少打了一个换行，都可能被判成PE，甚至直接算WA。所以写输出语句时，严格照着题目给的输出样例来，不要自己发挥。

4.2 最容易导致Wrong Answer的几个原因

第一个最典型的原因就是边界条件没按题面处理。栈空时执行pop或top，该输出什么错误信息，输出格式是什么样的，这里几乎贡献了这类题目的半数WA。第二个典型原因是多组数据没有初始化。上一组数据跑完之后，栈里还留着旧元素，下一组开头又把topIndex清零，等于把两组数据混在一起处理了。解决方式是把initStack放到while循环内部，或者每组数据读入后手动重置topIndex。

第三个原因是输出时大小写或分隔符不对。题面要求输出“Error”还是“error”，要求每条输出后面跟空格还是换行，都必须逐字对照。我见过有人因为把“empty”打成了“Empty”，反复提交很多次才醒悟。第四个原因是命令读取错误，尤其是gets和scanf混用之后，缓冲区里的换行符搅乱了整条命令序列。

4.3 Runtime Error的典型场景

运行时错误最常见的原因是数组越界。比如栈容量只有10，但操作序列里连续push了20个元素，而push函数又没有判断栈满，数据就会写到data[10]之外，程序当场崩溃。所以push函数里必须先判断isFull。再比如栈空时执行pop，代码直接做--topIndex并访问data[topIndex]，此时topIndex已经是0，访问data[-1]就是非法内存访问。

另一个容易被忽略的RE原因是scanf的返回值没处理。本地IDE里输入到文件末尾后，程序可能还能继续运行，但OJ上如果读不到数据却还在继续处理，就会陷入死循环或读到无效内容。while (scanf(...) != EOF)这种写法是标准做法，不要省掉EOF判断。

4.4 本地自测数据的构造方法

做题不能只靠提交去试错，那样效率太低。我习惯在本地先准备几组测试数据，用freopen把输入输出重定向到文件，跑完和期望输出做对比。下面的写法在本地测试时非常方便：

freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);

in.txt里可以放一组常规数据： 5 5 push 1 push 2 top pop top

如果题目要求top输出栈顶元素，期望输出是： 2 1

然后再构造一组空栈操作： 2 5 pop top

根据题面约定，看看该输出什么错误信息，是否符合预期。再构造一组栈满的测试，比如容量5却连续push 6次，看看满栈时的输出逻辑是否正确。空栈、正常、满栈三种情况都测一遍，提交的时候心里就有底了。

4.5 调试时的实用技巧

在关键位置打印中间状态，是最快的定位方式。push之后可以打印一下栈内所有元素，pop之后打印一下topIndex，命令解析分支里打印一下cmd的内容。这些调试用的printf在提交之前统一删掉就行，不会影响最终代码。

如果用了IDE的调试器，也可以在push和pop函数里打断点，观察data数组和topIndex的变化。栈这类数据结构调试起来其实很舒服，因为它只有一个变化入口，不像链表那样需要追踪各种指针关系。只要topIndex的增减和题目逻辑对得上，栈的实现基本就没问题。

5. 从这道实验题延伸出去

5.1 栈在经典算法里的应用

做完这道题，栈的基本操作已经到手了，可以顺手练几个经典应用。括号匹配就是用栈判断的经典例子：遍历字符串，遇到左括号就入栈，遇到右括号就出栈，最后检查栈是否为空。如果中途出现“该出栈时栈是空的”这种情况，括号一定不匹配。这个逻辑和本题里的pop空栈判断其实是一脉相承的。

逆波兰表达式求值也离不开栈。遇到数字就入栈，遇到运算符就弹出两个数字计算，再把结果压回栈里。整个过程你会反复用到push和pop，而且栈的顺序非常关键，谁先弹出、谁后弹出直接决定运算结果。还有进制转换，除基取余得到的余数顺序是逆序的，用栈把余数保存下来再统一输出，正好把后进先出的特性用得淋漓尽致。

5.2 单调栈：面试和竞赛里的常客

如果还想继续进阶，不妨了解一下单调栈。它依然是栈，只是入栈时保持栈内元素从上到下有序，通常用来解决“下一个更大元素”这类问题。因为每个元素最多入栈一次、出栈一次，整体复杂度可以做到O(n)，比双重循环高效很多。这类技巧在算法面试和程序设计竞赛里都很常见，从“栈的基本操作”到“单调栈”，是一条很自然的进阶路线。

5.3 三个值得长期保持的实操习惯

我把自己踩过几次坑之后总结出来的习惯分享给后来人。第一，写代码之前先手算一遍样例，把每一步操作在纸上模拟出来，确定每一步应该输出什么，再正式写代码。第二，每写完一个函数就单独测一次，不要攒到最后一次性调试，模块化测试能帮你把问题控制在很小的范围内。第三，提交之前做一次自查：边界条件有没有处理，输出格式有没有对上行，多组数据有没有重新初始化。这三个习惯看着简单，但确实能帮你省下大量反复提交的时间。

我个人做OJ题的一个心得是，像“栈的基本操作”这种题目，题目越基础，越能看出代码习惯的差距。有人一遍AC，有人反复提交七八次，差的往往不是智商，而是有没有把“先看题面、再写边界、最后测试”这套流程走完。这道题真正的价值不在于AC那一下的快感，而在于它逼着你把栈从概念变成了肌肉记忆。以后写再复杂的算法题，这套流程也是通用的。