栈和队列

🎯 一句话秒杀：栈是"先进后出"（后放的先拿），队列是"先进先出"（先排的先走）。都是操作受限的线性表。

---

① 📊【历年真题考情】

本章（栈和队列）在广东专升本计算机统考中的位置：

项目	结论
出题频次	⭐⭐⭐⭐⭐（五星必考）——2021-2026 年年必考，2026 新增循环队列判满考点
常考题型	单选、判断、填空（2026 循环队列判满）、简答（栈和队列区别）
预估分值	5~15 分 / 200 分（约 3%~8%）
考纲归属	2026 考纲「数据结构」考点13（栈、队列、循环队列）

考场真实出现过的高频题：

• 2023：栈的特点是 LIFO，队列的特点是 FIFO
• 2024：栈和队列都是操作受限的线性表
• 2021/2022：给定入栈顺序，判断合法出栈序列
• 2026：循环队列判满 → (rear+1) % m == front

🎯 学习目标：学完本章，你能 ① 判断任意出栈序列是否合法；② 说出循环队列判满/判空条件；③ 区分栈和队列的应用场景——这四类题就是本章真题的全部考法。

---

② 🗣️【零基础大白话引入】

栈是什么？ 像叠盘子——你洗好一个盘子放在最上面（入栈），要用的时候也是从最上面拿（出栈）。后洗的先拿，这就是"后进先出 LIFO"。

队列是什么？ 像排队买票——先排的人先买到票离开（出队），后来的人排在队尾（入队）。先排的先走，这就是"先进先出 FIFO"。

循环队列是什么？ 像环形餐厅的旋转餐台——餐台是环形的，菜转一圈又回来。队列的"队尾"走到头了，如果前面有空位就绕回开头继续用——循环利用空间。

为什么都是"操作受限"？ 栈只能在栈顶操作（不能从中间拿），队列只能在队头出队、队尾入队（不能插队）——限制操作规则，就是为了防止"乱拿乱放"。

💡 本章主线：栈（叠盘子）→ 队列（排队）→ 循环队列（环形餐台）→ 对比（什么时候用哪个）。核心是"进出规则"和"循环队列判满"。

---

③ 📖【正式核心知识点讲解】

3.1 栈（Stack）— 后进先出 LIFO

栈的定义

栈顶 ← ← 出栈/入栈都在这里
  ┌─────┐
  │ an  │ ← 栈顶
  │ ... │
  │ a2  │
  │ a1  │ ← 栈底
  └─────┘

核心原则： 只能在栈顶操作——进栈（push）和出栈（pop）

顺序栈（数组实现）

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 存放元素
    int top;             // 栈顶指针
} SqStack;

// 初始化
void InitStack(SqStack *S) {
    S->top = -1;  // 空栈时top=-1
}

// 判空
int IsEmpty(SqStack S) {
    return S.top == -1;
}

// 入栈
int Push(SqStack *S, int x) {
    if (S->top == MAXSIZE-1) return 0;  // 栈满
    S->data[++S->top] = x;  // top先+1，再赋值
    return 1;
}

// 出栈
int Pop(SqStack *S, int *x) {
    if (IsEmpty(*S)) return 0;  // 栈空
    *x = S->data[S->top--];     // 取值，top再-1
    return 1;
}

// 读栈顶
int GetTop(SqStack S, int *x) {
    if (IsEmpty(S)) return 0;
    *x = S.data[S.top];
    return 1;
}

链栈（链表实现）

// 用单链表实现——入栈就是头插，出栈就是删第一个结点
typedef struct Node {
    int data;
    struct Node *next;
} *LinkStack;

3.1.1 出栈序列判断（2021/2022 必考）

给定入栈顺序（如 1,2,3,4,5），判断出栈序列是否合法：模拟入栈出栈过程，逐个验证。

例题：入栈顺序为 1,2,3,4,5，出栈序列 3,2,1,5,4 是否合法？

步骤	操作	栈内（底→顶）	出栈序列
1	入栈 1	[1]	—
2	入栈 2	[1,2]	—
3	入栈 3	[1,2,3]	—
4	出栈 → 3	[1,2]	3
5	出栈 → 2	[1]	3,2
6	出栈 → 1	[]	3,2,1
7	入栈 4	[4]	3,2,1
8	入栈 5	[4,5]	3,2,1
9	出栈 → 5	[4]	3,2,1,5
10	出栈 → 4	[]	3,2,1,5,4 ✅

✅ 出栈序列 3,2,1,5,4 合法。记忆：模拟入栈出栈，能走通就合法。

栈的应用

• 括号匹配：左括号入栈，右括号与栈顶匹配
• 函数调用/递归：每次调用压栈，返回时出栈
• 表达式求值：中缀转后缀

3.2 队列（Queue）— 先进先出 FIFO

队列的定义

出队 ← [a1, a2, a3, ..., an] ← 入队
      队头              队尾

核心原则： 队头出队（dequeue），队尾入队（enqueue）

顺序队列（数组实现）

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front, rear;  // 队头指针、队尾指针
} SqQueue;

// 初始化
void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;  // 空队时front=rear=0
}

// 判空
int IsEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

// 入队
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;  // rear 后移
    return 1;
}

// 出队
int DeQueue(SqQueue *Q, int *x) {
    if (IsEmpty(*Q)) return 0;  // 队空
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;  // front 后移
    return 1;
}

3.3 循环队列（2026 新增考点）

