第7章栈与队列

🎯 本章学习目标

通过本章的学习，你将能够：

掌握栈的概念：理解栈的"先进后出"特性，掌握push/pop/top操作
掌握队列的概念：理解队列的"先进先出"特性，掌握push/pop/front操作
熟练循环队列：掌握循环队列的实现原理，能计算front/rear指针
掌握优先队列：理解priority_queue的用法，知道大小根堆的区别
区分栈和队列：清楚两者的区别和各自的适用场景
理解栈的应用：掌握括号匹配、表达式求值、DFS等经典应用
理解队列的应用：掌握BFS、层序遍历、排队模拟等经典应用
掌握中缀转后缀：理解调度场算法，能手动转换表达式
计算循环队列元素：能计算循环队列的元素个数、判空判满
应对真题题型：能解决选择、判断、代码填空等各类栈队列题目

🗺️ 本章知识图谱

栈与队列
├── 栈 Stack
│   ├── 特性：先进后出 FILO
│   ├── 基本操作
│   │   ├── push（入栈）
│   │   ├── pop（出栈，不返回值）
│   │   ├── top（栈顶元素）
│   │   ├── empty（判空）
│   │   └── size（元素数）
│   ├── 常见应用
│   │   ├── 括号匹配
│   │   ├── 表达式求值（后缀表达式）
│   │   ├── 中缀转后缀（调度场算法）
│   │   ├── DFS 深度优先搜索
│   │   ├── 函数调用栈
│   │   └── 递归转非递归
│   └── STL：stack
├── 队列 Queue
│   ├── 特性：先进先出 FIFO
│   ├── 基本操作
│   │   ├── push（入队）
│   │   ├── pop（出队，不返回值）
│   │   ├── front（队首元素）
│   │   ├── back（队尾元素）
│   │   ├── empty（判空）
│   │   └── size（元素数）
│   ├── 常见应用
│   │   ├── BFS 广度优先搜索
│   │   ├── 层序遍历
│   │   └── 排队模拟
│   └── STL：queue
├── 循环队列
│   ├── 数组实现
│   ├── front 队头指针
│   ├── rear 队尾指针（指向最后一个元素的下一位）
│   ├── 判空：front == rear
│   ├── 判满：(rear + 1) % maxSize == front
│   ├── 元素数：(rear - front + maxSize) % maxSize
│   └── 牺牲一个存储位区分空和满
├── 优先队列
│   ├── priority_queue
│   ├── 默认：大顶堆（最大的在前面）
│   ├── 小顶堆：greater<int>
│   └── 应用：贪心、TopK问题
└── 经典对比
    ├── 栈 vs 队列
    ├── 数据结构：栈 vs 队列
    └── DFS vs BFS

📖 引言

栈与队列是六级考试中最核心的数据结构考点，几乎每年必考，尤其以循环队列的下标计算和栈的应用场景最为高频。

准备好了吗？我们一口气拿下它。

一、栈（Stack）——后进先出 LIFO

1.1 定义

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

后进先出（Last In First Out，LIFO）
类比：一摞盘子，最后放上去的最先被拿走

栈顶 ← 3  ← 最后入栈，最先出栈
       2
栈底 ← 1  ← 最先入栈，最后出栈

1.2 核心操作

操作	含义	时间复杂度
`push(x)`	将元素x压入栈顶	O(1)
`pop()`	弹出栈顶元素	O(1)
`top()`	返回栈顶元素（不弹出）	O(1)
`empty()`	判断栈是否为空	O(1)
`size()`	返回栈中元素个数	O(1)

⚠️ 高频易错点：pop() 只弹出元素，不返回被弹出的值！要获取栈顶值，必须先 top() 再 pop()。

1.3 C++ STL `std::stack`

cpp

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << s.top() << endl;   // 输出 3
    s.pop();                    // 弹出 3
    cout << s.top() << endl;   // 输出 2
    cout << s.size() << endl;  // 输出 2
    cout << s.empty() << endl; // 输出 0 (false)
    return 0;
}

