【王道考研·数据结构】第三章栈和队列（整合版）

Austoin2026-03-272026-03-27

引言

第三章讨论的是两种“操作受限的线性表”：栈和队列。
它们都属于线性结构，但和前一章的线性表不同，最大的特点是：

不是任意位置都能操作
插入和删除都被限制在特定端点进行
也正因为这种限制，它们在很多具体问题里反而比普通线性表更高效、更自然，例如：
栈：括号匹配、表达式求值、递归调用
队列：层次遍历、广度优先搜索、资源调度
本篇基于现有旧文章，把第三章的栈、队列及其应用合并成一篇完整复习文章。

图像化理解（Mermaid）

  mindmap
  root((第三章核心地图))
    受限线性表
      栈 Stack（LIFO）
        进栈/出栈都在栈顶
      队列 Queue（FIFO）
        入队在队尾
        出队在队头

一句话理解：栈处理“最近的事”，队列处理“最早的事”。

一、栈的基本概念

1. 什么是栈

栈（Stack）是一种操作受限的线性表，只允许在表的一端进行插入和删除操作。

栈顶（Top）：允许插入和删除的一端
栈底（Bottom）：固定不动的一端
空栈：不含任何元素的栈
最直观的类比就是：
叠盘子
羽毛球筒
最后放进去的，总是最先拿出来。

2. 栈的核心特性：LIFO

栈的本质特征是：

后进先出（Last In First Out, LIFO）

3. 栈的基本操作

不管是顺序栈还是链栈，核心操作都一样：

InitStack(&S)：初始化
DestroyStack(&S)：销毁
Push(&S, x)：进栈 / 压栈
Pop(&S, &x)：出栈 / 弹栈
GetTop(S, &x)：读栈顶元素但不删除
StackEmpty(S)：判空

4. 栈的补充考点：合法出栈序列数量

若有 n 个不同元素依次进栈，则合法出栈序列的个数是卡特兰数：

1	1 / (n + 1) * C(2n, n)

这个结论经常出现在选择题里。若 `n` 不大，也可以直接手动模拟。

二、顺序栈

顺序栈用一组地址连续的存储单元存放栈中元素，通常还配一个 top 指针表示栈顶位置。

1. 基础版：`top = -1`

这是教材中最常见的一种定义方式：

#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

含义是：

初始化时 top = -1
top 始终指向当前栈顶元素的真实位置

初始化与判空

void InitStack(SqStack &S) {
    S.top = -1;
}
bool StackEmpty(SqStack S) {
    return S.top == -1;
}

进栈

bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) return false;
    S.data[++S.top] = x;
    return true;
}

出栈与读栈顶

bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) return false;
    x = S.data[S.top--];
    return true;
}
bool GetTop(SqStack S, ElemType &x) {
    if (S.top == -1) return false;
    x = S.data[S.top];
    return true;
}

2. 另一种写法：`top = 0`

有些题目中会把 top 设计成“下一个可插入位置”：

初始化：top = 0
判空：top == 0
栈满：top == MaxSize
进栈：data[top++] = x
出栈：x = data[--top]
遇到题目时要先判断：
top 到底表示“当前栈顶元素的位置”，还是“下一个空位置”。

3. 共享栈

如果有两个栈，可以让它们共享同一个数组空间：

0 号栈从下往上增长
1 号栈从上往下增长
定义：

typedef struct {
    ElemType data[MaxSize];
    int top0;
    int top1;
} ShStack;

初始化：

1 2	top0 = -1; top1 = MaxSize;

关键考点：

共享栈满的条件是 top0 + 1 == top1
共享栈的意义在于：

避免一个栈满了，另一个栈却空着造成浪费

三、链栈

链栈本质上就是：

只允许在表头进行插入和删除的单链表
也就是说：

进栈 = 头插法
出栈 = 头删法

1. 定义

typedef struct Linknode {
    ElemType data;
    struct Linknode *next;
} *LiStack;

2. 初始化

链栈常用不带头结点写法：

1
2
3

void InitStack(LiStack &S) {
    S = NULL;
}

3. 进栈

bool Push(LiStack &S, ElemType x) {
    struct Linknode* p = (struct Linknode*)malloc(sizeof(struct Linknode));
    if (p == NULL) return false;
    p->data = x;
    p->next = S;
    S = p;
    return true;
}

4. 出栈

bool Pop(LiStack &S, ElemType &x) {
    if (S == NULL) return false;
    struct Linknode* p = S;
    x = p->data;
    S = S->next;
    free(p);
    return true;
}

5. 链栈与顺序栈的对比

