栈与队列习题全解析：从出栈序列到循环队列的避坑指南

学数据结构的时候，很多人对“栈和队列”这一章的态度是：概念太简单了，不就是后进先出和先进先出嘛，没什么可学的。结果一到做题就被各种出栈序列、循环队列判满判空、括号匹配、表达式转换轮番教做人。这一章的知识点确实不多，但习题的花样却特别多，原因在于它考的从来不是“背结论”，而是对存储结构、操作限制和边界条件的综合理解。

这篇博文就围绕数据结构第八章常见的栈与队列习题展开，按题型拆解题思路，讲清楚每一步背后的原理，再把容易出错的细节和实际做题时的经验一起整理出来。不管你是正在期末复习，还是准备考研、面试刷题，这章啃透了，后面的树和图会顺很多，因为递归转非递归、深度优先搜索、层次遍历这些高级内容全都要用到栈和队列的基本功。

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. 选择题高频易错点与避坑表

这一章的选择题比大题更容易阴沟翻船，因为好多结论看起来是常识，实际上有一个隐藏前提。我把常见易错点整理成一张表，考前直接过一遍：

补充一个容易混淆的判断题：栈和队列都是“后进先出”或“先进先出”吗？正确的是栈是后进先出，队列是先进先出，两者都是操作受限的线性表。但如果说“栈和队列都只能在端点进行插入删除”，这个是成立的说法；如果说“栈和队列的物理结构相同”，这就是错的，它们的逻辑特性不同，物理实现也可以不同。

另外，共享栈这个冷门知识点也偶尔出现。两个栈共享一个数组，分别从数组两端开始生长，判满条件是top1 + 1 == top2。这个方案的价值在于能够充分利用数组空间，当一个栈空闲、另一个栈紧张时，空间可以互相调剂。

7. 不同场景下的刷题与练习建议

同样是栈与队列，期末复习、考研复习、面试准备三类场景的侧重点完全不同。很多同学拿着同一套题从头刷到尾，效率其实不高。

7.1 期末复习：概念判断题是主线

期末考试的题型多为选择、填空和简单的算法设计。复习重点放在：

• 栈顶指针不同初始化方式对应的判空判满条件
• 循环队列三种判满方案的对比
• 给出入栈序列，判断出栈序列合法性
• 中缀转后缀的手工流程

复习方法是把课本例题的每一行都搞懂，再独立重算一遍，不要“觉得会了”。另外可以把“栈的容量如果为 2，入栈 1 2 3 4，出栈序列有多少种”这类考题做一遍，这类组合题一旦考到，区分度非常高。

7.2 考研综合：抓递归转非递归和综合应用

考研大题喜欢把栈和二叉树、递归结合，比如让你用栈实现二叉树的三种遍历，或者用一个栈和一个队列实现某种调度逻辑。复习时要熟练写出链栈、链队列的类定义和核心操作函数，同时在时间复杂度、空间复杂度上能做分析。

很多考研同学在这章就把“栈模拟递归”练熟了，后面学图的深度优先搜索时直接受益。我的建议是不要跳过这个看似不重要的知识点，它是整个数据结构串起来的桥梁之一。

7.3 面试刷题：重点练“用栈实现队列”和“用队列实现栈”

面试中的栈与队列题和校内考试风格差异很大，一般不是让你背书，而是让你设计。两个经典题必须闭着眼睛写出来。

用两个栈实现队列：一个栈负责入队，另一个栈负责出队。出队时如果出队栈为空，把入队栈的所有元素依次弹出并压入出队栈，这样元素顺序就被反向一次，再弹出就是先进先出。这个题考查“操作序列中元素的反转特性”，面试官往往还会追问每个操作的时间复杂度。

用两个队列实现栈：入栈时把新元素放入非空队列，再把原队列的所有元素依次出队并入队到另一个队列，保证最新元素始终处在队头。这样出队操作就等价于出栈。这个题比前一个稍微绕一点，建议两个队列的操作都手写一遍。

心得：我刷这些题时的体会是，栈与队列互相转换的题并不难，难的是把“底层的操作顺序”想清楚。面试时如果卡住了，直接在纸上画出两个容器，拿两个数字模拟一遍入队出队，思路马上就通了。

7.4 一个值得养成的习惯：亲手实现一遍底层代码

不管目标是什么，我都建议你至少独立实现顺序栈、链栈、循环队列、链式队列四个基础结构。不照着书抄，合上书写完，再写几个测试用例调用一遍。这个过程能暴露出大量你以为懂但其实不懂的细节：入队时是否忘了判满、出栈时是否忘了释放节点、循环队列的取模是否写对。

数据结构是一门“动手才能发现盲区”的学科。第八章的栈和队列看似基础，但它位于所有后续数据结构的起点。堆栈实现递归调用，队列支撑广度优先遍历，贯穿整个课程体系。

最后分享一个我在学习阶段常用的自查技巧：每学完一个结构，顺手写一页“三句话总结”，内容分别是数据结构定义、核心操作与边界条件、经典应用场景。对我来说，这一页纸比刷十道题还有效。栈和队列的题目千变万化，但本质概念就那么几条，想透了，到哪儿都不怕。