学数据结构的时候很多人对“栈和队列”这一章的态度是概念太简单了不就是后进先出和先进先出嘛没什么可学的。结果一到做题就被各种出栈序列、循环队列判满判空、括号匹配、表达式转换轮番教做人。这一章的知识点确实不多但习题的花样却特别多原因在于它考的从来不是“背结论”而是对存储结构、操作限制和边界条件的综合理解。这篇博文就围绕数据结构第八章常见的栈与队列习题展开按题型拆解题思路讲清楚每一步背后的原理再把容易出错的细节和实际做题时的经验一起整理出来。不管你是正在期末复习还是准备考研、面试刷题这章啃透了后面的树和图会顺很多因为递归转非递归、深度优先搜索、层次遍历这些高级内容全都要用到栈和队列的基本功。1. 栈和队列到底在考什么先看清这一章的底层逻辑做题之前先把底层逻辑理顺。很多人栽跟头不是因为不会写代码而是没搞清楚“逻辑结构”和“物理结构”这两件事。栈和队列在逻辑上都是线性表只不过操作位置受限。栈只允许在一端栈顶插入和删除队列只允许在一端队尾插入、在另一端队头删除。重点在于“限制”二字——这种限制决定了它们的行为特征也成为几乎所有习题的命题源泉。物理结构上栈和队列都可以用顺序存储或链式存储实现。顺序存储是一个数组加下标指针链式存储是单链表加几个指针。这就构成了一个二维矩阵顺序栈、链栈、顺序队列又分普通队列和循环队列、链式队列。每一种组合的判空、判满、插入、删除条件都不同习题也围绕这些展开。1.1 栈的核心特性栈顶指针的两种初始化方式顺序栈最经典的考查点是栈顶指针的初始化到底是top -1还是top 0。这两个写法本身没有对错关键在于要能自己推导出配套的判空判满条件。以top -1初始化为例入栈操作是S.data[top] x; // 先移动指针再赋值出栈操作是x S.data[top--]; // 先取出元素再移动指针此时判空条件是top -1判满条件是top MAXSIZE - 1栈中元素个数是top 1。如果换成top 0初始化入栈变成S.data[top] x出栈变成x S.data[--top]。这时判空条件是top 0判满条件是top MAXSIZE元素个数就是top。两种写法在题目里都会出现千万别只记一个版本。遇到具体题目时先看清初始化方式再现场推导条件这样永远不会被绕晕。1.2 队列的两个指针front 和 rear 有着不同的“指向规则”队列比栈更容易乱因为有两个指针而且不同教材对 front 和 rear 的指向定义并不统一。最常见的定义是front 指向队头元素rear 指向队尾元素的下一个位置。在这种定义下入队操作是Q.data[Q.rear] x; Q.rear (Q.rear 1) % MAXSIZE;出队操作是x Q.data[Q.front]; Q.front (Q.front 1) % MAXSIZE;判空条件是front rear判满条件是(rear 1) % MAXSIZE front。但有些题目会采用另一种约定front 指向队头元素的前一个位置rear 指向队尾元素。此时入队要先把 rear 后移再赋值判满、判空条件也可能随之变化。所以做任何队列题目第一件事永远是确认两个指针的“语义”不要一上来就套公式。1.3 这一章的题型分布与命题规律根据我刷过的教材题、真题和面试题栈和队列这章的题型大概能分成六个方向出栈序列合法性判断与合法序列计数循环队列判空判满、元素个数计算栈的应用括号匹配、中缀转后缀、后缀表达式求值递归转非递归用栈模拟系统调用过程链式栈和链式队列的代码实现用栈实现队列、用队列实现栈等互相转换问题掌握了这六类题第八章基本就稳了。下面逐一拆解。2. 出栈序列合法性这一章的第一道“劝退题”题目长这样已知入栈序列为 1、2、3问下列哪个出栈序列是不可能出现的答案选项里会有 3、2、1也会有 3、1、2 这种迷惑项。很多初学者靠直觉猜结果对错全靠运气。正确的方法是掌握两种判断思路。2.1 暴力模拟法最笨但永远不会错用一个辅助栈按照入栈序列依次将元素入栈同时对比出栈序列。具体规则是每当栈顶元素等于当前出栈序列中待输出的元素时立即出栈然后继续比对入栈序列处理完但出栈序列还没处理完说明该序列非法。拿入栈序列 1、2、3、出栈序列 3、1、2 来演示。按照入栈顺序1 入栈栈顶是 1不等于出栈序列当前的 3继续2 入栈栈顶是 2不等于 3继续3 入栈栈顶是 3等于当前出栈元素 3弹出出栈指针后移到 1。此时栈顶是 2不等于出栈序列当前要的 1但入栈序列已经全部处理完了无法继续弹出 1所以序列 3、1、2 非法。提示模拟的过程中只要记住“入栈时能出就立刻出、不能出就继续压”这一条任何序列都能判出来。2.2 更快的判定进阶技巧考察较大元素的“压制”关系如果觉得每一步都模拟太慢可以记一个快速判定规律对出栈序列中的任意三个元素 a、b、c如果它们在原入栈序列中的相对顺序是 a 在前、c 在后且 a b c这里用元素大小代表入栈先后那么这三个元素不能以 c、a、b 的顺序出栈因为 c 出栈时b 和 a 都在栈中且 b 在 a 之上必然先出 b 而不是 a。这个规律本质上是模拟法的一种形式化表达。考试时如果只需要判断一两个序列用这个规律很快如果判断多个序列老老实实画个栈模拟反而更稳妥。2.3 合法序列的数量Catalan 数列问有多少种不同的合法出栈序列时答案是 Catalan 数。当入栈元素互不相同且栈容量不受限时n 个元素的合法出栈序列数量为C(n) (1 / (n 1)) * C(2n, n)n 3 时 C(3) 5恰好对应 1、2、3 的五个合法出栈序列123、132、213、231、321。n 4 时 C(4) 14枚举会累死Catalan 公式一步就能算出来。这里要特别强调一个坑Catalan 公式成立的前提是元素互不相同且栈容量无限。如果入栈序列里有重复元素或者题目限制了栈的容量这个公式就不能直接用必须回到模拟法。2.4 栈容量受限的变体这个坑每年都有人踩某题目说栈的容量最多为 3入栈序列是 1、2、3、4、5问下面哪个出栈序列不可能。此时即使某个序列用无穷大栈判定是合法的也可能因为容量受限而非法。比如序列 4、5、3、2、1按无穷大栈判定合法1 入、2 入、3 入、4 入、4 出、5 入、5 出、3 出、2 出、1 出。但容量为 3 时压到 4 入栈时栈内已经有 1、2、3 三个元素再加 4需要容量 4直接超限所以非法。容量受限题目不多但一旦碰到就是致命的。我的建议是看到“栈的容量为多少”这句话不要走捷径直接模拟并记录每一步栈内元素个数同时检查是否超限。3. 循环队列的判空判满三种方法在现场怎么选顺序队列最大的问题是“假溢出”即数组前面还有空位但 rear 已经指到末尾再入队就报满。循环队列用取模运算把数组首尾相接解决了空间浪费问题却带来了新的问题——如何区分队空和队满。因为循环队列的判空条件是 front rear如果存满时 rear 也回到 front 的位置空和满就分不清了。解决思路有三种。3.1 方法一牺牲一个存储单元这是使用最广的方法考试最常考。队列容量为 MAXSIZE 时只允许存 MAXSIZE - 1 个元素。约定队空front rear队满(rear 1) % MAXSIZE front元素个数(rear - front MAXSIZE) % MAXSIZE为什么这样能区分因为队满时 rear 紧挨在 front 前面两个指针不相遇。牺牲的那个格子就是为了让“队满”和“队空”在指针位置上不重叠。3.2 方法二增设一个标志位或计数器不浪费空间但要多维护一个变量。给队列加一个tag或count字段每次入队成功count出队成功count--。判空变成count 0判满变成count MAXSIZE。这样队满时 rear 回到 front 也没关系因为真正区分空满的是 count而不是指针位置。这个方案在考试题里也经常出现只是需要你在实现时多写几行赋值语句。优点是空间利用率 100%缺点是每次入队出队都要维护计数器编码时要小心漏写。3.3 方法三记录元素个数本质上是方法二的变体有些代码干脆直接用size变量记录长度入队size出队size--。判空size 0判满size MAXSIZE。这和计数器法没有本质区别都是“用额外的状态信息消解歧义”。三种方案没有绝对的好坏。考试选择题里如果题目问“某循环队列采用牺牲一个单元的方案已知 front 和 rear求元素个数”直接用公式(rear - front MAXSIZE) % MAXSIZE。如果题目问“如何区分队空队满”要能列出三种方案并说明各自的优缺点。3.4 指针指向不同时元素个数公式怎么变这一步是易错重灾区。如果题目规定 front 指向队头元素的前一个位置rear 指向队尾元素那么入队操作要先rear (rear 1) % MAXSIZE再赋值出队同理要先front (front 1) % MAXSIZE再取出元素。此时元素个数公式依然是(rear - front MAXSIZE) % MAXSIZE但判空条件会变化。比如使用牺牲一个单元方案时判空不再是front rear而要看两者的位置关系具体定义。遇到这种变体最稳妥的办法是画一个队长为 6 的循环队列把 front 和 rear 的实际值标出来模拟入队两次、出队一次再回看公式是否成立。图一画指针语义全清楚公式也不会记错。4. 栈的应用习题括号匹配、中缀转后缀、后缀求值栈的应用题是第八章的“大分值”部分期末考试的算法设计题和考研综合题都爱从这里出。4.1 括号匹配边界条件是考察重点题目给定一个只包含( ) [ ] { }的字符串判断括号是否匹配。经典解法是用栈遍历字符串遇到左括号入栈遇到右括号时若栈空则非法否则弹出栈顶并比对是否匹配。容易漏掉的细节有三个。第一遍历结束时栈不为空说明有多余的左括号非法。第二遇到右括号时栈为空说明右括号多了非法。第三栈顶弹出后必须能对应上同一个类型的左括号(]这种交叉匹配要判非法。一段常见的实现思路参考bool isMatching(char *s) { Stack stack; initStack(stack); for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { push(stack, s[i]); } else { if (isEmpty(stack)) return false; char top pop(stack); if (!isPair(top, s[i])) return false; } } return isEmpty(stack); }这套逻辑不只在字符串处理里用编译器语法检查、编辑器自动补全底层也都是这个思路。做题时最好把三种匹配组合写成一个isPair函数代码更清晰。4.2 中缀表达式转后缀表达式手工模拟的完整过程中缀转后缀逆波兰式是栈应用里最经典的题目。手工做题时可以用一个运算符栈和一个输出列表。规则如下遇到操作数直接输出到结果列表。遇到运算符如果栈为空或栈顶是左括号直接入栈如果栈顶运算符优先级低于当前运算符入栈否则不断弹出栈顶入结果列表直到栈顶优先级低于当前运算符再入栈同优先级时也要弹因为运算从左到右栈顶优先级不低于当前运算符就要弹出。遇到左括号直接入栈遇到右括号连续弹出并输出到结果列表直到弹出左括号为止左括号不输出。表达式扫描完把栈中剩余运算符全部弹出。拿一个完整的例子走一遍A B * (C - D) - E / F。A 输出当前结果为A入栈B 输出结果为A B*入栈因为*优先级高于栈顶(入栈C 输出结果为A B C-入栈因为栈顶是左括号D 输出结果为A B C D遇到)弹出-输出弹出(丢弃。结果为A B C D -。此时运算符栈从底到顶是 *遇到-当前栈顶是*优先级不低于当前-弹出*新栈顶优先级也不低同优先级左结合也弹出。结果变成A B C D - * 。此时栈空当前-入栈E 输出结果为A B C D - * E/入栈因为/优先级高于栈顶-F 输出结果为A B C D - * E F扫描结束弹出栈中剩余/和-最终后缀表达式为A B C D - * E F / -这个例子我在教同学时发现大多数人卡在“遇到新-时为什么要一路弹到栈空”。原因在于中缀表达式的-前面是B * (C - D)这一整块转后缀后这一整块必须先完整输出来再轮到后面的- E / F所以它必须放在栈顶的运算符之后弹出。4.3 后缀表达式求值注意操作数顺序后缀表达式的计算相对简单遇到操作数入栈遇到运算符从栈里弹出两个操作数做运算。但如果盯着实现细节看有一个点很容易错。减法运算和除法运算有严格的顺序先弹出的是右操作数后弹出的是左操作数。比如后缀表达式3 5 -正确结果是3 - 5 -2。如果搞反顺序算成5 - 3 2答案就完全错了。这也是为什么很多手算题目只差一个符号就翻车。注意写代码时凡是遇到-和/都要用一个临时变量保存先弹出的数再与后弹出的数运算不要把顺序写反。4.4 递归转非递归栈的本质是“系统调用栈的模拟”这一部分在教材第八章常作为进阶应用出现。递归函数每一次调用都涉及参数、返回地址和局部变量的保存系统在底层用“调用栈”维护这个过程。手动用栈模拟递归其实就是把这个调用栈显式地写出来。一个典型题目用非递归方式实现二叉树的中序遍历。思路是从根节点开始一路向左入栈当无法再向左时弹出栈顶并访问然后转向右子树重复上述过程void inorderTraversal(TreeNode *root) { Stack stack; TreeNode *cur root; while (cur ! NULL || !isEmpty(stack)) { while (cur ! NULL) { push(stack, cur); cur cur-left; } cur pop(stack); visit(cur); cur cur-right; } }这段代码在中序、前序、后序遍历中反复出现。理解了为什么cur要一路压到底再弹出就等于理解了系统函数调用的机制后面学图算法时也会很顺手。5. 链式栈和链式队列机试题里的“送命”细节笔试选择喜欢考顺序实现的判断条件机试或者手写算法题则更偏向链式实现。链式结构不涉及取模运算但指针的边界条件一样能让人崩溃。5.1 链栈的实现头插法就是天然的栈链栈本质上是“只能在头结点后操作的单链表”。入栈就是在头结点后插入新元素出栈就是删除头结点后的第一个节点。不用设置尾指针也不需要循环遍历。带头结点的链栈判空条件是head-next NULL。入栈void push(LinkStack *head, ElemType x) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data x; newNode-next head-next; head-next newNode; }出栈bool pop(LinkStack *head, ElemType *x) { if (head-next NULL) return false; Node *del head-next; *x del-data; head-next del-next; free(del); return true; }注意出栈时释放节点这个动作。机试判题时如果频繁malloc却不free内存会一路涨上去严重的直接超限。5.2 链式队列front 和 rear 两个指针的配合链式队列需要队头指针 front 和队尾指针 rear。头结点在这里很重要front 指向头结点rear 指向队尾节点。这样判空条件是front rear此时两个指针都指向头结点看起来非常干净。入队不判满直接创建新节点接到队尾void enQueue(LinkQueue *q, ElemType x) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data x; newNode-next NULL; q-rear-next newNode; q-rear newNode; }出队要判断空。删除头结点后的节点同时更新队头指针bool deQueue(LinkQueue *q, ElemType *x) { if (q-front q-rear) return false; Node *del q-front-next; *x del-data; q-front-next del-next; if (q-rear del) { q-rear q-front; } free(del); return true; }5.3 链式队列最容易踩的坑删最后一个节点时忘了修 rear上面代码中的if (q-rear del)这一句是很多人漏写的。当队列里只剩一个元素时出队把这个节点删除后rear 还指向已经被释放的节点如果后续再一次入队就会对野指针操作直接导致程序崩溃。我见过不少同学笔试写得头头是道机试一到这个边界就报段错误。代码逻辑上删除队内唯一节点后rear 必须回退到头结点。这个细节建议直接在纸上画一遍链式队列的三种状态变化空队列、有一个节点、有多个节点。画完就再也不容易忘。6. 选择题高频易错点与避坑表这一章的选择题比大题更容易阴沟翻船因为好多结论看起来是常识实际上有一个隐藏前提。我把常见易错点整理成一张表考前直接过一遍易错点正确结论常见错误栈和队列属于什么结构都是操作受限的线性表误以为是线性结构之外的独立结构栈是否只能用顺序存储顺序、链式皆可误以为链栈不算栈循环队列队满条件(rear 1) % MAXSIZE front写成rear front无法区分空满元素个数公式(rear - front MAXSIZE) % MAXSIZE漏加MAXSIZE导致负数后缀表达式运算顺序先弹出的是右操作数减法除法算反链队列删最后一个节点rear要回到front忘记更新 rear野指针递归转非递归用栈保存现场误用队列模拟补充一个容易混淆的判断题栈和队列都是“后进先出”或“先进先出”吗正确的是栈是后进先出队列是先进先出两者都是操作受限的线性表。但如果说“栈和队列都只能在端点进行插入删除”这个是成立的说法如果说“栈和队列的物理结构相同”这就是错的它们的逻辑特性不同物理实现也可以不同。另外共享栈这个冷门知识点也偶尔出现。两个栈共享一个数组分别从数组两端开始生长判满条件是top1 1 top2。这个方案的价值在于能够充分利用数组空间当一个栈空闲、另一个栈紧张时空间可以互相调剂。7. 不同场景下的刷题与练习建议同样是栈与队列期末复习、考研复习、面试准备三类场景的侧重点完全不同。很多同学拿着同一套题从头刷到尾效率其实不高。7.1 期末复习概念判断题是主线期末考试的题型多为选择、填空和简单的算法设计。复习重点放在栈顶指针不同初始化方式对应的判空判满条件循环队列三种判满方案的对比给出入栈序列判断出栈序列合法性中缀转后缀的手工流程复习方法是把课本例题的每一行都搞懂再独立重算一遍不要“觉得会了”。另外可以把“栈的容量如果为 2入栈 1 2 3 4出栈序列有多少种”这类考题做一遍这类组合题一旦考到区分度非常高。7.2 考研综合抓递归转非递归和综合应用考研大题喜欢把栈和二叉树、递归结合比如让你用栈实现二叉树的三种遍历或者用一个栈和一个队列实现某种调度逻辑。复习时要熟练写出链栈、链队列的类定义和核心操作函数同时在时间复杂度、空间复杂度上能做分析。很多考研同学在这章就把“栈模拟递归”练熟了后面学图的深度优先搜索时直接受益。我的建议是不要跳过这个看似不重要的知识点它是整个数据结构串起来的桥梁之一。7.3 面试刷题重点练“用栈实现队列”和“用队列实现栈”面试中的栈与队列题和校内考试风格差异很大一般不是让你背书而是让你设计。两个经典题必须闭着眼睛写出来。用两个栈实现队列一个栈负责入队另一个栈负责出队。出队时如果出队栈为空把入队栈的所有元素依次弹出并压入出队栈这样元素顺序就被反向一次再弹出就是先进先出。这个题考查“操作序列中元素的反转特性”面试官往往还会追问每个操作的时间复杂度。用两个队列实现栈入栈时把新元素放入非空队列再把原队列的所有元素依次出队并入队到另一个队列保证最新元素始终处在队头。这样出队操作就等价于出栈。这个题比前一个稍微绕一点建议两个队列的操作都手写一遍。心得我刷这些题时的体会是栈与队列互相转换的题并不难难的是把“底层的操作顺序”想清楚。面试时如果卡住了直接在纸上画出两个容器拿两个数字模拟一遍入队出队思路马上就通了。7.4 一个值得养成的习惯亲手实现一遍底层代码不管目标是什么我都建议你至少独立实现顺序栈、链栈、循环队列、链式队列四个基础结构。不照着书抄合上书写完再写几个测试用例调用一遍。这个过程能暴露出大量你以为懂但其实不懂的细节入队时是否忘了判满、出栈时是否忘了释放节点、循环队列的取模是否写对。数据结构是一门“动手才能发现盲区”的学科。第八章的栈和队列看似基础但它位于所有后续数据结构的起点。堆栈实现递归调用队列支撑广度优先遍历贯穿整个课程体系。最后分享一个我在学习阶段常用的自查技巧每学完一个结构顺手写一页“三句话总结”内容分别是数据结构定义、核心操作与边界条件、经典应用场景。对我来说这一页纸比刷十道题还有效。栈和队列的题目千变万化但本质概念就那么几条想透了到哪儿都不怕。