顺序栈优点

存取实现简单
不需要额外指针域

顺序栈缺点

容量受限
扩容不方便

链栈优点

空间分配灵活
理论上不容易“满”

链栈缺点

每个结点要额外存指针
不如数组紧凑

四、队列的基本概念

1. 什么是队列

队列（Queue）也是一种操作受限的线性表，但它和栈不同：

插入只允许在一端进行
删除只允许在另一端进行
其中：
队头（Front）：允许删除的一端
队尾（Rear）：允许插入的一端

2. 队列的核心特性：FIFO

队列的核心特性是：

先进先出（First In First Out, FIFO）
这就像排队打饭：谁先排，谁先出去。

3. 基本操作

InitQueue(&Q)：初始化队列
EnQueue(&Q, x)：入队
DeQueue(&Q, &x)：出队
GetHead(Q, &x)：读队头元素
QueueEmpty(Q)：判空

五、循环队列

1. 什么是假溢出

如果用普通数组实现队列，随着不断入队和出队：

front 和 rear 会不断后移
即使数组前面已经空出来，也可能因为后面走到头而无法继续入队
这就是假溢出。
为解决这个问题，教材引入了：
循环队列
也就是逻辑上把数组首尾相接。

2. 定义

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

3. 核心难点：如何区分队空和队满

初始化时：

1	front = rear = 0

问题在于：

队空时可能 front == rear
队满时也可能绕一圈后 front == rear
所以必须额外设计判定方式。考研中常见三种方案。

方案一：牺牲一个存储单元

这是最常见、教材最常用的方案。

队空：front == rear
队满：(rear + 1) % MaxSize == front
队长：(rear + MaxSize - front) % MaxSize
代码：

bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

方案二：增加 `size` 变量

队空：size == 0
队满：size == MaxSize

方案三：增加 `tag` 变量

每次入队后 tag = 1
每次出队后 tag = 0
于是：
队空：front == rear && tag == 0
队满：front == rear && tag == 1

4. 循环队列的高频易错点

指针移动别忘了 % MaxSize
队空与队满条件一定要先看题目到底采用哪种方案
队长公式要注意正负关系，常写成：

1	(rear + MaxSize - front) % MaxSize

六、链队列

链队列本质上是一个同时保存：

队头指针 front
队尾指针 rear
的单链表。

1. 定义

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

2. 带头结点的链队列

教材更推荐带头结点写法，因为逻辑统一。

初始化

void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

判空

1
2
3

bool IsEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

入队

void EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

出队

bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    free(p);
    return true;
}

3. 链队列的特殊边界

当队列中只有一个元素时：

出队后队列会变空
此时必须让 rear 重新指向头结点
这是链队列大题里的经典陷阱。

七、双端队列

1. 什么是双端队列

双端队列是一种允许在两端都进行插入和删除的线性表。

2. 两种常考变体

（1）输入受限的双端队列

只能从一端插入
允许从两端删除

（2）输出受限的双端队列

允许从两端插入
只能从一端删除

3. 合法输出序列的判断

做双端队列题时，一个重要思路是：

栈本质上是一种特殊的双端队列。
因此：

若某输出序列是合法的栈输出序列
那它在双端队列里一定也合法
若不是，再根据“输入受限”或“输出受限”的规则具体模拟。

八、栈的经典应用

1. 括号匹配

括号匹配是栈最经典的应用之一。
核心思想：

扫描到左括号，入栈
扫描到右括号，就拿它去匹配一个最近的左括号
之所以能这样做，是因为：
最后出现的左括号，必须最先被匹配。
这刚好符合栈的 LIFO 特性。

匹配失败的三种情况

扫描结束后栈非空：有左括号未匹配
扫描到右括号时栈空：右括号无对应左括号
弹出的左括号类型不匹配：如 [ 对上 )

2. 表达式求值

表达式一般分为：

中缀表达式
前缀表达式
后缀表达式

（1）三种表达式关系

先序思想对应前缀
中序思想对应中缀
后序思想对应后缀

（2）后缀表达式求值

算法过程：

从左往右扫描
遇到操作数，压栈
遇到运算符，连续弹出两个操作数
进行运算，再把结果压回栈
特别注意：
对减法和除法，先弹出的那个是右操作数，后弹出的才是左操作数。

（3）中缀转后缀

需要借助运算符栈。
规则是：

