数据结构栈全解析：C++实现与课后题高频考点

每次带新人复习数据结构，我总喜欢让他们先把第二章“栈”彻底啃下来。理由很朴素：整本《数据结构（C++描述）》的前半部分，如果只能留下一个概念，我肯定会选栈。它结构简单，就一个后进先出的规则，却能串起递归、表达式求值、括号匹配、迷宫求解一大片考点，也是后面队列、树、图遍历的思想底座。这一篇我把第二章栈的常见课后题按题型拆开，配上C++实现思路和参考答案，顺便把我自己踩过的坑、改作业时看到的高频错误一并写出来，适合正在期末复习、考研刷题、或者刚学完这一章想验证掌握程度的同学。

1. 先从整体上读懂这章：栈为什么值得单独拿出来讲

1.1 栈的本质不是“容器”，而是一个处理顺序约束的开关

很多人学栈的时候，第一反应是把它当成一个“只能从一头进出的数组”，这个理解不算错，但太浅了。栈真正厉害的地方在于：它用极小的结构成本，制造了一个“状态回溯”的能力。你把当前状态压进去，随时可以弹出来恢复现场，这在程序运行里几乎无处不在。

函数调用的嵌套、浏览器里点返回、文本编辑器里按撤销，核心动作都是一个栈。教材第二章把它放在线性表之后、队列之前，就是想让你建立一种思维习惯：先想清楚数据进出顺序，再决定用什么结构。栈就是为“逆序处理”而生的结构，凡是需要把一串东西先存下来、再反着取出来的场景，栈都是第一候选。

这一章课后题虽然表面花样多，但剥开看，绝大多数都在反复训练三件事：一是判断栈空栈满，二是处理栈顶指针的移动，三是用栈改变操作顺序。把这三件事练到条件反射，后面的树遍历、图的深度优先搜索、拓扑排序，学起来都会轻松非常多。

1.2 课后习题的主流题型，其实就四大类

我翻过不少版本的教材和配套习题集，第二章栈的题目基本可以用下面这张表归类：

出栈序列分析往往是第一个分水岭。题目会给一个入栈序列，比如1、2、3、4，然后问下面哪个出栈序列合法。很多同学靠直觉硬猜，能答对一部分，但遇到复杂一点就翻车。其实核心方法只有一个：模拟入栈过程，每当栈顶元素等于当前出栈序列的待匹配元素，就弹出，直到无法继续为止。合法序列一定能在模拟过程中完整弹空。

我当时复习时，专门拿了一张草稿纸，把1到n所有入栈序列的合法出栈情况列了一遍，才发现一个有趣结论：栈的输出序列规律其实非常严格，同一个输入，合法出栈序列的数量满足卡特兰数。虽然教材不一定考这个推导，但理解了这一层，很多选择题直接看了开头几个数字就能排除错误选项。

2. C++ 描述：两种栈的典型实现逐行拆解

2.1 顺序栈：数组加 top 指针，边界是命门

顺序栈是教科书默认给出的实现，逻辑最直白。我用C++写关键部分给各位看，重点在于 top 怎么定义。

#define MAXSIZE 100 template <typename T> class SeqStack { private: T data[MAXSIZE]; int top; // 栈顶元素的下标 public: SeqStack() { top = -1; } // 空栈时 top = -1 bool push(const T& e) { if (top == MAXSIZE - 1) return false; // 栈满 data[++top] = e; return true; } bool pop(T& e) { if (top == -1) return false; // 栈空 e = data[top--]; return true; } T peek() const { if (top == -1) throw "empty stack"; return data[top]; } bool empty() const { return top == -1; } };

top 初始化为 -1，代表栈中没有任何元素。入栈时先加1再存，出栈时先取再减1，这套约定要背下来。很多课后题喜欢在这里埋坑，比如问“top 初始化为 0 时，栈空和栈满条件怎么写”，答案是栈空判断变为 top == 0，栈满判断变为 top == MAXSIZE，入栈变成 data[top++] = e，出栈变成 e = data[--top]。同一个问题只是因为约定不同，答案完全不同，做题时务必看清楚题目定义。

