很多人学《数据结构C语言版 第2版》时前两章线性表还能靠背代码糊弄过去到了第三章栈和队列突然发现课后习题完全不知道从哪下手。严蔚敏这本教材的第三章表面上是讲两种基本数据结构实际考的却是“你能不能根据受限操作倒推出应用场景”这正好是期末和考研最喜欢出题的地方。这篇文章我就把第三章最常见的几类课后题全部拆开从思路到可运行的C语言代码再到那些老师不写在板书上的易错点一次讲清楚。适合正在复习考研数据结构、期末冲刺或者自学卡在第三章的同学直接对照着练。1. 第三章课后题到底在考什么——先看清题目背后的出题逻辑很多同学拿到课后习题第一反应是“这题我代码能跑但题不会做”问题就出在没弄明白这一章的本质。1.1 章节定位为什么栈和队列这么基础却总让人栽跟头栈和队列其实是“操作受限的线性表”。线性表可以在任意位置插入删除栈只能在栈顶操作队列只能一端入、另一端出。这个“受限”不是缺点反而让它们有了明确的语义栈天然解决“后进先出”的问题队列天然解决“先进先出”的问题。课后习题考察的核心就一句话给你一个实际场景你能否识别出它需要的是哪种受限操作并利用该结构的特性完成算法。所以书中算法题不会直接让你背诵 Define 栈的六个基本操作而是会问“利用栈实现十进制转二进制”“判断回文串”“表达式求值”这类应用题。1.2 高频题型总览这些题实际上是一类题我把第三章高频课后题整理成一个题型表刷题前先对号入座题型分类代表题目核心考点常见丢分点栈基础操作数制转换、回文判断、共享栈LIFO特性、判满判空忘记特判n0栈应用括号匹配、表达式求值优先级处理、出入栈时机左括号与右括号处理不对称队列操作循环队列、链队列、双端队列判满判空的多种方案浪费一个存储单元的约定递归相关汉诺塔、斐波那契系统栈、递归转非递归时间复杂度分析错误综合设计判断合法出栈序列模拟入栈出栈过程只凭头尾判断而不全程模拟你会发现这些题都在反复使用同一个思维流程判断场景是否符合某种受限操作特性再决定选哪种存储结构最后写操作代码。下面按这个流程逐类拆解。2. 栈的基础操作题数制转换、回文判断、共享栈的完整代码拆解这一节的三道题是第三章最有代表性的“栈应用题”考试出现频率极高代码量不大但细节很多。2.1 数制转换为什么栈天然适合做“倒序输出”的事十进制转二进制用的是“除2取余倒序排列”转八进制就是除8取余。核心问题是我们计算余数的顺序是从低位到高位但输出结果必须从高位到低位。这不就是后进先出吗我建议不要直接用数组逆序输出因为这道题考的就是你能不能想到用栈。参考实现如下#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SqStack; // 初始化栈顶指向-1 void InitStack(SqStack *S) { S-top -1; } int Push(SqStack *S, int x) { if (S-top MAXSIZE - 1) return 0; // 栈满 S-data[S-top] x; return 1; } int Pop(SqStack *S, int *x) { if (S-top -1) return 0; // 栈空 *x S-data[S-top--]; return 1; } // 十进制转二进制n 0 void Conversion(int n) { SqStack S; InitStack(S); while (n 0) { Push(S, n % 2); n / 2; } while (S.top ! -1) { int e; Pop(S, e); printf(%d, e); } printf(\n); } int main() { Conversion(13); // 输出 1101 return 0; }这段代码看起来简单但有两个必须注意的坑。第一n 0时循环一次都不执行输出结果是空行正确的做法是单独判断if (n 0) printf(0);。第二栈数组data[MAXSIZE]在实际考试中经常要考虑上界问题如果数字很大要么把 MAXSIZE 调大要么改用动态分配的栈空间。2.2 回文判断栈和队列“一对碰”的思路判断一个字符串是否是回文串正读反读都一样常规解法是双指针但课后习题要求的偏偏是用栈实现。为什么因为回文本质上是“后半部分应该等于前半部分的逆序”逆序操作就是栈的看家本领。思路有两种一种是整体入栈再逐个弹出与原串比较另一种是将前一半入栈再遍历后一半时逐个弹出比较。第二种效率更好也更贴合考点。难点在于字符串长度的奇偶性如果长度为奇数中间那个字符不需要参与比较。#include stdio.h #include string.h #define MAX 100 typedef struct { char data[MAX]; int top; } CharStack; int IsPalindrome(char *s) { int len strlen(s); CharStack stack; stack.top -1; // 将前半部分入栈 int half len / 2; for (int i 0; i half; i) { stack.data[stack.top] s[i]; } // 如果长度为奇数跳过中间字符 int start (len % 2 0) ? half : half 1; for (int i start; i len; i) { if (stack.top -1) return 0; if (stack.data[stack.top--] ! s[i]) return 0; } return stack.top -1; } int main() { printf(%d\n, IsPalindrome(abcba)); // 1 printf(%d\n, IsPalindrome(abccba)); // 1 printf(%d\n, IsPalindrome(hello)); // 0 return 0; }写完这段代码我特别提醒一句算法结束前一定要确认栈是否为空。有些写法在遍历还没结束时就已经排除了所有字符最后栈却不为空说明前半部分没比完这往往是长度奇偶判断写错导致的。2.3 共享栈两个栈共用一个数组的边界处理共享栈是第三章容易被忽略但考试爱出的小题。它在一个数组里开两个栈下标0和下标n-1分别作为两个栈底两个栈顶相向生长。这样做的好处是内存利用率高一个栈空闲时可以给另一个用。共享栈的边界条件比普通栈麻烦栈1为空top1 -1栈2为空top2 MAXSIZE栈满top1 1 top2核心操作代码#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top1; int top2; } SharedStack; void InitSharedStack(SharedStack *S) { S-top1 -1; S-top2 MAXSIZE; } int PushShared(SharedStack *S, int tag, int x) { if (S-top1 1 S-top2) return 0; // 栈满 if (tag 1) { S-data[S-top1] x; } else if (tag 2) { S-data[--S-top2] x; } return 1; } int PopShared(SharedStack *S, int tag, int *x) { if (tag 1) { if (S-top1 -1) return 0; *x S-data[S-top1--]; } else { if (S-top2 MAXSIZE) return 0; *x S-data[S-top2]; } return 1; }这一类题的丢分点几乎全在top2的处理上入栈是--S-top2出栈是S-top2方向不能搞反。如果实在记不住就想想栈2的栈顶指针初始在数组末尾入栈时指针必须向左移动才能腾出位置。3. 表达式求值题中缀转后缀优先级表才是灵魂第三章里面最能让考研人头疼的题目就是表达式求值。教材用的是“算符优先法”课后题经常要求你手写中缀表达式转后缀表达式再写代码求值。3.1 中缀转后缀的手算规则中缀表达式a b * c - d对应的后缀表达式是a b c * d -。手算规则只有三条操作数直接输出。遇到运算符时如果栈顶运算优先级不低于当前运算符则不断弹出栈顶并输出直到栈空或栈顶优先级更低。左括号直接入栈右括号则弹栈输出直到遇到左括号左括号本身不输出。举个例子(a b) * c - d遇到(a输出a入栈。遇到b输出b。遇到)弹栈输出丢弃左括号。遇到*此时栈空入栈。遇到c输出c。遇到-*优先级高于-弹出*然后-入栈。遇到d输出d。结束时弹出栈内剩余-。最终结果是a b c * d -。3.2 中缀转后缀的C语言实现注意左括号在栈内和栈外的优先级必须区分在栈外优先级最高直接入栈一旦进了栈优先级要降到最低以确保右括号出现前不会被中途弹出。#include stdio.h #include string.h char stack[100]; int top -1; int priority_out(char c) { if (c () return 10; if (c || c -) return 1; if (c * || c /) return 2; return 0; } int priority_in(char c) { if (c () return 0; if (c || c -) return 1; if (c * || c /) return 2; return 0; } int isOperator(char c) { return c || c - || c * || c /; } void InfixToPostfix(char *infix, char *postfix) { int j 0; for (int i 0; infix[i] ! \0; i) { char c infix[i]; if (c a c z) { postfix[j] c; // 操作数直接输出 } else if (c () { stack[top] c; } else if (c )) { while (top ! -1 stack[top] ! () { postfix[j] stack[top--]; } if (top ! -1) top--; // 丢弃左括号 } else if (isOperator(c)) { while (top ! -1 priority_in(stack[top]) priority_out(c)) { postfix[j] stack[top--]; } stack[top] c; } } while (top ! -1) { postfix[j] stack[top--]; } postfix[j] \0; } int main() { char infix[] (ab)*c-d; char postfix[100]; InfixToPostfix(infix, postfix); printf(%s\n, postfix); // abc*d- return 0; }这里最容易出bug的地方是循环弹栈时的比较符号必须是不是。如果只弹出优先级更高的情况遇到连续的加减或连续的乘除时后缀表达式的运算顺序就会错误。这一点我在批改同学代码时见过无数次。3.3 后缀表达式求值栈里存数字挨个算后缀表达式的特点是运算符在两个操作数之后求值只需要一个数字栈遇到数字入栈遇到运算符弹出两个操作数先弹出的是右操作数后弹出的是左操作数。这里有一个常见的低级错误——减法除法时后弹出的数要写在运算符左边反过来结果就错了。以处理个位数为例#include stdio.h int stack[100]; int top -1; int compute(int a, int b, char op) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: return b 0 ? 0 : a / b; } return 0; } int evalPostfix(char *postfix) { for (int i 0; postfix[i] ! \0; i) { char c postfix[i]; if (c 0 c 9) { stack[top] c - 0; } else if (c || c - || c * || c /) { int right stack[top--]; // 先弹出的数 int left stack[top--]; // 后弹出的数 stack[top] compute(left, right, c); } } return stack[top]; }如果是多位数比如123 456需要在扫描时连续读数字等遇到空格或运算符再入栈。标准做法是允许表达式用空格分隔操作数扫描时遇到数字就把一整串数字合并成一个整数。3.4 避坑负数、括号、除数为0怎么处理这三个坑是课后题里边边角角的加分点。处理负数最简单的方式是把它看成0 - x比如-5转换为后缀时就是0 5 -。另一种方式是给单目负号定义一个独立优先级但写起来复杂很多考试一般不要求。除数为0必须先判断。很多参考代码直接a / bb为0时C语言程序会异常终止。我在自己测试时发现某些评分系统会故意输入除数为0的用例来考察这个点。4. 循环队列和链队列习题判满判空那点事最容易翻车队列部分的课后题比栈更细碎因为循环队列的判满判空有不止一种实现方案很多同学只背一种题目稍微变化就懵了。4.1 循环队列为什么非要浪费一个格子顺序队列如果用普通数组假溢出问题很严重——队头元素出队后前面空间就浪费了。循环队列通过模运算把数组头尾相接解决假溢出。可是问题来了队列空时front rear如果队列满时也刚好front rear就无法区分空和满。解决方案就是约定牺牲一个存储单元。队满条件是(rear 1) % MAXSIZE front这样“满”状态会比实际容量少一格。具体操作队空front rear队满(rear 1) % MAXSIZE front队列长度(rear - front MAXSIZE) % MAXSIZE你会看到很多题直接说“循环队列的容量是MaxSize实际最多存储MaxSize-1个元素”原因就在这里。4.2 初始化、入队、出队的标准写法#define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一位置 } SqQueue; void InitQueue(SqQueue *Q) { Q-front Q-rear 0; } int EnQueue(SqQueue *Q, int x) { if ((Q-rear 1) % MAXSIZE Q-front) return 0; // 队满 Q-data[Q-rear] x; Q-rear (Q-rear 1) % MAXSIZE; return 1; } int DeQueue(SqQueue *Q, int *x) { if (Q-front Q-rear) return 0; // 队空 *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }入队时的模运算非常关键不能直接写rear那样会越界。我见过很多自学同学写的队列代码第一次入队正常入队到数组末尾时直接内存越界。一定要保证每次移动都取模。4.3 条件判满/计数判满/标志位判满三种方案怎么选除了浪费一个存储单元的方案教材和习题里还可能出现另外两种判满方案方案判满条件优点缺点牺牲一个单元(rear1)%MaxSize front判断简单少存一个元素增加size计数器size MaxSize不浪费空间每次入队出队要维护size增加tag标志位frontrear tag1不浪费空间逻辑稍复杂课后题如果明确说“不允许浪费存储空间”你就得用后两种。tag方案的思路是定义一个变量tag入队时置1出队时置0当front rear时看tag的值tag为1说明刚入队导致满tag为0说明刚出队导致空。这是考试喜欢出的变形题。4.4 链队列带头尾指针的链表实现链队列用单链表实现需要维护头指针front和尾指针rear。入队相当于尾插出队相当于头删。typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; void InitLinkQueue(LinkQueue *Q) { Q-front Q-rear (QNode*)malloc(sizeof(QNode)); Q-front-next NULL; } void EnLinkQueue(LinkQueue *Q, int x) { QNode *s (QNode*)malloc(sizeof(QNode)); s-data x; s-next NULL; Q-rear-next s; Q-rear s; } int DeLinkQueue(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 (p Q-rear) Q-rear Q-front; // 删的是唯一元素 free(p); return 1; }链队列最容易错的不是入队而是出队后如果队列变成空必须把rear指回front。如果不这么处理下一次入队时会通过一个已释放的指针访问内存。这个问题在选择题里经常以“删除最后一个元素后rear指针指向哪里”的形式出现。5. 递归题的本质汉诺塔和斐波那契背后的栈第三章习题里有一类题看起来和栈无关但本质是栈的应用——递归。教材里汉诺塔和斐波那契的题表面问“写出递归算法”实际考察的是你对“系统栈”的理解。5.1 递归为什么能执行系统栈帮我们记了什么每次函数调用时系统会把返回地址、局部变量、参数压入运行栈函数返回时再从栈顶恢复。所以递归的执行过程就是一次次的压栈和弹栈。课后题如果要求你用非递归方式实现递归算法本质就是让你用自定义栈模拟系统的运行栈。5.2 汉诺塔的递归解法和移动次数汉诺塔问题用递归写非常简洁n个圆盘从A移到C借助Bvoid Hanoi(int n, char A, char B, char C) { if (n 1) { printf(Move disk %d from %c to %c\n, n, A, C); return; } Hanoi(n - 1, A, C, B); // 上面n-1个从A移到B printf(Move disk %d from %c to %c\n, n, A, C); Hanoi(n - 1, B, A, C); // 再从B移到C }移动次数有递推公式T(n) 2T(n-1) 1解出来是T(n) 2^n - 1。这个公式在习题里经常出现如果题目不要求写代码只问次数直接用公式。5.3 递归转非递归显式栈是怎么模拟的以中序遍历二叉树为例第四章会用到但第三章递归题也会提前涉及非递归版本需要一个显式栈来模拟系统栈。虽然二叉树还没系统学但你可以理解成用栈保存“待处理的节点”先把左子树一路压栈弹栈时访问节点再转向右子树。这种转换题的通用套路是找出递归函数里每一个递归调用点、局部变量、返回点把它们打包成结构体压栈。考试一般只要求写核心思路不要求写出完整的可运行代码但会用选择题考你栈中保存的字段。5.4 斐波那契两种写法的复杂度差异斐波那契数列用递归写int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }看起来只有三行但时间复杂度是O(2^n)因为大量子问题被重复计算。比如fib(5)会计算两次fib(3)这个重复量随n增长极其恐怖。循环写法可以优化到O(n)int fib_iter(int n) { if (n 1) return n; int a 0, b 1; for (int i 2; i n; i) { int t a b; a b; b t; } return b; }这组对比经常以简答题形式出现问“递归求斐波那契的时间复杂度和空间复杂度”答案分别是O(2^n)和O(n)递归深度n。很多同学只答时间复杂度漏掉空间复杂度白白丢分。6. 那些“不显眼但爱考”的小题双端队列、边界条件与综合应用最后这部分是刷题时容易被忽略但考卷上往往占不小分值的题目类型。6.1 双端队列的概念题与操作题双端队列允许两端都能入队和出队。课本正文里没有像栈和队列那样花大篇幅讲习题却经常出。最容易考的是输入序列为1、2、3、4时用双端队列能否得到某个输出序列以及两个受限的双端队列输入受限/输出受限分别能产生哪些输出序列。做这类题不需要写代码画个队列图模拟即可。但要记住输出受限的双端队列两端都能入队只有一端能出队输入受限的双端队列只有一端能入队两端都能出队。考试问“下列哪个序列不能由输出受限双端队列得到”本质就是在考你在入队阶段能否通过两端交替插入让最终输出序列满足要求。6.2 边界条件总清单数组越界、空栈空队列、容量为1我把这一章最容易翻车的边界条件汇总成一张自查表写代码前逐条过一遍场景错误写法正确做法十进制转二进制n0循环不执行输出空单独输出“0”共享栈栈2入栈S-data[S-top2]S-data[--S-top2]循环队列判满rear1 front(rear1)%MaxSize front链队列删最后一个元素只改front不处理rear删除后令rear front后缀表达式除法先弹左操作数先弹右操作数后弹左操作数中缀转后缀比较符这张表适合考前十分钟看一遍全是常见的“会但错”的点。6.3 把栈/队列串起来的一道综合设计题思路第三章最后经常会有一道压轴综合题给定入栈序列1到n判断某个输出序列是否合法。这类题的正确解法是模拟而不是试图找数学规律。核心算法是用一个栈和一个指向输出序列当前位置的指针i。依次让1到n入栈每次入栈后检查栈顶是否等于输出序列的第i个元素如果等于就弹栈并让i后移循环检查直到栈顶不等于下一个输出元素。全部入栈且栈为空时序列合法。这个模拟过程的复杂度是O(n)因为每个元素最多入栈一次、出栈一次。很多同学觉得需要回溯其实不需要因为栈的“后进先出”特性决定了出栈顺序一旦满足前一个元素后面就顺序确定。做完这些题我发现第三章真正想训练的不是“背下栈和队列的实现代码”而是培养一种条件反射看到“逆序”想到栈看到“排队”想到队列看到“递归”就要联想到系统栈。备考时不要只对着答案抄每一道题都问自己一句“这个算法成立依赖栈/队列的哪个特性”想明白这一点后面第四章树、第五章图学起来会顺畅很多。我自己带过几轮考研复习凡是第三章用这个思路刷题的同学后面遇到复杂算法题的正确率明显更高。