操作数直接输出
( 直接入栈
) 触发弹栈直到遇到 (
运算符则比较优先级，把栈内优先级更高或相等的先弹出

（4）中缀表达式直接求值（双栈法）

同时使用：

操作数栈
运算符栈
本质上等于：
中缀转后缀 + 后缀求值 的融合版本。

3. 递归与函数调用栈

递归背后依赖的就是函数调用栈。
每次函数调用 / 递归调用，通常都要把这些信息压栈：

返回地址
实参
局部变量
因此：
递归优点：代码简洁
递归缺点：可能有重复计算，且递归层数过深会导致栈溢出
很多递归都可以通过自定义栈改写成非递归形式。

九、队列的经典应用

1. 树的层次遍历

层次遍历的本质就是：

先访问前一层
再访问后一层
这天然适合队列的 FIFO 特性。

2. 图的广度优先搜索 BFS

BFS 的基本过程是：

起始结点入队
队头出队并访问
将其所有未访问邻接点依次入队
重复直到队空

3. 操作系统中的应用

（1）CPU 调度

FCFS（先来先服务）就是典型队列思想。

（2）打印缓冲区

打印任务按到达顺序排队执行，也是队列。

十、图像化总览（Mermaid）

1. 栈操作图

  flowchart TB
    T[Top] --> A[7]
    A --> B[5]
    B --> C[2]
    C --> D[1]
    D --> E[Bottom]
    IN[进栈: 新元素压到 Top] --> T
    OUT[出栈: 只能弹 Top] --> T

2. 队列操作图

  flowchart LR
    F[Front] --> A[a] --> B[b] --> C[c] --> R[Rear]
    DEQ[出队: 从 Front 删除] --> F
    ENQ[入队: 在 Rear 后追加] --> R

3. 循环队列绕回图

  flowchart LR
    S0[0] --> S1[1] --> S2[2] --> S3[3] --> S4[4] --> S5[5] --> S6[6] --> S7[7] --> S0
    NOTE[rear = (rear + 1) % MaxSize]
    NOTE --> S7

4. 括号匹配流程图

  flowchart TD
    A[扫描字符流] --> B{字符类型}
    B -->|左括号| C[入栈]
    B -->|右括号| D{栈顶可匹配?}
    D -->|是| E[匹配并出栈]
    D -->|否| F[失败]
    C --> G[继续扫描]
    E --> G
    G --> H{扫描结束?}
    H -->|否| B
    H -->|是| I{栈是否为空}
    I -->|空| J[成功]
    I -->|非空| F

十一、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

LIFO vs FIFO
- 栈：后进先出（LIFO）
- 队列：先进先出（FIFO）
- 做题前先写这两个缩写，防止思维串台。
顺序栈两种 top 语义
- 语义1：top 指向“当前栈顶元素”（常见初值 -1）
- 语义2：top 指向“下一可放位置”（常见初值 0）
- 同一题里不能混用两套判空判满公式。
循环队列三种判满判空方案
- 牺牲一个单元
- 增加 size
- 增加 tag
- 条件完全不同，必须按题目指定方案计算。
链栈 vs 链队列的头结点习惯
- 链栈常不带头结点（头插头删简洁）
- 链队列常带头结点（统一空队/单元素出队边界）

B. 易错点（为什么错 + 怎么改）

循环队列忘记取模
- 错因：把循环队列当普通数组。
- 正解：front/rear 每次移动都要 % MaxSize。
循环队列长度公式写错
- 错因：直接写 rear-front 可能为负。
- 正解：(rear + MaxSize - front) % MaxSize。
链队列出队后漏改 rear
- 错因：只改了 front->next。
- 正解：若删的是最后一个结点，要令 rear = front。
后缀表达式求值弹栈顺序错
- 错因：把先弹出的当左操作数。
- 正解：先弹出的是右操作数，后弹出才是左操作数。
把“读栈顶”写成“出栈”
- 错因：GetTop 和 Pop 语义混淆。
- 正解：GetTop 只读不删，Pop 才删除。

C. 高频题型速解路线

括号匹配      -> 栈
表达式求值    -> 栈（操作数栈/运算符栈）
层次遍历/BFS  -> 队列
调度排队      -> 队列

十二、第三章高频题型与易错点

1. 合法出栈序列

判断核心：

在弹出某元素时，它之前入栈但尚未出栈的元素，必须按逆序排列。

2. 共享栈满的条件

必须记住：

1	top0 + 1 == top1

3. 循环队列长度公式

最常见写法：

1	(rear + MaxSize - front) % MaxSize

4. 链队列出队的特殊边界

当出队的是最后一个元素时，要记得：

1	rear = front

5. 表达式求值常见错误

最大坑点：

减法、除法的左右操作数顺序反了

6. 本章最容易混淆的地方

栈是 LIFO，队列是 FIFO
顺序栈里 top = -1 和 top = 0 两套逻辑不能混
循环队列判空 / 判满条件依赖于题目给的方案
链栈通常不带头结点，链队列通常带头结点更方便
双端队列不是“随便两端都能自由乱搞”，要看题目是输入受限还是输出受限

十三、书签级思维导图复现（第三章，Mermaid）

  mindmap
  root((第3章 栈、队列与受限线性表))
    3.1 栈
      栈定义（LIFO）
      顺序栈（top=-1 / top=0）
      共享栈（top0+1==top1）
      链栈（头插头删）
      应用
        括号匹配
        表达式求值
        递归
    3.2 队列
      队列定义（FIFO）
      顺序循环队列
        牺牲一个单元
        size 计数法
        tag 标记法
      链队列（常带头结点）
      双端队列（输入受限/输出受限）
    3.3 应用映射
      BFS/层序遍历 -> 队列
      逆波兰求值 -> 栈
      系统调度缓冲 -> 队列

十四、PDF 例题与知识点补充（栈与队列）

例题 1：栈合法出栈序列判定

题目：入栈序列为 1,2,3,4，序列 2,1,4,3 是否可能是合法出栈序列？

答案：可能。

详细解析：

入 1,2 后可依次出 2,1。
再入 3,4，可依次出 4,3。
全过程符合“后进先出”，故合法。

例题 2：顺序栈判空判满（top=-1 口径）

题目：top 指向当前栈顶元素且初值为 -1 时，判空判满条件是什么？

答案：

判空：top == -1
判满：top == MaxSize - 1

详细解析：

空栈时没有元素，栈顶下标定义为 -1。
满栈时最后一个合法下标是 MaxSize-1。

例题 3：顺序栈判空判满（top=0 口径）

题目：top 指向“下一可插入位置”且初值为 0 时，判空判满条件是什么？

答案：

判空：top == 0
判满：top == MaxSize

详细解析：

空栈时下一可插入位置就是 0。
满栈时下一可插入位置越过末尾，等于 MaxSize。

例题 4：共享栈判满

题目：双端共享栈的判满条件是什么？

答案：top0 + 1 == top1。

详细解析：

两个栈从数组两端向中间增长。
当两个栈顶“相邻且无空位”时即满。

例题 5：链栈出栈边界

题目：空栈执行 Pop 应如何处理？

答案：直接返回失败，不能访问栈顶数据域。

详细解析：

空栈无有效结点。
若继续访问 S->data 会触发非法访问。
正确做法是先判空再操作。

例题 6：循环队列（牺牲一个单元）判空/判满

题目：牺牲一个存储单元方案下，循环队列判空、判满和队长公式是什么？

答案：

判空：front == rear
判满：(rear + 1) % MaxSize == front
队长：(rear + MaxSize - front) % MaxSize

详细解析：

判空与判满需要不同状态，因此预留一个空位。
所有下标移动都必须取模实现“绕回”。

例题 7：循环队列长度计算

题目：MaxSize=8, front=6, rear=2，队长是多少？

答案：4。

详细解析：

代入公式：(rear + MaxSize - front) % MaxSize。
即 (2 + 8 - 6) % 8 = 4。

例题 8：链队列出队后重置 rear

题目：队中仅一个元素，出队后如何维护指针？

答案：rear = front。

详细解析：

删除唯一元素后队列应回到空队状态。
带头结点链队列空队特征是 front == rear。

例题 9：括号匹配失败类型

题目：括号匹配中有哪些典型失败情况？

答案：

遇右括号时栈空。
类型不匹配（如 [ 对 )）。
扫描结束后栈非空。

详细解析：

右括号必须与最近未匹配左括号配对。
任一条件不满足即非合法括号串。

例题 10：后缀表达式求值顺序

题目：后缀片段 a b - 的计算顺序是什么？

答案：先弹右操作数 b，再弹左操作数 a，计算 a-b。

详细解析：

栈顶先弹出的元素是右操作数。
第二个弹出的元素是左操作数。
减法/除法必须严格区分左右顺序。

例题 11：中缀转后缀核心规则

题目：中缀转后缀时的核心规则是什么？

答案：

操作数直接输出。
( 直接入栈。
) 触发弹栈直到 (。
运算符比较优先级后决定入栈或弹栈。

详细解析：

运算符栈用于暂存“尚未输出”的运算符。
括号用于局部优先级控制，不直接输出到后缀式。

例题 12：BFS 为什么必须用队列

题目：为什么广度优先搜索采用队列而不是栈？

答案：因为 BFS 需要按“先发现先扩展”的层次顺序处理顶点。

详细解析：

BFS 按层推进，本质是 FIFO。
队列可保证先入队的顶点先出队并扩展。

例题 13：双端队列合法性分析

题目：双端队列题目为何不能直接套“栈结论”？

答案：因为双端队列有输入受限/输出受限等约束，规则与普通栈不同。

详细解析：

双端队列允许两端操作，但通常会限制某一类操作位置。
需按题目给定约束模拟，不能直接套通用模板。

例题 14：递归与栈空间

题目：递归深度为 h 时，调用栈空间复杂度是多少？

答案：通常为 O(h)。

详细解析：

每层递归都对应一个栈帧。
最大同时存在的栈帧数约等于递归深度。

例题 15：本章复杂度速查

题目：栈/队列基本操作和常见应用复杂度分别是多少？

答案：

栈/队列基本操作：O(1)
循环队列入队出队：O(1)
括号匹配、表达式扫描：O(n)

详细解析：

基本操作只改少量指针/下标，故常数级。
扫描型问题需要遍历输入串一次，故线性级。

十五、第三章必背核对表

LIFO / FIFO 不能混。
顺序栈两套 top 语义不能混写。
循环队列三种判满判空方案要先看题设。
链队列单元素出队后要重置 rear。
后缀表达式减除法左右操作数顺序必须对。
层序遍历/BFS 一定是队列。
递归本质依赖调用栈。

总结

第三章的本质是：

栈解决“最近进入的先处理”的问题
队列解决“最早进入的先处理”的问题
真正要掌握的核心内容包括：

栈与队列的定义、基本操作
顺序栈、链栈、共享栈
循环队列的三种判满判空方式
链队列的边界处理
双端队列合法序列判断
栈在括号匹配、表达式求值、递归中的应用
队列在层次遍历、BFS 和系统调度中的应用
只要这些点真正吃透，第三章基本就稳了，而且会直接为后面树、图的遍历打下基础。

作者：[Austoin]
参考来源：基于现有旧文章整理

引言

图像化理解（Mermaid）

一句话理解：栈处理“最近的事”，队列处理“最早的事”。

一、栈的基本概念

1. 什么是栈

2. 栈的核心特性：LIFO

3. 栈的基本操作

4. 栈的补充考点：合法出栈序列数量

这个结论经常出现在选择题里。若 n 不大，也可以直接手动模拟。

二、顺序栈

1. 基础版：top = -1

初始化与判空

进栈

出栈与读栈顶

2. 另一种写法：top = 0

3. 共享栈

三、链栈

1. 定义

2. 初始化

3. 进栈

4. 出栈

5. 链栈与顺序栈的对比

顺序栈优点

顺序栈缺点

链栈优点

链栈缺点

四、队列的基本概念

1. 什么是队列

2. 队列的核心特性：FIFO

3. 基本操作

五、循环队列

1. 什么是假溢出

2. 定义

3. 核心难点：如何区分队空和队满

方案一：牺牲一个存储单元

方案二：增加 size 变量

方案三：增加 tag 变量

4. 循环队列的高频易错点

六、链队列

1. 定义

2. 带头结点的链队列

初始化

判空

入队

出队

3. 链队列的特殊边界

七、双端队列

1. 什么是双端队列

2. 两种常考变体

（1）输入受限的双端队列

（2）输出受限的双端队列

3. 合法输出序列的判断

八、栈的经典应用

1. 括号匹配

匹配失败的三种情况

2. 表达式求值

（1）三种表达式关系

（2）后缀表达式求值

（3）中缀转后缀

（4）中缀表达式直接求值（双栈法）

3. 递归与函数调用栈

九、队列的经典应用

1. 树的层次遍历

2. 图的广度优先搜索 BFS

3. 操作系统中的应用

（1）CPU 调度

（2）打印缓冲区

打印任务按到达顺序排队执行，也是队列。

十、图像化总览（Mermaid）

1. 栈操作图

2. 队列操作图

3. 循环队列绕回图

4. 括号匹配流程图

十一、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

B. 易错点（为什么错 + 怎么改）

C. 高频题型速解路线

十二、第三章高频题型与易错点

1. 合法出栈序列

2. 共享栈满的条件

这个结论经常出现在选择题里。若 `n` 不大，也可以直接手动模拟。

1. 基础版：`top = -1`

2. 另一种写法：`top = 0`

方案二：增加 `size` 变量

方案三：增加 `tag` 变量