1.4 栈的经典应用

① 括号匹配

核心思路：遇到左括号入栈，遇到右括号检查栈顶是否匹配。

cpp

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == ']' && st.top() != '[') return false;
            if (c == '}' && st.top() != '{') return false;
            st.pop();
        }
    }
    return st.empty(); // 栈为空说明全部匹配
}

🎯 考试常见考法：给出入栈序列，问可能的出栈序列。记住：合法出栈序列数 = 卡特兰数 C(2n,n)/(n+1)。

② 后缀表达式求值

后缀表达式（逆波兰表达式）：运算符在两个操作数之后，如 3 4 + 5 * 表示 (3+4)*5。

核心思路：

遇到数字 → 入栈
遇到运算符 → 弹出栈顶两个数，计算后结果入栈
最终栈中只剩一个数，即为答案

cpp

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop(); // 注意：b是后入栈的
            int a = st.top(); st.pop(); // a是先进栈的
            if (token == "+") st.push(a + b);
            if (token == "-") st.push(a - b);
            if (token == "*") st.push(a * b);
            if (token == "/") st.push(a / b); // 整数除法向零取整
        } else {
            st.push(stoi(token));
        }
    }
    return st.top();
}

⚠️ 易错点：出栈顺序！先弹出的是右操作数b，后弹出的是左操作数a。减法和除法中 a、b 顺序不能搞反！

③ DFS的本质

深度优先搜索（DFS）天然使用栈结构（递归本身就是用系统栈实现）。这也是为什么栈在图论和搜索算法中如此重要。

二、队列（Queue）——先进先出 FIFO

2.1 定义

队列也是一种受限的线性表，一端入队（队尾），一端出队（队头）。

先进先出（First In First Out，FIFO）
类比：排队买饭，先来的先买

队头 ← 1  2  3  ← 队尾
        先出       后入

2.2 核心操作

操作	含义	时间复杂度
`push(x)`	将元素x加入队尾	O(1)
`pop()`	弹出队头元素	O(1)
`front()`	返回队头元素	O(1)
`back()`	返回队尾元素	O(1)
`empty()`	判断队列是否为空	O(1)
`size()`	返回队列中元素个数	O(1)

⚠️ 注意区分：栈操作的是 top()，队列操作的是 front() 和 back()。

2.3 C++ STL `std::queue`

cpp

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << q.front() << endl;  // 输出 1
    cout << q.back() << endl;   // 输出 3
    q.pop();                     // 弹出 1
    cout << q.front() << endl;  // 输出 2
    cout << q.size() << endl;   // 输出 2
    return 0;
}

2.4 队列的经典应用

① BFS（广度优先搜索）

BFS 天然使用队列实现，逐层扩展搜索：

cpp

