企业官网建设流程全解析

很多人学《数据结构（C语言版 第2版）》时，前两章线性表还能靠背代码糊弄过去，到了第三章栈和队列，突然发现课后习题完全不知道从哪下手。严蔚敏这本教材的第三章表面上是讲两种基本数据结构，实际考的却是“你能不能根据受限操作倒推出应用场景”，这正好是期末和考研最喜欢出题的地方。这篇文章我就把第三章最常见的几类课后题全部拆开，从思路到可运行的C语言代码，再到那些老师不写在板书上的易错点，一次讲清楚。适合正在复习考研数据结构、期末冲刺或者自学卡在第三章的同学直接对照着练。

1. 第三章课后题到底在考什么——先看清题目背后的出题逻辑

很多同学拿到课后习题第一反应是“这题我代码能跑，但题不会做”，问题就出在没弄明白这一章的本质。

1.1 章节定位：为什么栈和队列这么基础却总让人栽跟头

栈和队列其实是“操作受限的线性表”。线性表可以在任意位置插入删除，栈只能在栈顶操作，队列只能一端入、另一端出。这个“受限”不是缺点，反而让它们有了明确的语义：栈天然解决“后进先出”的问题，队列天然解决“先进先出”的问题。

课后习题考察的核心就一句话：给你一个实际场景，你能否识别出它需要的是哪种受限操作，并利用该结构的特性完成算法。所以书中算法题不会直接让你背诵 Define 栈的六个基本操作，而是会问“利用栈实现十进制转二进制”“判断回文串”“表达式求值”这类应用题。

1.2 高频题型总览：这些题实际上是一类题

我把第三章高频课后题整理成一个题型表，刷题前先对号入座：

你会发现这些题都在反复使用同一个思维流程：判断场景是否符合某种受限操作特性，再决定选哪种存储结构，最后写操作代码。下面按这个流程逐类拆解。

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[] = "(a+b)*c-d"; char postfix[100]; InfixToPostfix(infix, postfix); printf("%s\n", postfix); // ab+c*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 / b，b为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 条件判满/计数判满/标志位判满三种方案怎么选

除了浪费一个存储单元的方案，教材和习题里还可能出现另外两种判满方案：

课后题如果明确说“不允许浪费存储空间”，你就得用后两种。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，借助B：

void 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

我把这一章最容易翻车的边界条件汇总成一张自查表，写代码前逐条过一遍：

这张表适合考前十分钟看一遍，全是常见的“会但错”的点。

6.3 把栈/队列串起来的一道综合设计题思路

第三章最后经常会有一道压轴综合题：给定入栈序列1到n，判断某个输出序列是否合法。这类题的正确解法是模拟，而不是试图找数学规律。

核心算法是：用一个栈和一个指向输出序列当前位置的指针i。依次让1到n入栈，每次入栈后检查栈顶是否等于输出序列的第i个元素，如果等于就弹栈并让i后移，循环检查直到栈顶不等于下一个输出元素。全部入栈且栈为空时，序列合法。

这个模拟过程的复杂度是O(n)，因为每个元素最多入栈一次、出栈一次。很多同学觉得需要回溯，其实不需要，因为栈的“后进先出”特性决定了出栈顺序一旦满足前一个元素，后面就顺序确定。

做完这些题我发现，第三章真正想训练的不是“背下栈和队列的实现代码”，而是培养一种条件反射：看到“逆序”想到栈，看到“排队”想到队列，看到“递归”就要联想到系统栈。备考时不要只对着答案抄，每一道题都问自己一句“这个算法成立依赖栈/队列的哪个特性”，想明白这一点，后面第四章树、第五章图学起来会顺畅很多。我自己带过几轮考研复习，凡是第三章用这个思路刷题的同学，后面遇到复杂算法题的正确率明显更高。