顺序栈最隐蔽的问题在于“满栈”与“可用空间”之间的关系。有些题目会故意把 MAXSIZE 定义成 10，然后连续入栈 9 个元素后问栈顶指针的值，答案不是 8 就是 9，取决于实现方式。所以这类题我建议一律用模拟法，不要背公式。

2.2 链栈：链表结构，彻底告别栈满

链栈在初学阶段容易被忽略，因为教材例题少，考试也偏重顺序栈。但链栈的代码实现包着栈的外壳，实际上考察的是单链表的头插法和头删法。把链栈写明白了，说明你很透彻地理解了栈顶指针的本质。

template <typename T> struct StackNode { T data; StackNode<T>* next; StackNode(const T& val, StackNode<T>* nxt = nullptr) : data(val), next(nxt) {} }; template <typename T> class LinkedStack { private: StackNode<T>* top; public: LinkedStack() : top(nullptr) {} void push(const T& e) { top = new StackNode<T>(e, top); // 新节点插在头部 } bool pop(T& e) { if (!top) return false; e = top->data; StackNode<T>* tmp = top; top = top->next; delete tmp; return true; } ~LinkedStack() { while (top) { StackNode<T>* tmp = top; top = top->next; delete tmp; } } };

注意，链栈的 push 不需要判断栈满，因为内存是动态分配的，但要在构造函数里把 top 置空，并且记得写析构函数释放内存。我在批改模拟项目X的代码时，看到不少同学漏写析构函数，导致栈每执行一次就泄漏一部分节点。这个问题在大型作业里一多跑几次就露馅，内存占用直接飙升。

2.3 顺序栈和链栈怎么选，答题时要说清楚

课后简答题经常问“什么时候用顺序栈，什么时候用链栈”。标准答法其实就两层：已知最大容量、要求存取速度快，选顺序栈；容量无法预估、需要频繁动态伸缩，选链栈。顺序栈的优点是缓存局部性好、实现简单，缺点是扩容麻烦；链栈的优点是理论上无限，缺点是每个节点多一个指针域，空间开销多 1/3 左右。

如果题目进一步追问“为什么栈通常不需要像顺序表那样大费周章地扩容”，答案也很干脆：栈的操作只发生在栈顶，不存在中间插入删除，就算要扩容，也只需要重新分配一片更大的空间，再把旧元素整体搬过去，不会像顺序表那样涉及多个位置的数据移动。

3. 课后高频应用题的完整解答思路

3.1 数制转换：反复取模，逆序输出，栈天生合适

这道题几乎每一本教材都会收：输入一个十进制整数 N 和进制 R，输出转换后的结果。原理是除 R 取余，余数先算出来，但要最后输出，这与栈的后进先出完全吻合。解题模板可以写成：

1. N 不为 0 时，把 N % R 压栈；
2. N = N / R；
3. 重复直到 N 为 0；
4. 依次出栈并输出，注意超过 10 的余数要映射成 A、B、C。

如果 N 是 0，直接输出 0，不要压栈。有些题目会把 R 设为 16，余数为 10 到 15 时输出大写字母。这个细节我在不少同学的作业里见过遗漏。

用栈做数制转换，最大的价值不是效率，而是让你直观感受“后进先出等于逆序输出”这件事。你可以试着不用栈，直接把余数存进数组再倒着打印一遍，同样能完成，但你会发现代码里多了一个“倒序”概念，而栈天然替你完成了这一步。

3.2 括号匹配：向后看 vs 向前看，思路说清楚就不难

括号匹配的题目描述很统一：给定一个只包含 ( ) [ ] { } 的字符串，判断括号是否成对且嵌套正确。解法可以写成这样：

1. 遇到左括号（( [ {），无条件压栈；
2. 遇到右括号时，先看栈是否为空，空则说明当前右括号没有对应的左括号，匹配失败；
3. 栈非空，弹出栈顶元素，检查是否与当前右括号配对，不配对则失败；
4. 全部扫描结束后，栈必须为空，否则说明还有左括号没有被闭合。

我在实际讲解时，喜欢用一个生活化类比：括号匹配很像等电梯的人排队进小区，左括号是刷卡进门的人，右括号是出门的人，刷卡进去的人必须按顺序再出门，如果中间有人乱插队，门禁就报警。但其实核心只有一条：当前遍历到的右括号，必须和最近一次压入的左括号配对。

代码实现时还要注意，匹配字符用 switch 或条件判断都行，但不要忽略栈顶取值的时机。标准写法是先弹出再比较，千万不要先比较再弹出，否则有栈元素残留的风险。

3.3 中缀转后缀与表达式求值：栈的两个高难考点

表达式求值是本章真正拉开差距的题目。常见有两种形态：一种是给中缀表达式转后缀表达式，另一种是给后缀表达式求值。中缀转后缀的规则可以浓缩成四句话：

• 操作数直接输出；
• 运算符与栈顶比较优先级，高则入栈，低或相等则弹出栈顶运算符，再继续比较；
• 左括号直接入栈，遇到右括号则弹出直到左括号；
• 扫描结束后，把栈里剩余运算符全部弹出。

括号优先级在转后缀时最容易被忽略。很多同学会下意识地把所有括号都当作运算符处理，结果转出来的后缀表达式完全没法求值。记住：左括号在栈外优先级最高，进栈之后优先级降到最低，这样设计是为了保证只有当右括号出现时才被弹出。括号本身不进入输出序列。

后缀表达式求值就简单多了：遇到操作数压栈，遇到运算符就从栈里弹出两个操作数，先弹出的放运算符右边，后弹出的放运算符左边，再把结果压回去。测试用例建议用 5 1 2 + 4 * + 3 - 这种经典式子，手动推一遍就能验证实现是否正确。这里最容易错的不是算法，而是减法、除法这种不满足交换律的运算，操作数顺序反了，结果立刻不对。

4. 难度升一级：共享栈、递归消解与迷宫模拟

4.1 共享栈：两个栈挤同一块数组，浪费空间最小化

共享栈是教材里一个很有设计感的题目，常以“设计一个算法，让两个栈共享一段存储空间”出现。思路非常简单：数组两端各设一个栈底，两个栈分别向中间生长。左侧栈栈顶指针为 leftTop，右侧栈栈顶指针为 rightTop，当 leftTop + 1 == rightTop 时栈满。

共享栈的意义在于：两个栈的使用情况往往此消彼长，如果各自分配固定空间，某个栈很容易溢出，另一个却大量空闲。共享存储空间以后，总空间利用率可以最大化。这个思想比实现本身更值得记住，因为后面学操作系统里的堆空间分配、双端队列设计时，都会看到类似思路的变体。

实现时最容易忽略的问题是入栈方向。左侧栈入栈，指针向右移动；右侧栈入栈，指针向左移动。很多同学写着写着，把两个栈的操作方向写成一样，结果第二个栈入栈直接覆盖了第一个栈的元素。我的建议是画一张数组示意图，每一步操作都标出两个栈顶所在位置，代码写完以后先把题目要求的用例跑一遍。

4.2 递归转栈：用你自己的栈替换系统调用栈

教材第二章总爱在末尾安排几道类似“用栈消除递归”的题。初看很难，其实本质就是在模拟系统调用栈的压栈与弹栈过程。以经典汉诺塔为例，递归写法只需要三行核心代码，但你要手动用栈模拟时，就必须把“当前要移动的盘数、起始柱、目标柱、辅助柱”打包成一个结构体压入栈中，然后按照递归展开的逆序压入子任务。

一个实用的套路是：先把原问题压栈，while 栈不空时弹出一个任务，如果任务规模可以直接解决就当场处理，否则把它的子任务按执行顺序逆序压栈。这里面最难把握的是“逆序压栈”。因为栈是后进先出，所以如果递归过程打算先处理左子树再处理右子树，压栈时就应先压右子树再压左子树，这样弹出顺序才符合原递归顺序。

这类题目在考试里未必要求写完整代码，但思路要能写在纸上。可以这样答题：定义结构体 Task 保存状态信息，每进入一层递归视为一次 push，每返回一层视为一次 pop，递归结束条件对应栈空。能把这句话写清楚，基本就能拿下一大半分数。

4.3 迷宫求解：把走过的格子都当状态压进栈

迷宫问题是栈的经典应用，也是我特别喜欢拿来考察学生的一道题。常见的设定是：迷宫用二维数组表示，1 是墙，0 是通路，要求从入口走到出口，输出一条可行路径。基于栈的做法有两条路线：第一，每次把当前位置压栈，沿某个方向探索，走不通就弹栈回退，这叫深度优先搜索；第二，先压入口，再不断弹出当前格子并扩展相邻格子入栈，这叫用栈代替队列实现的深度优先搜索。

课后题如果要求“写一个回溯算法”，多半认的是第一条路线。关键步骤有四个：设定方向数组来表示上下左右四个移动；标记已经走过的格子，防止绕圈；当前位置不可继续前进时弹栈回退；找到一个出口时把栈里的路径打印出来。最容易出问题的点是重复访问判断，如果没有 visited 标记，程序大概率会陷入死循环。

我在指导 A 同学做这个作业时发现，他写的回溯算法总是回退不干净，仔细一看，原来是弹栈后没有把当前位置更新成新的栈顶元素。回退的本质就是“重新读取栈顶状态”，这一步写漏了，整个搜索就断掉了。

5. 作业提交前必看的细节复盘与常见错误清单

5.1 top 指针初始值不一致导致的连锁错误

顺序栈的空栈判断、入栈下标、出栈下标，全部由 top 的初始值决定。如果你的代码里构造栈时 top 初始化为 0，但后续 push 写的是先 ++top 再赋值，那么第一个元素会落在下标 1，白白浪费一个存储单元，栈满判断也会错一个位置。

我见过最典型的案例，是同学某次直接复制了网上的顺序栈代码，构造函数写的是 top = -1，但 push 里写的是 data[top++] = e，结果第一次入栈就写到了 data[0] 而 top 变成 0，逻辑上看起来没问题，可实际上栈顶元素是 data[0] 还是 data[1] 完全取决于你初始化方式，一旦和题目约定不一致，出栈顺序照样错。写代码前后务必检查三行：构造函数的 top、入栈语句、出栈语句，三者必须互相照应。

5.2 引用参数、返回值和析构函数三个隐藏扣分点

栈的 pop 操作通常写成 bool pop(T& e)，也就是把弹出的值写到引用参数里。很多同学图省事写成 T pop()，看起来也能跑，但在某些场景下会带来问题：如果栈空，你根本不知道返回值是无效数据还是有效数据，调用方无法区分。教材课后题经常拿这个点做讨论，标准答案基本都倾向用 bool 配合引用参数返回结果。

链栈的析构函数也是一块雷区。单链表栈在销毁时一定要用临时指针保存 next 节点，再 delete 当前节点，否则你刚释放掉当前节点，就再也拿不到 next 指针了。另外，入栈分配新节点后，如果后续操作失败，也要注意释放已经分配的内存，虽然课后小题不太会抓这个点，但作为工程习惯必须养成。

5.3 越界访问比栈溢出更隐蔽

顺序栈常见的报错是“栈已满，无法入栈”，但更隐蔽的问题是越界。比如 MAXSIZE 为 10，你却连续 push 了 12 个元素，很多编译器不会立刻报错，而是悄悄破坏了数组边界以外的内存。有时候程序最终输出正确，但下一次操作时出现莫名其妙的崩溃，排查半天才发现是栈越界导致的。

排查这类问题，我的习惯是在 push 入口处加断言，或者打印一个“当前元素个数”的日志。做题时如果题目已经给出了 MAXSIZE，就老老实实判断 top == MAXSIZE - 1。不要心存侥幸，数组越界是 C/C++ 里所有诡异行为的头号来源。

5.4 代码可以跑、答案却是错的：别忘了“链栈空栈”的判断顺序

链栈的 pop 必须两步分开处理：先判断 top 是否为空，再取栈顶元素。如果顺序反了，比如先写 e = top->data，再判断 if(!top)，当栈为空时程序会直接访问空指针，崩溃得毫无预兆。这不是你逻辑不行，而是代码执行顺序设计得太脆弱。

我每次检查学生作业，都会专门构造三个测试用例：空栈 pop、连续 push 和 pop 交替、入栈后立即清空。这三个用例跑完，栈实现里 80% 的隐藏问题都会暴露。这个习惯也建议你保持，做实验题时哪怕题目没要求，也要自己多补几个边界测试。

6. 常见教材第二章习题参考答案速查

6.1 选择题里的高频陷阱与答案

• 题目：一个栈的入栈序列是 a、b、c、d、e，则栈的不可行输出序列是哪个？ 解决思路是拿每个待选项模拟一遍。这里给出一组经典选项，正确答案是“d、c、e、b、a”可行，“d、e、c、b、a”可行，“e、d、c、a、b”不可行，因为 b 在 a 前面压栈，b 应该在 a 之前先出。
• 题目：判定一个栈是否为空，在顺序栈 top 初始为 -1 时，条件是 top == -1。
• 题目：容量为 10 的栈，若 top 初始值为 0，连续入栈 7 个元素后，栈顶指针值为 7，栈中元素个数也是 7。 能看出这种对应关系，说明你已经理解 top 值和实际元素个数之间的换算规则。

6.2 简答题参考答案范例

题目：为什么说栈是线性表的一种特殊形式？ 答：栈的逻辑结构与线性表相同，都是元素之间的一对一关系，但它的插入删除操作被限制在表尾即栈顶进行，因此是操作受限的线性表。

题目：顺序栈和链栈的栈满判断有何不同？ 答：顺序栈因为使用固定数组，栈满条件由数组容量决定；链栈动态分配节点，只有在系统内存耗尽时才不能入栈，通常不存在预先定义的栈满概念。

题目：共享栈什么时候会溢出？ 答：当两个栈顶指针相遇，即左侧栈顶加一等于右侧栈顶时，共享空间已用尽，此时任意一侧再入栈都会溢出。

6.3 算法设计题参考思路

题目：设计算法，用两个栈模拟一个队列。 思路是：入队时全部压入栈 A；出队时如果栈 B 非空，直接弹出栈 B 的栈顶；如果栈 B 为空，先把栈 A 所有元素依次弹出并压入栈 B，再从栈 B 弹出栈顶。这个方案模拟了队列先进先出的特性。我建议各位一定画一下数据流动图，只看文字很容易转不过弯。

题目：设计算法，判断单链表是否成环，且只能用一个辅助栈。 思路：遍历链表，把每个节点的指针压入栈中；每走到一个新节点时，检查栈内是否已经出现过这个节点。如果出现过，说明有环。但这里要注意，用栈判断成环并不高效，课后题之所以这么出，主要目的还是考察你对“栈存储历史信息”的理解。

题目：利用栈实现十进制转十六进制。 思路就是前面提过的除 16 取余法，余数大于 9 时分别映射 A 到 F。一个容易考到的变体是：输入数字可能为负数，需要先处理符号位，再将绝对值部分转换，最后补上负号。

题目：假设一个表达式包含小括号和中括号，要求写出匹配算法。 答案是：扫描表达式，遇到左括号入栈，遇到右括号时，若栈空则失败；若栈顶不是对应的左括号则失败；若匹配则弹栈。扫描结束后若栈空则成功，否则失败。

6.4 这些题的后续延伸：从课后题到工程题

很多同学做完这些课后题，觉得栈已经被玩明白了。但真实项目里，栈的变体远比教材复杂。浏览器的前进后退是两个栈的配合；编译器在语法分析阶段用状态栈处理嵌套结构；操作系统的事件循环里有任务栈的影子。课后题让你写一个表达式的求值，其实是在训练你将原始问题抽象成操作序列的能力。

我自己辅导新人时，最喜欢出的扩展题是：把括号匹配升级为同时支持三类括号，并返回第一个出错的位置。这个升级非常简单，只需要在匹配失败时记下当前字符序号，却非常考验代码的健壮性，因为没有出错返回的代码很难测试。如果你能把这一版写对，说明栈的基本功已经过关了。

最后分享一个我在实际写代码中的体会：判断栈问题时，永远先在纸上把“栈空、栈满、栈中一个元素、栈中多个元素”四种状态都画一遍。别看这个过程笨，它能把 80% 的边界条件错误挡在编译之前。栈这个结构虽然简单，但越简单的结构越容易出现想当然的错误，保持手画状态图的习惯，比背多少道题都有用。