void bfs(int start) {
    queue<int> q;
    bool visited[1005] = {false};
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 访问节点u
        
        for (int v : adj[u]) { // 遍历u的所有邻居
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

② 任务调度

操作系统中，多个任务按到达顺序排队，先到先服务（FCFS），就是队列的典型应用。

三、循环队列——为什么要"循环"？

3.1 为什么需要循环队列？

用数组实现普通队列：入队时 tail++，出队时 head++。问题在于：

初始状态: [_, _, _, _, _]   head=0, tail=0
入队3次:  [1, 2, 3, _, _]   head=0, tail=3
出队2次:  [_, _, 3, _, _]   head=2, tail=3
再入队2次: [_, _, 3, 4, 5]   head=2, tail=5 ← 满了！

数组前面明明有空位（下标0、1），却无法使用了！空间浪费！

循环队列的解决方案：让数组"首尾相连"形成环。

3.2 数组实现

核心变量：

head：队头指针，指向队头元素
tail：队尾指针，指向下一个入队位置（注意不是队尾元素！）
maxSize：数组最大容量

3.3 关键公式（⭐ 选择题高频考点！）

操作	公式
入队	`data[tail] = x; tail = (tail + 1) % maxSize;`
出队	`x = data[head]; head = (head + 1) % maxSize;`
判空	`head == tail`
判满	`(tail + 1) % maxSize == head`
队列中元素个数	`(tail - head + maxSize) % maxSize`

⚠️ 高频易错点1：判满条件是 (tail+1) % maxSize == head，即牺牲一个存储位来区分空和满。此时实际最多存 maxSize - 1 个元素。

⚠️ 高频易错点2：元素个数公式 (tail - head + maxSize) % maxSize 中的 + maxSize 是为了防止负数取模。很多选择题会考这个公式！

⚠️ 高频易错点3：下标计算一律是 (x + 1) % maxSize，不是 x++。

3.4 完整实现

cpp

class CircularQueue {
    int data[1005];
    int head, tail, maxSize;
public:
    CircularQueue(int size) {
        maxSize = size;
        head = tail = 0;
    }
    
    bool isEmpty() {
        return head == tail;
    }
    
    bool isFull() {
        return (tail + 1) % maxSize == head;
    }
    
    bool enqueue(int x) {
        if (isFull()) return false;
        data[tail] = x;
        tail = (tail + 1) % maxSize;
        return true;
    }
    
    bool dequeue(int &x) {
        if (isEmpty()) return false;
        x = data[head];
        head = (head + 1) % maxSize;
        return true;
    }
    
    int size() {
        return (tail - head + maxSize) % maxSize;
    }
};

四、优先队列（priority_queue）

4.1 概念

优先队列不再按 FIFO 规则出队，而是按优先级出队——每次出队的都是优先级最高的元素。

底层实现：堆（Heap），入队出队时间复杂度均为 O(log n)。

4.2 默认大顶堆

C++ 的 priority_queue 默认是大顶堆（最大值先出队）：

cpp

#include <queue>
priority_queue<int> pq; // 大顶堆
pq.push(3);
pq.push(1);
pq.push(5);
pq.push(2);

cout << pq.top() << endl; // 输出 5（最大值）
pq.pop();                  // 弹出 5
cout << pq.top() << endl; // 输出 3

4.3 自定义排序

小顶堆（最小值先出队）：

cpp

#include <functional>
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
pq.push(3);
pq.push(1);
pq.push(5);
cout << pq.top() << endl; // 输出 1（最小值）

自定义结构体排序：

cpp

struct Node {
    int val, priority;
    // 优先级小的先出队（小顶堆）
    bool operator<(const Node& other) const {
        return priority > other.priority; // 注意：这里用 > 表示优先级小者优先出队
    }
};

priority_queue<Node> pq;

⚠️ 易错点：operator< 中用 > 实现小顶堆，用 < 实现大顶堆。逻辑是反的！

4.4 应用场景

Dijkstra 最短路径算法（📚 拓展 · 超纲）：用小顶堆优化，每次取距离最小的节点
Top-K 问题：找第K大/小的元素
合并有序序列：用优先队列维护多路归并
任务调度：按优先级分配CPU时间

五、栈 vs 队列对比总结

对比项	栈（Stack）	队列（Queue）
存取原则	后进先出（LIFO）	先进先出（FIFO）
操作端	仅栈顶一端	队头出，队尾入
插入操作	`push(x)`	`push(x)`
删除操作	`pop()`	`pop()`
查看操作	`top()`	`front()` / `back()`
典型应用	括号匹配、后缀表达式、DFS	BFS、任务调度
优先队列	无	按优先级出队
底层结构	数组/链表（STL默认deque）	数组/链表（STL默认deque）

六、经典案例完整代码

案例1：后缀表达式求值

cpp

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b);
        } else {
            st.push(stoi(token));
        }
    }
    return st.top();
}