循环队列 = 把数组"首尾相连"成环，解决"假溢出"问题

循环队列示意图（m=8）：
   [7] ← [0] ← front
   ↓         ↑
   [6]       [1]
   ↓         ↑
   [5] ← [4] ← [3] ← [2] ← rear

3.3.1 循环队列判空/判满（2026 必考）

状态	条件	说明
队空	front == rear	初始状态或出队到空
队满	(rear + 1) % m == front	牺牲一个单元区分空/满
队长	(rear - front + m) % m	当前元素个数

✅ 2026 真题：循环队列队满条件 → (rear + 1) % m == front 💡 为什么队满时不直接 rear == front？因为 队空也是 front == rear——必须牺牲一个单元来区分：队满时 rear 在 front 前一个位置。

3.4 栈 vs 队列 对比表

对比项	栈	队列
原则	后进先出 LIFO	先进先出 FIFO
操作位置	栈顶（一端）	队头出、队尾入（两端）
实现	顺序栈/链栈	顺序队列/链队列/循环队列
应用	括号匹配、递归、表达式求值	BFS、缓冲区、任务调度
共同点	都是操作受限的线性表（2024 判断）

✅ 2024 真题：栈和队列的共同点是 → 都是操作受限的线性表

---

④ 🧪【真题同源例题】

例题 1：判断出栈序列合法性

入栈顺序为 1,2,3,4，出栈序列 4,3,2,1 是否合法？

逐项推演：

1. 入栈 1,2,3,4 → 栈内 [1,2,3,4]
2. 出栈 4 → 栈内 [1,2,3]
3. 出栈 3 → 栈内 [1,2]
4. 出栈 2 → 栈内 [1]
5. 出栈 1 → 栈内 []
6. 合法 ✅

入栈全部入完再出栈＝倒序输出，显然合法。

例题 2：循环队列判满

设循环队列长度为 m=8，front=2，rear=1，判断队满还是队空？

逐项推演：

1. 判空：front == rear？2 ≠ 1 → 不空
2. 判满：(rear+1) % m == front？(1+1)%8 = 2 == front=2 → 队满 ✅
3. 队长：(1-2+8)%8 = 7 → 7 个元素

答案：队满（牺牲一个空位，实际存 7 个元素）。

---

⑤ ⚠️【历年真题高频扣分坑】

#	陷阱	错误做法	正确做法	出处
1	循环队列判满	用 front==rear 判满	判满 = (rear+1)%m==front	2026
2	队列操作端	以为队尾出队	队头出队、队尾入队	经典
3	栈操作端	以为栈底出栈	只能栈顶操作	2023
4	出栈序列	强行套公式	逐个元素模拟入栈出栈	2021
5	栈和队列混淆	栈 FIFO 队列 LIFO	栈 LIFO，队列 FIFO	2023
6	循环队列牺牲单元	以为 m 个全能用	判满牺牲一个单元，最多存 m-1	2026
7	front/rear 初始值	以为从 0 开始	初始 front=rear=0 表空	经典
8	共享栈	不了解两端向中间	了解即可	经典

---

⑥ 📝【课后自测练习题】

1. 入栈顺序 1,2,3，以下哪个出栈序列不可能？（2021 真题风格）

A. 1,2,3　　B. 3,2,1　　C. 2,1,3　　D. 3,1,2

---

2. 循环队列长度为 m，队满条件为（　　）（2026 真题风格）

A. front == rear　　B. (rear+1) % m == front　　C. rear+1 == front　　D. front+1 == rear

---

3. 栈的特点是（　　），队列的特点是（　　）（2023 真题风格）

A. FIFO, LIFO　　B. LIFO, FIFO　　C. 先进先出, 后进先出　　D. 随机存取, 顺序存取

---

4. 判断：栈和队列的共同点是都是操作受限的线性表。（2024 真题风格）

A. 正确　　B. 错误

---

👆 点击展开答案

第1题：D. 3,1,2

• 要出 3，必须先入 1,2,3 → 栈内 [1,2,3] → 出 3 → 栈内 [1,2] → 接下来只能出 2 不能出 1 → 3,1,2 不可能

第2题：B. (rear+1) % m == front

• 循环队列判满，牺牲一个单元（2026 新增考点）

第3题：B. LIFO, FIFO

• 栈=后进先出 LIFO；队列=先进先出 FIFO

第4题：A. 正确

• 栈和队列都是操作受限的线性表（2024 判断原题）

---

📝 原有闭卷挑战（保留 + 扩充）

（点击下方空白查看答案）

1. 栈和队列的共同点？

2. 栈的入栈顺序 1,2,3，出栈顺序 3,2,1 是否合法？

3. 循环队列队空条件？

4. 循环队列队满条件？

5. 队列的应用场景？

👆 点击展开答案

1. 都是操作受限的线性表
2. 合法（全部入栈再全部出栈）
3. front == rear
4. (rear+1) % m == front
5. BFS、缓冲区、任务调度

---

📖 教材习题对照

教材习题	知识点	难度
习题3.1~3.2	栈的定义与操作	⭐⭐
习题3.3~3.4	队列的定义与操作	⭐⭐
习题3.5	循环队列	⭐⭐⭐

对应教材：严蔚敏《数据结构》C语言版 第2版 → 第3章 栈和队列 对应考试大纲：考点13 — 栈和队列

📺 配套视频

复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。

• 严蔚敏 华科大 P7~P10 第三章 栈和队列 · 栈/队列/循环队列