企业官网建设流程全解析

考研数据结构手记(3)——栈和队列

深夜的自习室里，我刚把栈和队列的第三遍笔记整理完，桌上摊着历年真题里所有跟栈和队列沾边的题目。如果说前面几章线性表、链表是“数据结构的地基”，那栈和队列就是大家第一次真正感受到“数据结构思维”的地方，也是很多同学考研复习的第一道分水岭。这一章概念不难，代码量也不大，但考法极其灵活，选择题、算法题、应用题里都能看到它们的身影。今天这篇手记，把我这一轮复习踩过的坑、总结出来的规律，以及从真题里提炼出来的答题套路，一次性给你捋清楚。

1. 考研到底怎么考栈和队列

1.1 一张考点地图

栈和队列在408大纲里属于“线性表”的进阶内容，但考法颗粒度很细。我把历年真题里的考点整理成了一张清单，你可以先对照着看自己掌握到哪一步：

• 基本概念题：栈是后进先出（LIFO），队列是先进先出（FIFO），常以选择形式让你判断“哪个操作序列符合栈的性质”。
• 存储结构与实现细节：顺序栈的判空判满条件、top指针指向；链栈的插入删除方向；循环队列的队空队满判定、长度计算公式；链队的入队出队。这一块是选择题主力，也是后面算法题的基础。
• 综合应用题：括号匹配、表达式求值（中缀转后缀、后缀求值）、递归调用的栈模拟、用栈实现队列、用队列实现栈。这种题既可能出现在选择题里让你选“操作后的元素序列”，也可能直接作为代码题让你手写核心函数。
• 数学类考点：给定n个元素按序入栈，问可能的出栈序列数量，本质是卡特兰数；或者给一个出栈序列，判断它是否合法。这类题考的是对栈操作过程的推演能力。

从考频来看，循环队列的判空判满几乎年年碰，代码题里括号匹配和表达式求值是“压轴常客”。所以复习的时候，别把栈和队列当成两个孤立的东西，它们是一对对称结构：一个限制在表尾插入删除，一个限制在表头插入、表尾删除。你只要抓住“受限线性表”这个本质，后面很多题都能顺势推理出来。

1.2 为什么栈和队列要放在一起学

很多人直接把这一章拆成“栈”和“队列”两节分开背，但我觉得它们必须对照着学，才能真正理解透。

栈是一种后进先出的结构，所有的插入和删除都限定在栈顶（表尾）进行；队列是先进先出的结构，队头出、队尾进。从底层存储看，两者都可以用顺序存储或链式存储实现，但思维方式刚好相反：

• 顺序栈因为只在尾端操作，所以不需要移动大量元素，top指针做“追赶”动作；
• 顺序队列如果在队尾入队、队头出队，会面临“假溢出”问题，所以必须引入循环队列的概念，让front和rear在数组里转圈。

如果你分开看，顺序栈和顺序队列的代码差别其实很大；但把它们并排放在一起，你会发现本质是同一套顺序存储思想的不同演绎。备考时最有效的方法是“画图模拟”：把入栈出栈、入队出队每一步的数组状态画出来，比单纯背代码管用十倍。我后面会在第四章详细介绍怎么画图。

1.3 我的复习策略顺序

这一章我的复习次序经过了两次调整，最后定下来的是：

第一轮，先完整手写一遍基础代码：顺序栈、链栈、循环队列、链队列。不看书抄，而是理解后用白纸写，写完再对照课本纠错。

第二轮，刷选择题，重点是概念判断和简单推演。刷的过程中凡是遇到“top指针初始值”“判满条件”之类的题，先去翻代码，不要硬背结论。

第三轮，才开始啃“综合应用”，比如括号匹配、表达式求值、用两个栈实现队列。这部分需要把之前的基础代码熟练到“闭眼就能写出来”的程度，否则你在考场上现场推逻辑，时间根本不够。