int main() {
    // 计算 (3 + 4) * 5 = 35
    vector<string> tokens = {"3", "4", "+", "5", "*"};
    cout << "结果: " << evalRPN(tokens) << endl; // 输出 35
    return 0;
}

案例2：括号匹配

cpp

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty();
}

int main() {
    cout << isValid("({[]})") << endl;  // 输出 1 (true)
    cout << isValid("([)]") << endl;    // 输出 0 (false)
    cout << isValid("((())") << endl;   // 输出 0 (false)
    return 0;
}

案例3：循环队列操作演示

cpp

#include <iostream>
using namespace std;

int main() {
    const int maxSize = 6; // 数组大小6，实际最多存5个元素
    int data[maxSize];
    int head = 0, tail = 0;
    
    // 入队: 10, 20, 30, 40, 50
    data[tail] = 10; tail = (tail + 1) % maxSize;
    data[tail] = 20; tail = (tail + 1) % maxSize;
    data[tail] = 30; tail = (tail + 1) % maxSize;
    data[tail] = 40; tail = (tail + 1) % maxSize;
    data[tail] = 50; tail = (tail + 1) % maxSize;
    // 此时队列已满: tail=5, head=0, (5+1)%6=0==head ✓
    
    cout << "元素个数: " << (tail - head + maxSize) % maxSize << endl; // 5
    
    // 出队两次
    int x;
    x = data[head]; head = (head + 1) % maxSize; // 出队10
    x = data[head]; head = (head + 1) % maxSize; // 出队20
    
    cout << "出队后元素个数: " << (tail - head + maxSize) % maxSize << endl; // 3
    cout << "队头元素: " << data[head] << endl; // 30
    
    // 再入队: 60, 70（利用前面的空位！）
    data[tail] = 60; tail = (tail + 1) % maxSize;
    data[tail] = 70; tail = (tail + 1) % maxSize;
    // tail = (5+2)%6 = 1
    
    cout << "循环后元素个数: " << (tail - head + maxSize) % maxSize << endl; // 5
    // 队列: 30 40 50 60 70
    
    return 0;
}

七、📝 实战练习

练习题 1（单选题）

题目： 一个循环队列用大小为8的数组实现，head=2，tail=6。此时队列中有多少个元素？

A. 2
B. 4
C. 6
D. 8

🔑 点击查看答案与解析

答案： B

**解析：**元素个数 = (tail - head + maxSize) % maxSize = (6 - 2 + 8) % 8 = 12 % 8 = 4。

判断是否满了：(tail + 1) % maxSize = (6+1) % 8 = 7 ≠ head(2)，所以没满。

---

练习题 2（单选题）

题目： 一个循环队列数组大小为5，初始为空。依次执行以下操作：入队A、入队B、入队C、入队D、出队、入队E。此时队列从队头到队尾依次是？

A. B, C, D, E
B. A, B, C, D, E
C. C, D, E, B
D. B, C, D

🔑 点击查看答案与解析

答案： A

**解析：**maxSize=5，最多存4个元素。

逐步模拟（head=0, tail=0）：

入A: data[0]=A, tail=1
入B: data[1]=B, tail=2
入C: data[2]=C, tail=3
入D: data[3]=D, tail=4 → 此时满了！(4+1)%5=0==head
出队: 出A, head=1
入E: data[4]=E, tail=(4+1)%5=0

队头到队尾：data[1]到data[4] = B, C, D, E

---

练习题 3（编程题）

题目： 给定中缀表达式 3 + 4 * 2，手动将其转换为后缀表达式，并用栈模拟求值过程。

🔑 点击查看答案与解析

练习题三中缀转后缀（使用调度场算法）：

3 + 4 * 2 → 后缀表达式：3 4 2 * +

栈模拟求值过程：

