1. 先把你对栈的理解从“背定义”升级到“画图”第二章“栈”其实是个分水岭。前面学的线性表、顺序表、链表本质上都是线性结构操作无非是增删改查。但栈不一样它只允许在一端插入和删除这个“操作受限”的设计是为了满足一种极其常见的需求暂时保存现场回头再恢复。很多同学学完这一章能背出“栈是先进后出的线性结构”但要让他手写一个括号匹配算法或者讲讲函数递归调用时系统具体做了什么就卡壳了。课后题的价值就在于帮你把这些抽象概念变成能跑起来的代码。我习惯把栈理解成一个“只开一头的箱子”。放东西叫入栈push拿东西叫出栈pop但你只能从开口那一端操作。你放进去的顺序是1、2、3拿出来就得是3、2、1。栈的抽象数据类型ADT也就三个核心操作push、pop、top或者叫peek只读栈顶不出栈。注意栈在逻辑上只有栈顶一端开放但物理存储上既可以用连续空间数组实现也可以用离散空间链表实现。这两种实现方式各有各的适用场景课后题里往往要求你分别写出类定义和核心操作这是本章必修的第一关。这一章课后的题目我大致归个类第一类是概念辨析题比如“栈和一般线性表的区别”“什么情况下用栈不用队列”第二类是基础实现题让你写顺序栈、链栈的类模板和push、pop代码第三类是应用场景题比如括号匹配、表达式转换、进制转换、回文判定第四类是扩展设计题比如双栈共享空间、用栈模拟递归。下面我按这个思路把每类题目的解题逻辑和代码都给捋一遍。2. 顺序栈与链式栈两条路线一套逻辑2.1 顺序栈连续性带来的高效与局限顺序栈的底层是一个数组外加一个栈顶指针。栈顶指针指向的是当前栈顶元素的位置。初始化时栈为空栈顶指针一般设为 -1表示栈里没有元素。入栈操作先判断会不会溢出也就是栈是否已满。如果没满栈顶指针先加1再把新元素放进栈顶指针指向的位置。出栈操作先判断是不是空栈如果非空记录栈顶元素值然后栈顶指针减1。注意出栈时数组里那个位置还残留着旧值但我们通过栈顶指针的边界控制让这个旧值永远不会再被访问到这就算真正“删除了”。C的类模板定义教材里一般是这样template typename T class SeqStack { private: T* data; // 动态数组 int top; // 栈顶指针空栈为 -1 int capacity; // 容量 public: SeqStack(int maxSize 100); ~SeqStack(); bool push(const T item); bool pop(T item); bool getTop(T item) const; bool isEmpty() const; bool isFull() const; };核心的push和pop实现我会这样写template typename T bool SeqStackT::push(const T item) { if (isFull()) { return false; // 栈满入栈失败 } data[top] item; // 先移动指针再赋值 return true; } template typename T bool SeqStackT::pop(T item) { if (isEmpty()) { return false; // 栈空出栈失败 } item data[top--]; // 先取元素再移动指针 return true; }这里两个细节新手特别容易写反push时是先加指针再赋值pop时是先赋值再减指针。为什么会这样设计因为栈顶指针永远指向最后一个有效元素。入栈时新元素要放到老栈顶的“上面”一格所以指针先往上走出栈时要把栈顶元素拿走所以先取值再把指针往下收。如果你用静态数组写顺序栈还要留意容量上限。课后题里经常有个“判断栈满”的题你要明确栈满的条件是 top capacity - 1不是 top capacity。这个“减1”的边界问题笔试和机试都是高频失分点。2.2 链式栈不设上限的弹性选择链式栈的底层是单链表但操作被限制了只能在表头插入和删除。所以链式栈的入栈相当于头插法出栈相当于删除头结点。链式栈不用判断“栈满”除非内存真的耗尽了这是它相比顺序栈最大的优势。但代价是每个元素多存一个指针域内存占用略高而且频繁动态申请释放节点运行效率上可能不如顺序栈稳定。链栈的类定义核心是节点结构和入栈出栈template typename T class LinkStack { private: struct Node { T data; Node* next; Node(const T value, Node* n nullptr) : data(value), next(n) {} }; Node* topNode; // 栈顶指针指向链表的头结点 public: LinkStack(); ~LinkStack(); bool push(const T item); bool pop(T item); bool getTop(T item) const; bool isEmpty() const; };入栈template typename T bool LinkStackT::push(const T item) { Node* newNode new Node(item, topNode); topNode newNode; return true; }出栈template typename T bool LinkStackT::pop(T item) { if (isEmpty()) { return false; } Node* temp topNode; item temp-data; topNode temp-next; delete temp; return true; }这里有个坑出栈时一定要先保存被删除的节点指针再移动栈顶指针最后delete。顺序写反的话你会删掉一个新节点或者对悬空指针操作直接崩溃。做题时我不建议追求一次写对而是写完立刻做一次“指针走查”模拟入栈1、2、3、出栈一次看指针有没有丢链。2.3 两种方案的选择逻辑课后题如果只要求“实现一个栈”默认选顺序栈因为代码简单、好调试。但题目如果出现“元素个数不确定”或者“实时插入删除”的描述链栈更稳妥。我个人的选择标准是这样栈的最大规模能提前估算且操作频繁——选顺序栈cache命中率高、分配内存次数少性能更好栈的规模不可预知可能很大——选链式栈避免扩容带来的移动成本。另外如果题目明确要求“不使用动态数组只能用链表”那就老老实实写链栈。3. 典型课后题逐题拆解从读题到AC的全过程3.1 括号匹配检查栈应用的第一个实战题目通常这样出给定一个只包含(,),[,],{,}的字符串判断括号是否正确闭合。比如{[()]}是合法的{[(])}就不合法({)]也不合法。正确的配对不仅是左右数量相等顺序也必须严格匹配。算法的核心逻辑遍历字符串遇到左括号就入栈遇到右括号先看栈是否为空——如果为空说明右括号没有对应左括号直接判定非法如果非空取出栈顶左括号判断类型是否匹配遍历结束后如果栈不为空说明有多余的左括号同样判定非法。#include stack #include string #include iostream bool isMatching(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char topC st.top(); st.pop(); if (!isMatching(topC, c)) return false; } } return st.empty(); }这题容易出错的地方是判断右括号时先st.top()再st.pop()如果忘了先检查empty空栈调用top()是未定义行为某些环境下直接崩溃。我做题时的习惯是在纸上先写两个测试用例一个合法串()[{}]一个非法串([)]然后手动走一遍程序确认每个分支都覆盖到。这样不仅能验证代码还能帮你熟悉“栈整个过程的状态变化”——栈只在处理左括号时增长遇到匹配的右括号时收缩如果有交叉嵌套栈顶和当前右括号对不上就会提前暴露问题。3.2 中缀表达式转后缀考的是思路不是语法这种题在课后题里通常是“设计算法”和要求手写结果。中缀表达式是a b * c后缀逆波兰表达式是a b c * 。转换的规则用栈来实现思路是这样的操作数直接输出遇到左括号入栈遇到右括号不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符比较它与栈顶运算符的优先级。如果当前运算符优先级低于或等于栈顶就把栈顶运算符弹出并输出然后再比较新的栈顶直到栈顶优先级更低或栈空最后把当前运算符入栈遍历结束后把栈中剩余的运算符依次弹出输出这里最常见的错误是把“等于”的情况弹栈搞反了。比如表达式a - b - c按左结合性相当于(a - b) - c所以减法遇到栈顶也是减法时必须先弹出栈顶再入栈当前这样得到后缀才是a b - c -。如果你只在当前优先级“低于”栈顶时才弹等于时不弹会得到a b c - -这实际上对应的中缀是a - (b - c)结果就错了。优先级表可以这样记运算符优先级*/2-1(0只在栈内作为边界标记补充一个平时练习时用的技巧用栈做表达式转换可以准备一组表达式先用手算后缀再用程序跑一遍对照结果。我建议至少测这几类纯加减混合、乘除嵌套括号、多层层层嵌套、括号内部只有一个操作数的情况比如(-a)这种。3.3 数值进制转换栈天然解决逆序输出进制转换的题目一般要求输入一个十进制整数n输出其r进制表示。算法是连除法不断用 n 除以 r取余数直到 n 变为 0然后逆序输出这些余数。“逆序输出”这个特征恰恰是栈的用武之地。入栈顺序是低位到高位出栈顺序就是高位到低位。代码写出来非常短void convert(int n, int r) { std::stackchar st; const std::string digits 0123456789ABCDEF; while (n 0) { st.push(digits[n % r]); n / r; } while (!st.empty()) { std::cout st.top(); st.pop(); } std::cout std::endl; }有同学可能会问这不就是一个循环倒着输出的事吗为什么要用栈你要知道课堂上讲数据结构从来不只是为了让你实现某个具体功能而是要抽象出一类“共性需求”。逆序输出是一个场景后面要讲的递归现场恢复、编译器括号匹配、表达式求值这些统统是“先做的事情后完成”。当你养成了“遇到有逆序或回退需求的场景就想到用栈”的思维习惯这些课后题才算没白做。3.4 双栈共享一个数组一类经典的空间优化题这道题是第二章最有含金量的题目之一。要求用一个一维数组实现两个栈两个栈共同占用这块空间如何设计入栈、出栈、判空、判满经典方案是“两端生长”两个栈的栈底分别位于数组的两端栈顶向中间移动。栈1从数组下标0开始向上增长栈2从数组末尾开始向下增长。栈1的空栈指针是top1 -1栈2的空栈指针是top2 capacity。栈满的条件是top1 1 top2说明两个栈顶已经相邻空间用尽。入栈1判满然后data[top1] item。入栈2判满然后data[--top2] item。template typename T class DualStack { private: T* data; int top1, top2; int capacity; public: DualStack(int maxSize 100); bool pushLeft(const T item); bool pushRight(const T item); bool popLeft(T item); bool popRight(T item); bool isEmptyLeft() const { return top1 -1; } bool isEmptyRight() const { return top2 capacity; } bool isFull() const { return top1 1 top2; } };这道题暗含着一个非常重要的思想两个操作方向相反的栈往往可以共享同一段存储空间达到空间利用率的提升。课后题里还有个相似的变形两个队列能不能共享空间答案是不能用同样的“两端生长”思路因为队列需要在两端操作共享空间会很麻烦。这个对比记忆下来写题时能少走很多弯路。栈1和栈2的空闲条件判断我见过很多人写错top1 top2这种写法就是错的。正确的判断是两者相邻也就是top2 - top1 1。往左栈压一个元素时栈1指针向索引2的方向增长往右栈压一个元素时栈2指针向索引变小的方向增长。容易弄混的地方就在于栈2增长的数值方向是负数方向但判断栈满仍然只看两个指针是否相邻。4. 应用场景题栈能解决哪些“看似不相关”的问题4.1 用栈模拟递归调用有一种常见题型不用递归用栈来写出某个递归函数的非递归版本。比如求斐波那契数列或者写一个非递归的汉诺塔。这里的关键是理解“递归函数在系统层面是怎么被执行的”——每一步调用都会生成一个“活动记录”压在系统栈上里面包含参数、局部变量、返回地址。递归返回时系统从栈顶弹出记录恢复现场继续执行。课后题里让你“用栈模拟递归”本质不是让你优化性能而是让你用显式栈去复刻这个“栈帧”的压入和弹出过程。举个例子非递归中序遍历二叉树后续章节的内容就是显式栈的典型应用但第二章里你只需要理解凡是一个问题能被拆成子问题、且子问题完成后需要回到之前的某个状态继续处理这个“回退”行为就可以由栈来完成。我在做这类题时的经验是先画出递归调用的“人字形”展开图标清楚每一层进入时压了什么、返回时弹了什么再往下写代码。直接上来敲代码大概率会漏掉某个状态的恢复导致程序死循环。4.2 回文判定两边同时比较的对称问题判断一个字符串是不是回文正读反读相同可以用栈前半段入栈后半段逐个和栈顶比较。奇数长度时正中间字符不用参与比较先跳过。这个题看起来简单但考的是对“栈的容量控制”的敏感度。对长度为 n 的串你只需要压入前面n/2个字符。遍历后半段时每读一个字符就和栈顶比对相同就弹出不相同直接判假。如果最终栈被弹空说明是回文否则不是。这里我补充一个容易忽略的细节当 n 为奇数时比如abcba前半段压入的是a、b中间字符c不需要入栈从后半段第一个元素b开始比较即可。很多同学把这个中间字符也压进去比较的时候就会多出一次不匹配。处理办法是先算half n / 2压入前 half 个如果 n 是奇数循环比较时从索引half 1开始跳过中间位。4.3 浏览器前进后退与编辑器的撤销操作有些应用题会问“如何设计浏览器的前进后退功能”。这个题一般不会要求完整代码而是让你描述方案两个栈一个存“后退历史”一个存“前进历史”。点击新页面时把当前页面压入后退栈清空前进栈点后退时把当前页面压入前进栈从后退栈弹出页面点前进时则反向操作。编辑器的“撤销”也是同理每次操作压入撤销栈撤销时从撤销栈弹出并执行反向操作同时压入重做栈。这个方案还能延伸出“撤销之后新做操作会清空重做栈”的细节——很多软件就是这么设计的。这类题之所以常出现在第二章的课后题中是因为它考察的不是“你背没背过栈的定义”而是“你能不能识别出现实需求里的栈结构”。我建议你把“两个栈、方向相反的流动”这个模型记下来类似的题都能套用。5. 易错点与调试技巧把踩过的坑提前帮你踩一遍5.1 栈满和栈空的判断顺序顺序栈的代码最常见的Bug长这样if (top capacity) { ... } // 错误top 最大只能是 capacity - 1以及if (top 0) { ... } // 错误栈空时 top -1这两个错误本质上都是“边界值没把握准确”。我自己写代码的习惯是把栈允许的状态穷举一遍。顺序栈容量为 5 时top的合法范围是 -1 到 4。-1空栈01个元素45个元素栈满5下标越界不允许出现。每次写 push 之前先问自己当前是 -1 到 4 的哪一个会不会变成 5pop 之前问当前会不会是 -1这样一梳理边界就不容易错了。5.2 值传递导致栈内容没变化写栈的类成员函数时pop的参数应该是引用还是值这个细节很多人没注意。如果你写成bool pop(T item); // 错误外部变量收不到弹出的值那弹出的数据只存在于函数内部的拷贝里出了函数就丢了。正确写法是bool pop(T item)。同理push的参数建议传常量引用const T item避免不必要的拷贝。虽然对 int 这种基本类型差别不大但如果 T 是字符串或者自定义对象值传递会产生临时对象性能差很多。这属于“好的编码习惯”范畴数据结构课作业里不扣分到了工程实践里很重要。5.3 链栈节点的内存泄漏链栈的析构函数如果只写了delete topNode必然泄漏其他节点。正确做法是循环释放template typename T LinkStackT::~LinkStack() { while (topNode ! nullptr) { Node* temp topNode; topNode topNode-next; delete temp; } }这个循环的顺序和 pop 一样先保存旧栈顶移动指针再删除。不要纠结“省一个临时变量”有时候省掉的临时变量就是内存泄漏的根源。我在教别人调试链栈问题时常让他们做一件事把栈变成“可视化”的写一个打印函数从左到右依次打印栈顶到栈底的所有元素。这样做有一个好处每次 push、pop、甚至析构之前都打印一次当前状态出问题就能立刻定位到是哪一步操作导致指针悬空或链表断裂。5.4 用标准库stack做题的正确姿势如果课后题没有强制要求手写栈直接用std::stack可以节省大量时间。但要注意std::stack的默认底层容器是std::deque不是std::vector。队列这种双端结构作为底层实现提供了在头部快速插入删除的能力。如果你希望底层是 vector可以这样声明std::stackint, std::vectorint st;这个知识点不会考你“ deque 和 vector 谁更快”的结论但你知道std::stack可以指定底层容器说明你对 STL 适配器有理解写代码时也更有掌控感。6. 从课后题到实战栈在真实系统里是怎么发光的学完第二章你可能会问这些题目我考试会做了但实际开发里栈到底用来干嘛我说三个最常见的真实场景第一个是函数调用。每次你调用一个函数系统会把返回地址、参数、局部变量压入调用栈函数返回时栈帧弹出。递归栈溢出本质上就是这个系统栈被压满了。理解了这一点你就能明白为什么递归深度过大会段错误。第二个是编译器的语法分析。解析表达式、检查括号匹配、生成后缀代码统统离不开栈。就连 JSON 解析器里处理嵌套花括号也会用到栈来追踪当前所处层级。第三个是深度优先搜索DFS。图算法里DFS 可以递归实现也可以用显式栈实现。显式栈的好处是避免了系统递归的开销和深度限制。这里我先不展开图的细节但你心里要有个数栈不是数据结构课本里的一个孤立章节它是后续树、图、算法设计的地基。从学习路径来看第二章的课后题做扎实了后面学的队列、递归、二叉树非递归遍历、图的深度优先遍历都会轻松很多。尤其“用栈模拟递归”这一节你在第二章就掌握好到第六章学二叉树时会少掉不少头发。我再简单回顾一下刷题时的自查清单每次 push、pop、getTop 之前是否检查了栈满/栈空pop/top 的参数是否用了引用传出链栈删除节点时是否先保存指针再释放使用两个栈的场景栈满条件是否在两个栈顶之间判断就我个人经验做这一章的题目最有价值的收获不是背会了哪个具体算法而是建立起“栈是一种管理暂时性数据的容器”的直觉。拿到题目先问自己这里有没有“暂时存放、后续逆序处理”的需求有就用栈。这个思维模式会跟着你走完整个数据结构课程甚至陪你走过工作后面试和实际项目里各种场景。
1. 先把你对栈的理解从“背定义”升级到“画图”第二章“栈”其实是个分水岭。前面学的线性表、顺序表、链表本质上都是线性结构操作无非是增删改查。但栈不一样它只允许在一端插入和删除这个“操作受限”的设计是为了满足一种极其常见的需求暂时保存现场回头再恢复。很多同学学完这一章能背出“栈是先进后出的线性结构”但要让他手写一个括号匹配算法或者讲讲函数递归调用时系统具体做了什么就卡壳了。课后题的价值就在于帮你把这些抽象概念变成能跑起来的代码。我习惯把栈理解成一个“只开一头的箱子”。放东西叫入栈push拿东西叫出栈pop但你只能从开口那一端操作。你放进去的顺序是1、2、3拿出来就得是3、2、1。栈的抽象数据类型ADT也就三个核心操作push、pop、top或者叫peek只读栈顶不出栈。注意栈在逻辑上只有栈顶一端开放但物理存储上既可以用连续空间数组实现也可以用离散空间链表实现。这两种实现方式各有各的适用场景课后题里往往要求你分别写出类定义和核心操作这是本章必修的第一关。这一章课后的题目我大致归个类第一类是概念辨析题比如“栈和一般线性表的区别”“什么情况下用栈不用队列”第二类是基础实现题让你写顺序栈、链栈的类模板和push、pop代码第三类是应用场景题比如括号匹配、表达式转换、进制转换、回文判定第四类是扩展设计题比如双栈共享空间、用栈模拟递归。下面我按这个思路把每类题目的解题逻辑和代码都给捋一遍。2. 顺序栈与链式栈两条路线一套逻辑2.1 顺序栈连续性带来的高效与局限顺序栈的底层是一个数组外加一个栈顶指针。栈顶指针指向的是当前栈顶元素的位置。初始化时栈为空栈顶指针一般设为 -1表示栈里没有元素。入栈操作先判断会不会溢出也就是栈是否已满。如果没满栈顶指针先加1再把新元素放进栈顶指针指向的位置。出栈操作先判断是不是空栈如果非空记录栈顶元素值然后栈顶指针减1。注意出栈时数组里那个位置还残留着旧值但我们通过栈顶指针的边界控制让这个旧值永远不会再被访问到这就算真正“删除了”。C的类模板定义教材里一般是这样template typename T class SeqStack { private: T* data; // 动态数组 int top; // 栈顶指针空栈为 -1 int capacity; // 容量 public: SeqStack(int maxSize 100); ~SeqStack(); bool push(const T item); bool pop(T item); bool getTop(T item) const; bool isEmpty() const; bool isFull() const; };核心的push和pop实现我会这样写template typename T bool SeqStackT::push(const T item) { if (isFull()) { return false; // 栈满入栈失败 } data[top] item; // 先移动指针再赋值 return true; } template typename T bool SeqStackT::pop(T item) { if (isEmpty()) { return false; // 栈空出栈失败 } item data[top--]; // 先取元素再移动指针 return true; }这里两个细节新手特别容易写反push时是先加指针再赋值pop时是先赋值再减指针。为什么会这样设计因为栈顶指针永远指向最后一个有效元素。入栈时新元素要放到老栈顶的“上面”一格所以指针先往上走出栈时要把栈顶元素拿走所以先取值再把指针往下收。如果你用静态数组写顺序栈还要留意容量上限。课后题里经常有个“判断栈满”的题你要明确栈满的条件是 top capacity - 1不是 top capacity。这个“减1”的边界问题笔试和机试都是高频失分点。2.2 链式栈不设上限的弹性选择链式栈的底层是单链表但操作被限制了只能在表头插入和删除。所以链式栈的入栈相当于头插法出栈相当于删除头结点。链式栈不用判断“栈满”除非内存真的耗尽了这是它相比顺序栈最大的优势。但代价是每个元素多存一个指针域内存占用略高而且频繁动态申请释放节点运行效率上可能不如顺序栈稳定。链栈的类定义核心是节点结构和入栈出栈template typename T class LinkStack { private: struct Node { T data; Node* next; Node(const T value, Node* n nullptr) : data(value), next(n) {} }; Node* topNode; // 栈顶指针指向链表的头结点 public: LinkStack(); ~LinkStack(); bool push(const T item); bool pop(T item); bool getTop(T item) const; bool isEmpty() const; };入栈template typename T bool LinkStackT::push(const T item) { Node* newNode new Node(item, topNode); topNode newNode; return true; }出栈template typename T bool LinkStackT::pop(T item) { if (isEmpty()) { return false; } Node* temp topNode; item temp-data; topNode temp-next; delete temp; return true; }这里有个坑出栈时一定要先保存被删除的节点指针再移动栈顶指针最后delete。顺序写反的话你会删掉一个新节点或者对悬空指针操作直接崩溃。做题时我不建议追求一次写对而是写完立刻做一次“指针走查”模拟入栈1、2、3、出栈一次看指针有没有丢链。2.3 两种方案的选择逻辑课后题如果只要求“实现一个栈”默认选顺序栈因为代码简单、好调试。但题目如果出现“元素个数不确定”或者“实时插入删除”的描述链栈更稳妥。我个人的选择标准是这样栈的最大规模能提前估算且操作频繁——选顺序栈cache命中率高、分配内存次数少性能更好栈的规模不可预知可能很大——选链式栈避免扩容带来的移动成本。另外如果题目明确要求“不使用动态数组只能用链表”那就老老实实写链栈。3. 典型课后题逐题拆解从读题到AC的全过程3.1 括号匹配检查栈应用的第一个实战题目通常这样出给定一个只包含(,),[,],{,}的字符串判断括号是否正确闭合。比如{[()]}是合法的{[(])}就不合法({)]也不合法。正确的配对不仅是左右数量相等顺序也必须严格匹配。算法的核心逻辑遍历字符串遇到左括号就入栈遇到右括号先看栈是否为空——如果为空说明右括号没有对应左括号直接判定非法如果非空取出栈顶左括号判断类型是否匹配遍历结束后如果栈不为空说明有多余的左括号同样判定非法。#include stack #include string #include iostream bool isMatching(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char topC st.top(); st.pop(); if (!isMatching(topC, c)) return false; } } return st.empty(); }这题容易出错的地方是判断右括号时先st.top()再st.pop()如果忘了先检查empty空栈调用top()是未定义行为某些环境下直接崩溃。我做题时的习惯是在纸上先写两个测试用例一个合法串()[{}]一个非法串([)]然后手动走一遍程序确认每个分支都覆盖到。这样不仅能验证代码还能帮你熟悉“栈整个过程的状态变化”——栈只在处理左括号时增长遇到匹配的右括号时收缩如果有交叉嵌套栈顶和当前右括号对不上就会提前暴露问题。3.2 中缀表达式转后缀考的是思路不是语法这种题在课后题里通常是“设计算法”和要求手写结果。中缀表达式是a b * c后缀逆波兰表达式是a b c * 。转换的规则用栈来实现思路是这样的操作数直接输出遇到左括号入栈遇到右括号不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出遇到运算符比较它与栈顶运算符的优先级。如果当前运算符优先级低于或等于栈顶就把栈顶运算符弹出并输出然后再比较新的栈顶直到栈顶优先级更低或栈空最后把当前运算符入栈遍历结束后把栈中剩余的运算符依次弹出输出这里最常见的错误是把“等于”的情况弹栈搞反了。比如表达式a - b - c按左结合性相当于(a - b) - c所以减法遇到栈顶也是减法时必须先弹出栈顶再入栈当前这样得到后缀才是a b - c -。如果你只在当前优先级“低于”栈顶时才弹等于时不弹会得到a b c - -这实际上对应的中缀是a - (b - c)结果就错了。优先级表可以这样记运算符优先级*/2-1(0只在栈内作为边界标记补充一个平时练习时用的技巧用栈做表达式转换可以准备一组表达式先用手算后缀再用程序跑一遍对照结果。我建议至少测这几类纯加减混合、乘除嵌套括号、多层层层嵌套、括号内部只有一个操作数的情况比如(-a)这种。3.3 数值进制转换栈天然解决逆序输出进制转换的题目一般要求输入一个十进制整数n输出其r进制表示。算法是连除法不断用 n 除以 r取余数直到 n 变为 0然后逆序输出这些余数。“逆序输出”这个特征恰恰是栈的用武之地。入栈顺序是低位到高位出栈顺序就是高位到低位。代码写出来非常短void convert(int n, int r) { std::stackchar st; const std::string digits 0123456789ABCDEF; while (n 0) { st.push(digits[n % r]); n / r; } while (!st.empty()) { std::cout st.top(); st.pop(); } std::cout std::endl; }有同学可能会问这不就是一个循环倒着输出的事吗为什么要用栈你要知道课堂上讲数据结构从来不只是为了让你实现某个具体功能而是要抽象出一类“共性需求”。逆序输出是一个场景后面要讲的递归现场恢复、编译器括号匹配、表达式求值这些统统是“先做的事情后完成”。当你养成了“遇到有逆序或回退需求的场景就想到用栈”的思维习惯这些课后题才算没白做。3.4 双栈共享一个数组一类经典的空间优化题这道题是第二章最有含金量的题目之一。要求用一个一维数组实现两个栈两个栈共同占用这块空间如何设计入栈、出栈、判空、判满经典方案是“两端生长”两个栈的栈底分别位于数组的两端栈顶向中间移动。栈1从数组下标0开始向上增长栈2从数组末尾开始向下增长。栈1的空栈指针是top1 -1栈2的空栈指针是top2 capacity。栈满的条件是top1 1 top2说明两个栈顶已经相邻空间用尽。入栈1判满然后data[top1] item。入栈2判满然后data[--top2] item。template typename T class DualStack { private: T* data; int top1, top2; int capacity; public: DualStack(int maxSize 100); bool pushLeft(const T item); bool pushRight(const T item); bool popLeft(T item); bool popRight(T item); bool isEmptyLeft() const { return top1 -1; } bool isEmptyRight() const { return top2 capacity; } bool isFull() const { return top1 1 top2; } };这道题暗含着一个非常重要的思想两个操作方向相反的栈往往可以共享同一段存储空间达到空间利用率的提升。课后题里还有个相似的变形两个队列能不能共享空间答案是不能用同样的“两端生长”思路因为队列需要在两端操作共享空间会很麻烦。这个对比记忆下来写题时能少走很多弯路。栈1和栈2的空闲条件判断我见过很多人写错top1 top2这种写法就是错的。正确的判断是两者相邻也就是top2 - top1 1。往左栈压一个元素时栈1指针向索引2的方向增长往右栈压一个元素时栈2指针向索引变小的方向增长。容易弄混的地方就在于栈2增长的数值方向是负数方向但判断栈满仍然只看两个指针是否相邻。4. 应用场景题栈能解决哪些“看似不相关”的问题4.1 用栈模拟递归调用有一种常见题型不用递归用栈来写出某个递归函数的非递归版本。比如求斐波那契数列或者写一个非递归的汉诺塔。这里的关键是理解“递归函数在系统层面是怎么被执行的”——每一步调用都会生成一个“活动记录”压在系统栈上里面包含参数、局部变量、返回地址。递归返回时系统从栈顶弹出记录恢复现场继续执行。课后题里让你“用栈模拟递归”本质不是让你优化性能而是让你用显式栈去复刻这个“栈帧”的压入和弹出过程。举个例子非递归中序遍历二叉树后续章节的内容就是显式栈的典型应用但第二章里你只需要理解凡是一个问题能被拆成子问题、且子问题完成后需要回到之前的某个状态继续处理这个“回退”行为就可以由栈来完成。我在做这类题时的经验是先画出递归调用的“人字形”展开图标清楚每一层进入时压了什么、返回时弹了什么再往下写代码。直接上来敲代码大概率会漏掉某个状态的恢复导致程序死循环。4.2 回文判定两边同时比较的对称问题判断一个字符串是不是回文正读反读相同可以用栈前半段入栈后半段逐个和栈顶比较。奇数长度时正中间字符不用参与比较先跳过。这个题看起来简单但考的是对“栈的容量控制”的敏感度。对长度为 n 的串你只需要压入前面n/2个字符。遍历后半段时每读一个字符就和栈顶比对相同就弹出不相同直接判假。如果最终栈被弹空说明是回文否则不是。这里我补充一个容易忽略的细节当 n 为奇数时比如abcba前半段压入的是a、b中间字符c不需要入栈从后半段第一个元素b开始比较即可。很多同学把这个中间字符也压进去比较的时候就会多出一次不匹配。处理办法是先算half n / 2压入前 half 个如果 n 是奇数循环比较时从索引half 1开始跳过中间位。4.3 浏览器前进后退与编辑器的撤销操作有些应用题会问“如何设计浏览器的前进后退功能”。这个题一般不会要求完整代码而是让你描述方案两个栈一个存“后退历史”一个存“前进历史”。点击新页面时把当前页面压入后退栈清空前进栈点后退时把当前页面压入前进栈从后退栈弹出页面点前进时则反向操作。编辑器的“撤销”也是同理每次操作压入撤销栈撤销时从撤销栈弹出并执行反向操作同时压入重做栈。这个方案还能延伸出“撤销之后新做操作会清空重做栈”的细节——很多软件就是这么设计的。这类题之所以常出现在第二章的课后题中是因为它考察的不是“你背没背过栈的定义”而是“你能不能识别出现实需求里的栈结构”。我建议你把“两个栈、方向相反的流动”这个模型记下来类似的题都能套用。5. 易错点与调试技巧把踩过的坑提前帮你踩一遍5.1 栈满和栈空的判断顺序顺序栈的代码最常见的Bug长这样if (top capacity) { ... } // 错误top 最大只能是 capacity - 1以及if (top 0) { ... } // 错误栈空时 top -1这两个错误本质上都是“边界值没把握准确”。我自己写代码的习惯是把栈允许的状态穷举一遍。顺序栈容量为 5 时top的合法范围是 -1 到 4。-1空栈01个元素45个元素栈满5下标越界不允许出现。每次写 push 之前先问自己当前是 -1 到 4 的哪一个会不会变成 5pop 之前问当前会不会是 -1这样一梳理边界就不容易错了。5.2 值传递导致栈内容没变化写栈的类成员函数时pop的参数应该是引用还是值这个细节很多人没注意。如果你写成bool pop(T item); // 错误外部变量收不到弹出的值那弹出的数据只存在于函数内部的拷贝里出了函数就丢了。正确写法是bool pop(T item)。同理push的参数建议传常量引用const T item避免不必要的拷贝。虽然对 int 这种基本类型差别不大但如果 T 是字符串或者自定义对象值传递会产生临时对象性能差很多。这属于“好的编码习惯”范畴数据结构课作业里不扣分到了工程实践里很重要。5.3 链栈节点的内存泄漏链栈的析构函数如果只写了delete topNode必然泄漏其他节点。正确做法是循环释放template typename T LinkStackT::~LinkStack() { while (topNode ! nullptr) { Node* temp topNode; topNode topNode-next; delete temp; } }这个循环的顺序和 pop 一样先保存旧栈顶移动指针再删除。不要纠结“省一个临时变量”有时候省掉的临时变量就是内存泄漏的根源。我在教别人调试链栈问题时常让他们做一件事把栈变成“可视化”的写一个打印函数从左到右依次打印栈顶到栈底的所有元素。这样做有一个好处每次 push、pop、甚至析构之前都打印一次当前状态出问题就能立刻定位到是哪一步操作导致指针悬空或链表断裂。5.4 用标准库stack做题的正确姿势如果课后题没有强制要求手写栈直接用std::stack可以节省大量时间。但要注意std::stack的默认底层容器是std::deque不是std::vector。队列这种双端结构作为底层实现提供了在头部快速插入删除的能力。如果你希望底层是 vector可以这样声明std::stackint, std::vectorint st;这个知识点不会考你“ deque 和 vector 谁更快”的结论但你知道std::stack可以指定底层容器说明你对 STL 适配器有理解写代码时也更有掌控感。6. 从课后题到实战栈在真实系统里是怎么发光的学完第二章你可能会问这些题目我考试会做了但实际开发里栈到底用来干嘛我说三个最常见的真实场景第一个是函数调用。每次你调用一个函数系统会把返回地址、参数、局部变量压入调用栈函数返回时栈帧弹出。递归栈溢出本质上就是这个系统栈被压满了。理解了这一点你就能明白为什么递归深度过大会段错误。第二个是编译器的语法分析。解析表达式、检查括号匹配、生成后缀代码统统离不开栈。就连 JSON 解析器里处理嵌套花括号也会用到栈来追踪当前所处层级。第三个是深度优先搜索DFS。图算法里DFS 可以递归实现也可以用显式栈实现。显式栈的好处是避免了系统递归的开销和深度限制。这里我先不展开图的细节但你心里要有个数栈不是数据结构课本里的一个孤立章节它是后续树、图、算法设计的地基。从学习路径来看第二章的课后题做扎实了后面学的队列、递归、二叉树非递归遍历、图的深度优先遍历都会轻松很多。尤其“用栈模拟递归”这一节你在第二章就掌握好到第六章学二叉树时会少掉不少头发。我再简单回顾一下刷题时的自查清单每次 push、pop、getTop 之前是否检查了栈满/栈空pop/top 的参数是否用了引用传出链栈删除节点时是否先保存指针再释放使用两个栈的场景栈满条件是否在两个栈顶之间判断就我个人经验做这一章的题目最有价值的收获不是背会了哪个具体算法而是建立起“栈是一种管理暂时性数据的容器”的直觉。拿到题目先问自己这里有没有“暂时存放、后续逆序处理”的需求有就用栈。这个思维模式会跟着你走完整个数据结构课程甚至陪你走过工作后面试和实际项目里各种场景。