第四轮，做真题，整理错题。这一章的错题很有价值，因为很多错误选项设计的非常巧妙，比如用它栈空队列空、栈满队列满的条件互相干扰，你在刷题时踩过的坑就是考场上最容易掉进去的坑。

2. 顺序栈的两个流派：top指针到底怎么选

2.1 初始值为-1和初始值为0的区别

顺序栈的代码，绝大多数教材上有两种写法：一种top初值设为-1，一种top初值设为0。很多同学第一遍学的时候没有固定一个版本，结果刷题时一会儿这个答案一会儿那个答案，越刷越乱。这里我帮你彻底理清楚：

top=-1 版本：top指向栈顶元素所在位置。栈空条件是 top == -1，栈满条件是 top == MaxSize - 1。入栈先执行 top++，再存数据；出栈先取数据，再执行 top--。对应代码：

#define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack &S) { S.top = -1; } bool StackEmpty(SqStack S) { return S.top == -1; } bool StackFull(SqStack S) { return S.top == MaxSize - 1; } bool Push(SqStack &S, int x) { if (StackFull(S)) return false; S.data[++S.top] = x; return true; } bool Pop(SqStack &S, int &x) { if (StackEmpty(S)) return false; x = S.data[S.top--]; return true; } bool GetTop(SqStack S, int &x) { if (StackEmpty(S)) return false; x = S.data[S.top]; return true; }

top=0 版本：top指向栈顶元素的下一个位置，也就是“下一个元素将要存放的位置”。栈空条件是 top == 0，栈满条件是 top == MaxSize。入栈先存数据再 top++，出栈先 top-- 再取数据：

void InitStack(SqStack &S) { S.top = 0; } bool StackEmpty(SqStack S) { return S.top == 0; } bool StackFull(SqStack S) { return S.top == MaxSize; } bool Push(SqStack &S, int x) { if (StackFull(S)) return false; S.data[S.top++] = x; return true; } bool Pop(SqStack &S, int &x) { if (StackEmpty(S)) return false; x = S.data[--S.top]; return true; }

这两个版本没有对错之分，但你必须“从一而终”。我个人习惯用 top=-1 版本，原因是它和“指针/下标指向当前元素”的直觉一致，判满、取栈顶元素更直白。但你只要选定一个，把所有真题按这个版本过一遍，就不会乱。

2.2 上溢、下溢与“假溢出”

顺序栈最容易出问题的两个场景是上溢和下溢。

上溢指栈满后继续入栈，数据会覆盖栈底之外的存储区，轻则越界，重则程序崩溃。所以写 Push 之前一定要做判满。有些题目会考“栈满后再入栈发生了什么”，答案就是“上溢”。

下溢指栈空后继续出栈，取出来的是一个无效值。考试里经常会设计一个场景：一个栈初始化后连续入栈a、b、c，然后出栈两次，再入栈d，问你最后栈里是什么。这种题看起来简单，但如果你把下溢情况判断错了，整个推演就废了。我建议所有涉及栈操作推演的题，第一步先写清楚“当前栈内元素+栈顶位置”，再一步一步走。

“假溢出”这个词专门针对队列：顺序队列的rear指向队尾，front指向队头，当rear走到数组末端时即使数组前面还有空位，也无法继续入队，因为没有“循环”的概念。解决办法就是循环队列，我们下一章展开。

2.3 共享栈：一道性价比极高的选择题考点

共享栈是两个栈共用同一块连续存储空间，一般教材里的标准模型是：两个栈的栈底分别在数组两端，栈顶向中间延伸。

• 栈1的top1初始化为 -1，从左往右生长；
• 栈2的top2初始化为 MaxSize，从右往左生长；
• 栈满条件是 top1 + 1 == top2，也就是两个栈的栈顶指针相邻，没有空位了。