读入	操作	栈状态
3	入栈	[3]
4	入栈	[3, 4]
2	入栈	[3, 4, 2]
*	弹出2和4，4×2=8入栈	[3, 8]
+	弹出8和3，3+8=11入栈	[11]

结果：11（即 3 + (4 × 2) = 3 + 8 = 11）

---

练习题 4（判断题）

题目： 栈的特点是先进先出（FIFO），队列的特点是后进先出（LIFO）。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 正好说反了！

栈 Stack：先进后出 FILO（First In Last Out）
队列 Queue：先进先出 FIFO（First In First Out）

🍎 生活比喻：
栈 = 叠盘子：最后放上去的第一个被拿走
队列 = 排队：先来的先服务

---

练习题 5（单选题）

题目： 循环队列用数组实现，数组大小为 5（下标 0~4），front=1，rear=4。队列中有多少个元素？（）

A. 3
B. 4
C. 5
D. 2

🔑 点击查看答案与解析

答案： A

解析： 循环队列元素个数公式： (rear - front + maxSize) % maxSize

代入数值：

front = 1, rear = 4, maxSize = 5
元素数 = (4 - 1 + 5) % 5 = 8 % 5 = 3

验证：元素在 data[1], data[2], data[3] = 3 个元素（rear 指向队尾的下一个位置，所以 data[4] 是空的）。

选 A。

🔥 高频考点：循环队列的元素数计算是必考题！公式：(rear - front + maxSize) % maxSize。加 maxSize 是为了防止负数。

---

练习题 6（判断题）

题目： 循环队列中（牺牲一个存储位），判断队满的条件是？（）

A. front == rear
B. (rear + 1) % maxSize == front
C. rear == maxSize
D. front == 0 && rear == maxSize - 1

🔑 点击查看答案与解析

答案： B

解析： 循环队列的两个核心判断：

判空：front == rear
判满：(rear + 1) % maxSize == front（牺牲一个存储位）

为什么要牺牲一个存储位？因为如果不牺牲，那么"空"和"满"时 front 都等于 rear，无法区分。

选 B。

💡 记忆技巧：队满 = 队尾再往前走一步就碰到队头了。用取模是因为循环，走到末尾要回到开头。

---

练习题 7（单选题）

题目： C++ 的 priority_queue 默认是大顶堆还是小顶堆？要实现小顶堆应该怎么写？（）

A. 默认小顶堆；priority_queue<int, vector<int>, greater<int>> 是大顶堆
B. 默认大顶堆；priority_queue<int, vector<int>, greater<int>> 是小顶堆
C. 默认大顶堆；priority_queue<int, vector<int>, less<int>> 是小顶堆
D. 默认小顶堆；priority_queue<int, vector<int>, less<int>> 是大顶堆

🔑 点击查看答案与解析

答案： B

解析：

C++ 的 priority_queue 默认是大顶堆（最大的元素排在队首）
要实现小顶堆，需要指定比较器：priority_queue<int, vector<int>, greater<int>>
less<int> 是大顶堆（默认），greater<int> 是小顶堆

选 B。

🔥 易错点：很多同学搞反 greater 和 less。记住：greater = 大于 = 小的在前（小顶堆）；less = 小于 = 大的在前（大顶堆）。

---

练习题 8（判断题）

题目： 给定一个只包含 ( 和 ) 的字符串，判断括号是否有效匹配。

输入：一个字符串
输出：匹配输出 "Yes"，不匹配输出 "No"

样例输入 1：(())
样例输出 1：Yes

样例输入 2：())
样例输出 2：No

🔑 点击查看答案与解析

答案：

cpp

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);       // 左括号入栈
        } else {
            if (st.empty()) return false;  // 右括号多余
            st.pop();                     // 匹配成功，弹出左括号
        }
    }
    return st.empty();  // 栈空说明全部匹配
}

