基础数据结构
栈
栈是一种后进先出（LIFO）的数据结构，适合处理具有嵌套或逆序特点的问题。在竞赛中，栈常用于解析表达式、匹配括号和消除连续相同元素等场景。
栈的基本操作
push(x)：把元素放到栈顶top()：查询栈顶元素（不删除）pop()：删除栈顶元素（注意：pop()不会返回值）empty()：判断栈是否为空size()：栈里元素个数
基本操作示例代码
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<int> st;
// 初始：st = [ ]（空）
st.push(10);
// st = [10]
// 栈顶在右边（或最上面）：10
st.push(20);
// st = [10, 20]
// 栈顶是 20
st.push(30);
// st = [10, 20, 30]
// 栈顶是 30
int x = st.top();
// x = 30
// st 没变：st = [10, 20, 30]
st.pop();
// 删除栈顶 30
// st = [10, 20]
st.pop();
// 删除栈顶 20
// st = [10]
cout << st.top() << "\n";
// 输出 10
// st 仍然不变：st = [10]
cout << st.size() << "\n";
// 输出 1
cout << st.empty() << "\n";
// 输出 0（0 代表 false，说明不空）
st.pop();
// 删除 10
// st = [ ]
cout << st.empty() << "\n";
// 输出 1（1 代表 true，说明是空）
return 0;
}
模板例题1：表达式求值
应用场景： 对于包含加减乘除和括号的算术表达式，要计算其结果。栈可以方便地处理运算符的优先级和括号嵌套。典型做法是使用两个栈：一个存放运算数，另一个存放运算符。算法流程为：从左到右扫描表达式，遇到数字则入数字栈，遇到运算符则根据优先级处理——如果当前运算符优先级不高于栈顶运算符，就弹出运算符栈顶进行计算，将结果压回数字栈。遇到左括号直接入运算符栈，遇到右括号则不断弹出运算符直至左括号。这样利用栈结构即可正确计算表达式的值。
讲解说明： 栈在表达式求值中扮演了“临时存储”的角色，保证了运算顺序符合优先级规则。例如表达式 3 + 5 * (2 + 6)，扫描到 ( 时将其入栈，扫描完内部子表达式并计算出结果8，将8压入数字栈，然后继续运算。借助栈，复杂的中缀表达式计算可以转换为后缀表达式再求值，或直接用双栈法完成。
练习题： 以下题目可以帮助体会栈在表达式求值中的应用：
- 验证栈序列
- 打字练习
模板例题2：括号匹配
应用场景： 判断括号序列是否正确配对是栈的经典应用场景。例如验证形如 ([]{}) 的字符串是否为合法括号序列，或在表达式中检查括号是否成对匹配。利用栈的后进先出特性，我们可以自然地处理嵌套的括号结构。
讲解说明： 算法非常直观：从左到右遍历字符串，遇到左括号（如 (、[、{）就压栈，遇到右括号（如 )、]、}）时就从栈顶弹出一个左括号进行匹配。如果类型不对应或者栈已空，则匹配失败；遍历结束后如果栈不为空，则说明有未匹配的左括号，也是不合法的。借助栈，能够正确识别多层嵌套的括号结构。例如字符串 {[()()]}，栈的变化过程对应了括号从内层到外层的匹配，非常形象地模拟了人手工检查括号配对的过程。
练习题： 以下题目涉及括号匹配及其变形，适合使用栈来解决：
- 括号匹配初级
- 移动括号
模板例题3：连续相同项消除（消消乐）
应用场景： 给定一个元素序列（例如字符串或数字序列），当出现相邻且相同的元素时予以消除，并将两端连接继续检查，直到无法再消除为止。这类“消消乐”问题常用于字符串消除、相邻元素抵消等场景，使用栈可以高效模拟这一过程。
讲解说明： 栈的核心思想是当新元素和栈顶元素相同时，就弹出栈顶而不是将新元素入栈，这相当于消除了这一对相同元素。如果不相同则正常入栈。遍历完整个序列后，未被消除的元素将顺序保留在栈中。例如处理字符串ABBBAAC：从左到右，A入栈；遇到B入栈；下一个B与栈顶相同，弹出栈顶（消除一对B）；继续下一个B，与新栈顶（此时为A）不同，入栈；如此继续，当扫描完毕后栈中剩下的序列即为消除后的结果。栈在这里保证了消除的局部操作能正确传递影响，相当于自动维护了当前未消除序列。
练习题： 以下题目围绕相邻消除的规则，使用栈实现模拟：
- CSP-S 2023 消消乐（O（n²））:从左到右遍历字符串，然后用栈存储，如果新加入的字符和栈顶字符相同，则消除（栈顶pop），否则就把新元素放入栈中。若栈为空说明能全部消除完。
队列
队列是一种先进先出（FIFO）的数据结构，善于处理按序序列和循环过程的问题。典型应用包括模拟循环队列（如约瑟夫问题）、固定窗口数据处理，以及广度优先搜索等。
队列的基本操作
push(x)：从队尾加入front()：查询队首元素pop()：删除队首元素empty()：是否为空size()：队列长度
基本操作示例代码
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> q;
// 初始：q = [ ]（空）
q.push(10);
// q = [10]
// 队首 = 10，队尾 = 10
q.push(20);
// q = [10, 20]
// 队首 = 10，队尾 = 20
q.push(30);
// q = [10, 20, 30]
// 队首 = 10，队尾 = 30
int x = q.front();
// x = 10
// q 不变：q = [10, 20, 30]
q.pop();
// 删除队首 10
// q = [20, 30]
cout << q.front() << "\n";
// 输出 20
// q 不变：q = [20, 30]
cout << q.size() << "\n";
// 输出 2
cout << q.empty() << "\n";
// 输出 0（不空）
q.pop();
// 删除 20
// q = [30]
q.pop();
// 删除 30
// q = [ ]
cout << q.empty() << "\n";
// 输出 1（为空）
return 0;
}
模板例题1：循环模拟
应用场景： 约瑟夫问题是经典的循环队列模拟题。有 n 个人围成一圈，每次数到第 m 个就将其淘汰，问最后剩下的人是谁。使用队列可以直接模拟这个过程：初始时将1到n号依次入队，然后不断将队首元素出队并将其淘汰或尾部重插达到循环效果。除了约瑟夫问题，各种需要“循环轮转”处理的情景都可以用队列实现。
讲解说明： 队列天然支持将队首元素移到队尾这一操作，正好吻合了循环游戏的流程。以约瑟夫问题为例，最初队列按顺序装入所有人编号。然后执行以下循环：将前m-1个元素依次出队再入队（相当于数数过程），第m个出队的人就是淘汰者（不再入队）。如此往复直到剩下最后一个元素。队列的FIFO特性保证了顺序轮转的正确性。这个过程如果用数组模拟会比较繁琐，而用队列操作弹出和加入就极为简洁。
练习题： 以下题目可以使用循环队列模拟来解决：
- 约瑟夫问题
- 三人游戏
- 乒乓球
- 礼物摆放
- 周末舞会
模板例题2：固定窗口元素处理
应用场景： 对一序列元素进行滑动窗口处理，即在长度为k的窗口内进行某种计算，然后窗口每次向右滑动一格。这类操作包括滑动窗口求和/平均值、统计不同元素个数等。例如“最近使用的缓存”机制：系统只能记住最近的k个访问过的元素，每新访问一个元素，如果它已在缓存中则命中，否则产生缺失并将其加入缓存（若缓存满则淘汰最早的元素）。队列可以很好地模拟固定窗口随时间推移的更新。
讲解说明： 以缓存模拟为例，队列维护了当前窗口内的元素（按访问顺序）。当有新元素访问时，检查它是否已在当前窗口：如果在，则通常不重复加入（可能更新其位置，视具体规则）；如果不在，则意味着一次“未命中”，需要将它加入队尾，同时如果队列长度超过k，就从队首移除最早的元素。通过队首、队尾的操作，队列始终保持最多k个最近元素。这和现实中队列排队先来先服务的机制一致。另一类滑动窗口问题是计算每个窗口内的某些统计量，如果不要求使用单调队列优化，也可用普通队列每次进出一个元素来维护窗口。
练习题： 以下题目体现了固定窗口或缓存机制，可用队列模拟：
- [NOIP 2010 提高组] 机器翻译（维护大小为m的队列）
- [NOIP 2016 普及组] 海港（维护大小为1的队列）
动态数组（Vector）
动态数组指运行过程中大小可变的顺序表结构。它能根据需要自动扩容或缩减，在算法竞赛中常用于处理未知规模的数据、构建可变长度的列表或表示稀疏数据结构。
动态数组的基本操作
push_back(x)：在末尾加入一个元素pop_back()：删除末尾元素a[i]：像普通数组一样按下标访问size()：当前元素个数empty()：是否为空
基本操作示例代码
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a;
// 初始：a = [ ]
a.push_back(10);
// a = [10]
a.push_back(20);
// a = [10, 20]
a.push_back(30);
// a = [10, 20, 30]
cout << a[0] << "\n";
// 输出 10（下标从 0 开始）
// a 不变：a = [10, 20, 30]
cout << a.back() << "\n";
// 输出 30（back() 查看最后一个元素）
// a 不变
a.pop_back();
// 删除最后一个 30
// a = [10, 20]
cout << a.size() << "\n";
// 输出 2
cout << a.empty() << "\n";
// 输出 0（不空）
a.clear();
// 清空整个 vector
// a = [ ]
cout << a.empty() << "\n";
// 输出 1（为空）
return 0;
}
模板例题1：动态大小顺序表
应用场景： 当需要存储的数据量在运行期间才确定，或者需要频繁执行在末尾添加/删除操作时，动态数组提供了灵活性。例如从输入中读取若干整数但事先不知道有多少，可以用动态数组不断执行push_back来存储。此外，构造一些序列时（如按需生成素数列表、逐步扩展结果等）也依赖动态数组自动扩张容量。
讲解说明： 与静态数组需要预先定义固定大小不同，动态数组会根据元素增减动态调整容量。内部机制通常是倍增扩容以摊摊降低扩容次数。在竞赛中，这意味着不必担心数组溢出或浪费空间。例如，读取一连串未知长度的数据时，可以在读取过程中使用vector.push_back(x)将元素加入数组末尾。对于需要删除末尾元素的情况，pop_back()操作也能在均摊常数时间完成。动态数组可以看作“会自动增长的数组”，既保持了随机访问的特性，又能适应规模变化。
练习题： 以下练习侧重动态数组的基本使用和容量变化：
- 团队全能赛
模板例题2：稀疏二维表示
应用场景： 在处理二维数据时，如果数据非常稀疏（大部分位置为空或默认值），使用常规的二维静态数组会浪费大量空间。这时可以采用动态数组或链表来仅存储非空元素的位置和值。例如图论中的邻接表表示法，就是用动态数组来存储每个节点的邻接点列表，相比邻接矩阵大幅节省空间，特别适用于稀疏图（边很少的图）。又比如有些问题给出一个坐标平面上的若干特殊点，我们可以用动态结构存这些点，而不必建立完整的大矩阵。
讲解说明： 以邻接表为例，我们用一个动态数组列表 adj[] 来表示图：adj[u]存储节点u的所有邻接边。这样对于有N个节点、M条边的图，空间复杂度从O(N^2)降低到O(N+M)，在M远小于N^2时节约显著。动态数组让每个节点的邻接边列表在读入时逐渐扩充，而不需预先知道节点度的上限。对于稀疏矩阵场景，如果坐标范围很大但非零元素很少，可以用一个动态数组列表保存每一行中非零元素的列号及值，或者直接用键值对映射来存非零单元。这种稀疏表示利用了动态结构按需存储的优点，避免无用的空间分配。
练习题： 以下题目涉及稀疏数据的存储或大范围坐标处理，宜采用动态数组/邻接表等结构：
- 约数表
- 兵力统计
【后置衔接知识点】
1、深度优先搜索
2、广度优先搜索
【思维导图】
【题目知识点分类】