共享栈存在的意义是动态地平衡两个栈的存储需求。比如栈1元素很多、栈2元素很少，如果给它们各分MaxSize/2的固定空间，栈1可能溢出而栈2大量空闲；共享栈模式下，栈1可以一直往中间扩张。选择题常问“共享栈相比普通顺序栈的最大优点”，答案就是提高存储空间利用率。

我自己动手写共享栈时踩过一个小坑：初始化时，我把第二个栈的栈顶也设成了MaxSize-1，结果入栈判断的时候搞混了方向。记住，共享栈的栈底是数组两端，栈顶向中间走，所以top2是递减的，入栈时用 S.data[S.top2--] = x，出栈时 x = S.data[++S.top2]。

3. 队列实现的核心：循环队列和它的三个公式

3.1 为什么顺序队列必须用循环结构

队列的顺序存储如果不做循环，会出现一个很尴尬的场景：front指向队头元素的下一个位置，rear指向队尾元素的下一个位置。当 rear == MaxSize时，队列“满”了，但实际数组前半部分可能已经空出一大片位置。这就是“假溢出”。解决办法是把数组逻辑上看成一个环，让rear到了尾部就绕回头部继续用。

但是问题来了：循环队列里，队空时 front == rear，队满时 front == rear 也会成立——同一个条件，两种含义，你会懵掉。所以标准的循环队列必须要“牺牲一个存储单元”来区分布尔状态：队满条件变成 (rear + 1) % MaxSize == front，也就是当rear的下一个位置就是front时，认为队列已满，实际上数组中还有一个空位没有使用。

你可能觉得浪费一个格子很心疼，但这是408里最标准的模型。还有一种“不浪费格子”的解法是加一个标志位或者计数器记录队列长度，但真题里绝大多数场景都是牺牲一个单元，先把标准模型吃透，其他变形自然能推出来。

3.2 循环队列的三个核心公式

循环队列的代码本身不难，难在三个公式背后的“模运算”思想。我直接给你结论，再解释为什么：

• 队空条件：front == rear
• 队满条件：(rear + 1) % MaxSize == front
• 队列长度：(rear - front + MaxSize) % MaxSize

为什么长度公式是 (rear - front + MaxSize) % MaxSize？因为循环队列里rear可能“绕过”数组末尾跑到front前面，如果直接 rear - front 会得到负数。加上 MaxSize 再取模，就等于“把负数纠正到正数范围内”。

举个具体例子：假设 MaxSize = 5，front = 3，rear = 1，直观上rear在front前面，队列应该不空。长度应该是 (1 - 3 + 5) % 5 = 3 % 5 = 3个元素。你可以在纸上画一个长度为5的圆环，从下标3往后数到下标1，确实是3个元素（下标3、4、0）。这个公式是选择题重灾区，建议你推导一次而不是死记。

3.3 循环队列代码实现

#define MaxSize 100 typedef struct { int data[MaxSize]; int front; // 指向队头元素 int rear; // 指向队尾元素的后一个位置 } SqQueue; void InitQueue(SqQueue &Q) { Q.front = Q.rear = 0; } bool QueueEmpty(SqQueue Q) { return Q.front == Q.rear; } bool QueueFull(SqQueue Q) { return (Q.rear + 1) % MaxSize == Q.front; } bool EnQueue(SqQueue &Q, int x) { if (QueueFull(Q)) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; return true; } bool DeQueue(SqQueue &Q, int &x) { if (QueueEmpty(Q)) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; return true; }

这段代码里你需要注意两个细节。入队时，先存数据，再让rear向后移动；出队时，先取数据，再让front向后移动。移动用的是取模运算，这是循环的关键。如果你漏了取模，rear就会“跑出”数组，变成假溢出。

3.4 链式队列和链栈：代码更简单的选择

链栈和链队列在考研代码题里相对温和，因为不需要考虑“满”的问题。链栈只需要一个指向栈顶的指针，入栈相当于头插法，出栈相当于删除第一个结点。链队列则需要队头和队尾两个指针，通常带头结点，入队在队尾指针后插入，出队删除头结点后的第一个结点。