int main() {
    string s;
    cin >> s;
    if (isValid(s)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

解析： 括号匹配是栈的经典应用：

遇到左括号：入栈
遇到右括号：
- 如果栈空，说明右括号多余 → 不匹配
- 否则弹出栈顶（一个左括号），表示匹配成功
遍历结束后，栈必须为空（左括号不能有剩余）

💡 扩展：如果有多种括号（{}），遇到左括号都入栈，遇到右括号就看栈顶是不是对应的左括号。

---

八、📊 考点总结表

考点	重要程度	出题形式	易错点
栈的特性（FILO）	⭐⭐⭐⭐⭐	选择/判断	和队列搞反
队列的特性（FIFO）	⭐⭐⭐⭐⭐	选择/判断	和栈搞反
栈的基本操作（push/pop/top）	⭐⭐⭐⭐	选择/代码填空	pop不返回值，要用top先取
队列的基本操作（push/pop/front）	⭐⭐⭐⭐	选择/代码填空	pop不返回值，要用front先取
循环队列判空判满	⭐⭐⭐⭐⭐	选择/代码填空	空：front==rear；满：(rear+1)%size==front
循环队列元素个数计算	⭐⭐⭐⭐⭐	选择/计算	(rear-front+size)%size
循环队列入队出队指针变化	⭐⭐⭐⭐⭐	代码填空/选择	取模运算：(x+1)%maxSize
牺牲一个存储位	⭐⭐⭐⭐	选择/判断	区分空和满
栈的应用（括号匹配、表达式求值）	⭐⭐⭐⭐⭐	编程题/选择	右操作数先弹出
队列的应用（BFS、层序遍历）	⭐⭐⭐⭐	选择/编程	BFS用队列
优先队列大小顶堆	⭐⭐⭐⭐	选择/代码填空	默认大顶堆；greater是小顶堆
中缀转后缀（调度场算法）	⭐⭐⭐	选择/程序阅读	运算符优先级

⭐ 必背速记卡

┌─────────────────────────────────────────────────────────────┐
│                    ⭐ 必背公式与易错点                        │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 循环队列判满: (tail + 1) % maxSize == head              │
│  2. 循环队列元素数: (tail - head + maxSize) % maxSize        │
│  3. 下标更新: x = (x + 1) % maxSize （不是 x++）             │
│  4. 牺牲一个存储位: 容量为maxSize的数组最多存maxSize-1个元素   │
│  5. pop()不返回值！先top()/front()再pop()                    │
│  6. 后缀表达式求值: 先弹出的是右操作数                       │
│  7. priority_queue默认大顶堆，greater<int>是小顶堆            │
│  8. 栈→DFS，队列→BFS，这个对应关系必须记住                   │
│                                                             │
└─────────────────────────────────────────────────────────────┘

九、全书回顾 · 六级知识地图

从第1章到本章，你已经走完了 GESP 六级 C++ 备考的完整路径：

章	主题	对应考纲知识块
第1章	总览：六大考点全景	——
第2章	树的基本概念与遍历	树的基本概念、构造与遍历
第3章	哈夫曼树与特殊树	哈夫曼树、完全二叉树、二叉排序树；哈夫曼编码、格雷编码
第4章	搜索算法	DFS、BFS、二叉树的搜索算法
第5章	简单动态规划	一维动态规划、简单背包
第6章	面向对象编程基础	面向对象思想、类的创建与初始化、封装/继承/多态
第7章	栈与队列	栈、队列、循环队列

七章内容，从考纲全景出发，你认识了树并掌握了它的四种遍历与"前序+中序还原"；你学会了哈夫曼树的构造、哈夫曼编码与格雷编码；你用 DFS/BFS 走迷宫、搜连通块；你把"打家劫舍"和"01 背包"化成一维递推；你第一次写下 class，理解了封装、继承与多态；现在，你又把栈、队列、循环队列与优先队列的用法和下标计算牢牢记住。🎉 六级考纲的每一块版图，你都已走遍。

🎯 冲刺阶段备考规划（考前 2~3 周）

回归基础概念：把七章的核心定义与公式再通读一遍，确保没有遗漏
重点突破：
- 循环队列下标计算（选择题必考，必须手算熟练）
- 栈的出栈序列合法性判断（卡特兰数）
- 树的遍历序列互推（前序 + 中序 → 后序，反之亦然）
- 一维 DP 的状态定义与递推方向（01 背包必须倒序）
刷题策略：按知识点分类刷题，每个知识点至少做 20~30 道题

答案： B

**解析：**元素个数 = (tail - head + maxSize) % maxSize = (6 - 2 + 8) % 8 = 12 % 8 = 4。

判断是否满了：(tail + 1) % maxSize = (6+1) % 8 = 7 ≠ head(2)，所以没满。

答案： A

**解析：**maxSize=5，最多存4个元素。

逐步模拟（head=0, tail=0）：

入A: data[0]=A, tail=1
入B: data[1]=B, tail=2
入C: data[2]=C, tail=3
入D: data[3]=D, tail=4 → 此时满了！(4+1)%5=0==head
出队: 出A, head=1
入E: data[4]=E, tail=(4+1)%5=0

队头到队尾：data[1]到data[4] = B, C, D, E

第7章 栈与队列 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

📖 引言 ​

一、栈（Stack）——后进先出 LIFO ​

1.1 定义 ​

1.2 核心操作 ​

1.3 C++ STL std::stack ​

1.4 栈的经典应用 ​

二、队列（Queue）——先进先出 FIFO ​

2.1 定义 ​

2.2 核心操作 ​

2.3 C++ STL std::queue ​

2.4 队列的经典应用 ​

三、循环队列——为什么要"循环"？ ​

3.1 为什么需要循环队列？ ​

3.2 数组实现 ​

3.3 关键公式（⭐ 选择题高频考点！） ​

3.4 完整实现 ​

四、优先队列（priority_queue） ​

4.1 概念 ​

4.2 默认大顶堆 ​

4.3 自定义排序 ​

4.4 应用场景 ​

五、栈 vs 队列对比总结 ​

六、经典案例完整代码 ​

案例1：后缀表达式求值 ​

案例2：括号匹配 ​

案例3：循环队列操作演示 ​

七、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（编程题） ​

练习题 4（判断题） ​

练习题 5（单选题） ​

练习题 6（判断题） ​

练习题 7（单选题） ​

练习题 8（判断题） ​

八、📊 考点总结表 ​

⭐ 必背速记卡 ​

九、全书回顾 · 六级知识地图 ​

🎯 冲刺阶段备考规划（考前 2~3 周） ​

第7章栈与队列

🎯 本章学习目标

🗺️ 本章知识图谱

📖 引言

一、栈（Stack）——后进先出 LIFO

1.1 定义

1.2 核心操作

1.3 C++ STL `std::stack`

1.4 栈的经典应用

二、队列（Queue）——先进先出 FIFO

2.1 定义

2.2 核心操作

2.3 C++ STL `std::queue`

2.4 队列的经典应用

三、循环队列——为什么要"循环"？

3.1 为什么需要循环队列？

3.2 数组实现

3.3 关键公式（⭐ 选择题高频考点！）

3.4 完整实现

四、优先队列（priority_queue）

4.1 概念

4.2 默认大顶堆

4.3 自定义排序

4.4 应用场景

五、栈 vs 队列对比总结

六、经典案例完整代码

案例1：后缀表达式求值

案例2：括号匹配

案例3：循环队列操作演示

七、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（编程题）

练习题 4（判断题）

练习题 5（单选题）

练习题 6（判断题）

练习题 7（单选题）

练习题 8（判断题）

八、📊 考点总结表

⭐ 必背速记卡

九、全书回顾 · 六级知识地图

🎯 冲刺阶段备考规划（考前 2~3 周）