值得注意的一个考点是：链队列出队时，如果要删除的结点恰好是队尾结点，删完后需要把rear指向front（体现在代码里就是Q->rear = Q->front）。因为头结点不算队元素，删除最后一个元素后，队列空了，队尾指针如果还指向那个已被释放的结点，后面入队就会出问题。很多同学写代码时忽略了这行，后来在模拟题里反复翻车。

链栈和链队的存储密度问题也是选择题常客：链式存储因为有指针域的额外开销，存储密度小于1；顺序存储的存储密度为1。这句话在你背“优缺点对比”的时候一定会遇到。

4. 从基础到应用：栈的三大经典实操场景

4.1 括号匹配：最像“真题”的栈应用

括号匹配是栈应用里最经典的入门题，因为它的逻辑非常直白：遇到左括号就入栈，遇到右括号就判断栈顶是否匹配。匹配则弹出，不匹配则报错；扫描完所有字符后，栈里还有残留的左括号也是不匹配。

我用C语言实现了一遍核心逻辑：

#include <stdbool.h> #include <string.h> bool isMatching(char str[]) { SqStack S; InitStack(S); int n = strlen(str); for (int i = 0; i < n; i++) { char c = str[i]; if (c == '(' || c == '[' || c == '{') { Push(S, c); } else if (c == ')' || c == ']' || c == '}') { if (StackEmpty(S)) { return false; // 右括号多于左括号 } char top; Pop(S, top); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return StackEmpty(S); // 全部匹配且栈空才算通过 }

这段代码里最容易漏的是最后那个 return StackEmpty(S)。如果输入是“( [ ]”，前面括号都能对上，但栈里还残留一个“(”，这时候应该判false。考试时如果你只做了“扫描过程中匹配”的判断，忘了检查栈是否为空，就会在这类“只多不少”的输入上出错。

4.2 表达式求值：中缀转后缀的算法核心

表达式求值是考研代码题里的“重量级选手”，虽然不一定让你完整写出整个求值器，但“中缀转后缀”的思想是必须滚瓜烂熟的。

中缀表达式转后缀表达式（逆波兰式）的经典算法，用栈来保存运算符：

1. 从左到右扫描表达式，遇到操作数直接输出；
2. 遇到运算符时，如果栈为空，直接入栈；否则比较它和栈顶运算符的优先级：
   • 当前运算符优先级高于栈顶，入栈；
   • 否则，弹出栈顶运算符输出，再继续比较，直到当前运算符可以入栈；
3. 遇到左括号直接入栈，遇到右括号则弹栈输出，直到弹出左括号为止；
4. 扫描完成后，把栈里剩余的运算符依次弹出输出。

这里最烦人的是优先级比较。比如“+”和“”比较，“”优先级高；两个“+”在一起，栈顶的“+”应弹出，因为运算是左结合的。如果你在模拟题里推错了，整个后缀表达式就会乱套。

我举一个例子，你可以在纸上手动模拟一遍：

输入：A + B * C - D / E

后缀结果应该是：A B C * + D E / -

模拟一下：A输出，+入栈，B输出，优先级高于+所以入栈，C输出，-优先级低于栈顶*，弹出*，再与+比较，低于+，弹出+，然后-入栈，D输出，/优先级高于-所以/入栈，E输出，扫描结束，弹出栈中所有运算符，得到-和/。完整后缀就是 A B C * + D E / -。这个例子你推过一遍，中缀转后缀就基本掌握了。

后缀表达式求值就更简单了：扫描后缀表达式，遇到数字入栈，遇到运算符就弹出两个操作数，先弹出的是右操作数，计算后将结果重新入栈。扫描完，栈顶就是最终结果。

4.3 递归与栈：为什么说“递归本质上是栈”

函数调用时，系统会用“函数调用栈”保存返回地址、局部变量和参数。递归之所以能自动“回退”，就是因为每层递归调用都把自己的状态压入系统栈，返回时再弹出。理解了这一点，很多“递归转非递归”的题目就有思路了：你只需要显式地用一个栈模拟系统栈的压栈和弹栈过程。

比如二叉树的前序遍历递归版本，用栈模拟时：先访问根结点，再把右孩子入栈，最后把左孩子入栈（因为栈是后进先出，先入栈的后访问）。这里如果你把入栈顺序搞反了，遍历结果就会变成“根右左”，那就成了另一种遍历方式了。

我在复习这块时自己写过一个“模拟函数调用栈”的小程序，用来观察递归调用过程。你会发现真正发生递归的时候，栈的深度就是递归调用的层数，这个层数在选择题里经常被问到，比如“求n的阶乘递归算法的时间复杂度和空间复杂度”，答案分别是O(n)和O(n)。

5. 常见问题速查与真题实战思路

5.1 top指针初始化弄混怎么办

这是我自己早期复习最头疼的问题。一道题说“栈的top指针指向栈顶元素的上一个位置，判断栈空的条件是什么”，我总想套top=-1版本的结论，结果答案是 top == 0。

解决办法是：拿到这种题，先确认题目给的是哪个版本。如果只说“top指向栈顶元素的下一个位置”，那就对应top=0版本；如果说“top指向栈顶元素本身”，那就是top=-1版本。再背一套对应的判空判满公式就够了。千万不能混着记，一混必错。

5.2 出栈序列合法性怎么推

给定入栈序列1,2,3,...,n，判断某个出栈序列是否合法，选择题高频。

最稳妥的方法是直接模拟：用一个栈，从左到右扫描出栈序列，如果栈顶不是当前要出栈的元素，就继续按入栈顺序往栈里压入；如果压完了还匹配不上，就说明这个出栈序列不合法。这个方法虽然看起来笨，但绝对准确，而且不费脑子。

如果问的是“n个元素入栈后，可能的不同出栈序列数量”，那就是卡特兰数公式：C(2n, n) / (n+1)。比如n=3时，合法出栈序列有5种；n=4时是14种。选择题里还有一种问法是“以下哪个序列不可能出现”，这时候用模拟法逐个排除最保险。

5.3 两个栈实现队列的代码模板

这是栈和队列结合的经典题目，也是很多同学第一反应“不可能”但其实很简单的题。

思路：设置两个栈，一个负责入队（s1），一个负责出队（s2）。

• 入队：直接把元素压入s1；
• 出队：如果s2不为空，直接从s2弹出；如果s2为空，先把s1中所有元素依次弹出并压入s2，再从s2弹出。

s2等价于一个“缓冲翻转区”，把s1里的顺序颠倒一次，就从后进先出变成了先进先出。

写代码时有一个关键判断：出队时先看s2为空，再把s1全部“倒”进来。如果s2非空时你误把s1里的元素又倒进来，顺序就乱了。这个细节我在一次模拟题里踩过，后来专门标红记在笔记上。

5.4 易错点速查表

我把这一章选择题里最容易出错的细节整理成了表格，建议你考前最后一天只看这张表：

这张表不是我抄来的，是我刷了三轮真题之后自己总结的。每一行都对应过至少一道真题或模拟题，你可以打印出来贴在手账本上，考前过一眼比翻整本书效率高很多。

栈和队列这一章，我个人最大的体会是：千万不要死记硬背。代码要亲手敲，出入栈、出入队的每一步要亲手在纸上画出来，公式要亲手推一遍。等你把“为什么牺牲一个空间单元”想明白了，“为什么长度公式要加MaxSize取模”想明白了，题干再怎么变，你都能一眼看穿。最后再分享一个小技巧：复习循环队列时，用一个真实数组比如长度为5，把front和rear放在不同的相对位置上，手动模拟入队、出队、达到满队的整个过程，这样一套下来，比在脑子里空想十遍都管用。