算法学习第二章：各种数据结构，包括链表、栈与队列、kmp算法、并查集、堆等常见数据结构（主要以数组模拟），以及c++的STL使用技巧。
1.链表
我们这里选择使用数组来模拟链表而不是使用传统的结构体定义，因为如果使用结构体定义链表，在构造新节点插入时，会需要new一个新节点，而new操作是非常慢的，在数据量稍微大一些的时候（甚至106级别的数据量），可能就会因为new操作超时，所以这里选择使用数组模拟，最主要的原因就是快，而之后的栈和队列，可以选择使用STL中的容器直接使用，不过我们在这里还是选择使用数组模拟。
我们使用两个数组来模拟单链表，分别是e[]和ne[]，其中e[i]存储的是 i 号节点的值，ne[i]存储的值是 i 号节点的下一个节点是哪个节点（节点的编号）
单链表代码实现（包括插入等链表操作）
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// head表示头结点的编号，head本身是一个虚拟节点，不存储数据，它指向的是链表第一个节点的下标
// idx表示当前我们已经使用到哪个下标了，，也就是下一次创建节点时应该分配的下标
int head, idx, e[N], ne[N];
// 初始化链表
void init() {
head = -1; // head = -1表示链表暂时没有节点
idx = 0;
}
// 在链表头节点处插入值为x的节点
void insert_to_head(int x) {
e[idx] = x;
ne[idx] = head;
haed = idx;
idx ++;
}
// 向节点编号为k的节点后面插入一个值为x的节点
void insert(int k, int x) {
e[idx] = x; // 设置数字idx下标的值为x
ne[idx] = ne[k]; // 将插入的节点的next指针设置为k号节点的next节点
ne[k] = idx; // 将k号节点的next指针设置为插入的节点
idx ++; // 移动idx
}
// 将k号节点后面的节点移除
void remove(int k) {
ne[k] = ne[ne[k]];
}
// 遍历链表，因为我们下标是从1开始的，所以如果遍历到0，说明已经遍历结束了
void interate() {
for (int i = head; i ; i = ne[i]) cout << e[i] << endl;
}这里可以看到我们对于idx的处理是只增不减的，在算法题中我们只关心程序能否在规定时间内跑完，对于内存泄露并不是很关心，这是写工程代码需要考虑的事情，我们这里为了简洁处理于是将idx设置为只增。
对于双链表，我们需要两个数组来分别表示左指针和右指针，分别用l[]和r[]表示
双链表代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N],idx, head;
// 初始化链表
void init() {
head = -1; // head = -1表示链表为空
idx = 0;
}
// 向链表头节点插入值为x的节点
void insert_to_head(int x) {
e[idx] = x;
r[idx] = head;
l[head] = idx;
l[idx] = -1;
head = idx;
idx ++;
}
// 向节点编号为k的节点右边插入一个值为x的节点
void insert(int k, int x) {
e[idx] = x; // 将新节点的值设为x
l[idx] = k; // 将新节点的左指针设为k号节点
r[idx] = r[k]; // 将新节点的右指针指向k号节点的右节点
l[r[k]] = idx; // 将k节点的下一个节点的左指针设为添加的新节点
r[k] = idx; // 将k号节点的右指针指向新节点
idx ++;
}
// 向k号节点的左边插入节点相当于向l[k]号节点的右边插入节点
intsert(l[k], x);
// 删除编号为k的节点，只需要连接l[k]和r[k]节点即可
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}2.栈与队列
栈和队列因为具有相似性，所以把它们两个放到一起。
栈
栈是一种先进后出的数据结构（FILO），在使用数组模拟栈的时候，我们需要维护一个数组表示栈以及一个指针表示栈顶
代码实现
#include <iostream>
using namespace std;
const int N = 1000;
// stk表示栈，tt表示栈顶指针
int stk[N], tt = 0;
// 向栈中插入元素
void push(int x) {
stk[++ tt] = x; // 这里使用前置递增运算符是为了方便判空和获取栈顶元素
}
// 弹出栈顶元素
int pop() {
return stk[tt --];
}
// 获取栈顶元素
int top() {
return stk[tt];
}
// 判断栈是否为空
bool empty() {
return !tt;
}队列
队列是一种先进先出的数据结构（FIFO），使用数组模拟队列的时候，需要维护一个数组表示队列和两个指针hh和tt分别表示队头和队尾。
代码实现
#include <iostream>
using namespace std;
const int N = 10000;
// tt表示队尾元素的下标， hh表示队头（不含元素，即要弹出的队头元素下标是hh+1）
int q[N], hh = 0, tt = 0;
// 向队尾插入一个元素（入队）
void push(int x) {
q[++ tt] = x;
}
// 队头元素出队，并返回出队元素
int pop() {
return q[++ hh];
}
// 获取队头元素
int top() {
return q[hh + 1];
}
// 判断队列是否为空
bool empty() {
return hh >= tt;
}可以看到hh和tt两个指针都是只增不减的，我们这里同样不考虑内存泄漏，主要是为了达到O(1)时间复杂度。我们也可以直接使用STL提供的stack和queue容器来使用栈和队列，只是用数组模拟更方便。
用数组模拟栈和队列的一个典型算法就是单调栈和单调队列，详细例题参考单调栈和滑动窗口
单调栈：给出项数为 n 的整数数列 a1…n。定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标。若不存在，则 f(i)=0。试求出 f(1…n)。
思路：单调栈单调队列的优化思路和双指针类似，都是先从暴力做法开始。然后在暴力算法基础上进行优化。本题最简单的暴力算法就是二重循环，时间复杂度为O(n2)。优化的第一步就是我们可以维护一个数字，我们每遍历到一个元素，就可以将其下标先放入数组，之后我们每遍历到一个元素，可以和数组中的元素比较，如果发现数组中的元素比这个数小，则将对应的答案设置为当前下标，同时需要将已经获得答案的数移除数组，很显然越小的数越容易被移出数组，因此我们可以维护一个单调栈，栈顶永远是最小的元素，当遍历到的元素比栈顶元素小时，则弹出栈，然后继续比较下一个栈顶元素，比较完成之后将当前元素入栈
代码实现
#include <iostream>
using namespace std;
const int N = 100000;
// ans存储的就是f(i)，stk存储的是下标
int stk[N], a[N], ans[N];
int n, tt = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) {
while (tt && a[stk[tt]] < a[i]) ans[stk[tt --]] = i;
stk[++ tt] = i;
}
for (int i = 1; i<= n; i ++) cout << a[i] << " ";
return 0;
}时间复杂度分析：从tt角度来分析，每个数最多只会进栈一次和出栈一次，因此最多有2n次操作，故时间复杂度为O(n)。
单调队列：有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。
例如，对于序列 [1,3,−1,−3,5,3,6,7] 以及 k=3，有如下过程：
解题思路：首先还是经典的暴力二重循环遍历，时间复杂度O(n2)，我们可以发现，在遍历的过程中，如果窗口进入了一个数比前面的数字大，那么它前面的数字就不会再出现在答案中了，我们就可以丢弃它，同样如果数字比前面的数组小，同样也可以丢弃前面的数字了，基于这个思想我们便可以使用一个队列来解决这个问题
代码实现
#include <iostream>
using namespace std;
const int N = 100010;
// q是我们定义的单调队列，hh表示队列最后一个元素的左指针，tt表示队尾指针
int q[N], a[N];
int n, k ,tt = 0, hh = 0;
int main() {
cin >> n >> k;
for (int i = 0; i < n; i ++) cin >> a[i];
// 先求每个滑动窗口的最小值
for (int i = 0; i < n; i ++) {
// 如果队列中有比a[i]还大的值，那么这些值永远不会作为答案输出了，因此可以舍弃。
while (tt > hh && a[q[tt]] >= a[i]) tt --;
// 这里必须先入队，否则后面判断时队列可能为空从而被前面的脏数据影响
q[++ tt] = i;
// 如果队头下标已经不在窗口内了，则出队
if (q[hh + 1] < i - k + 1) hh ++;
// 只有窗口左侧到0下标的时候才开始输出
if (i >= k - 1) cout << q[hh + 1] << " ";
}
// 清空队列
cout << endl;
hh = tt = 0;
// 求最大值，流程是一样的，求最大值和最小值代码是对称的
for (int i = 0; i < n; i ++) {
while (tt > hh && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if (q[hh + 1] < i - k + 1) hh ++;
if (i >= k - 1) cout << q[hh + 1] << " ";
}
return 0;
}时间复杂度分析：对于每个元素同样最多入队一次和出队一次，最多有2n次操作，时间复杂度为O(n)。
总的来说单调栈和单调队列虽然算法比较抽象，但是其应用场景并不多，比较典型的就是本文中给出的例题，其中滑动窗口使用的相对来说更加广泛，当我们在解题过程中能够将解题过程分解出来滑动窗口这个模型，我们就可以使用单调队列来优化。
3.KMP算法
kmp算法是用来在一个长字符串s中找到一个短字符串p所有出现的位置的算法。
核心思想：如果采用传统的暴力扫描，我们需要使用一个二重循环来遍历两个字符串，时间复杂度为O(n2)，但是这种做法显然丢失了很多信息。假设当前匹配到了s[i]和p[j + 1]（为什么是 j + 1 而不是 j 通过后面的内容可以看到是为了方便表示），在传统的二重循环中，如果我们判断s[i] != p[j + 1]，我们就会从头开始匹配，但是这会导致我们浪费了一个关键信息：s[i]和p[j + 1]虽然不匹配，但是它们之前的内容是全部可以匹配上的，于是我们就会想到：能否不从头开始匹配，而是在前面找一个位置，从这个位置开始可以继续和s[i]开始匹配，也就是说，本来我们找到的匹配的区间的是p[1, j]，因为p[j + 1]无法匹配，我们需要再找一个区间p[1, k]继续开始匹配，这要求p[1, k]也可以和s[i]之前的字符串匹配上，这样就可以减少了很多不必要的过多回退。
实现kmp算法的核心难点在于如何找到匹配失败后应该从哪里继续开始，我们不需要每次匹配失败后都临时去找这个位置，我们可以在最开始就维护一个数组ne[]，该数组记录了每次匹配失败后应该回退的位置。ne[j]表示以p[j]为结尾的子字符串，最远可以和从p字符串起始位置开始的多远的子字符串匹配。也就是说假设ne[j] = k，表示p[1, k] = p[j - k + 1, j]，当p[j]匹配失败之后，可以将p前移一定位置继续匹配，下次开始匹配的位置就是ne[j] + 1；
前面提到为什么要用p[j + 1]而不是p[j]，因为p[j]表示我们匹配到的最后一个相等的字符，可以直接使用ne[j]来回退到对应位置，从ne[j] + 1开始继续匹配。
kmp算法代码实现
#include <iostream>
using namespace std;
const int N = 100010;
// n，m分别表示s和p的长度
int n, m;
int s[N], p[N], ne[N];
int main() {
// 这里选择从1下标开始读取是避免边界问题，不需n要对0进行判断
cin >> n >> s + 1 >> m >> p + 1;
// 求ne数组的过程可以看作是p和p自己匹配
// 显然ne[1] = 0，所以这里从下标为2开始匹配
for (int i = 2, j = 0; i < m; i ++) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
// 匹配过程，这里j初始值设为0是因为我们规定待匹配的下标是j + 1
for (int i = 1, j = 0; i <= n; i ++) {
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++;
// 如果匹配成功，则输出字符串起始位置
if (j == m) cout << i - m + 1 << " ";
}
return 0;
}时间复杂度分析：虽然我们代码中使用的是二重循环，但是主串指针i和子串指针j（子串起始位置的指针）是不会回退的，所以时间复杂度不会超过O(n + m)，而在大部分题目中n和m的数量级相差又会很大，所以时间复杂度近似为O(n)。
4.Trie前缀树
Tire前缀树是一种高效地存储和查询字符串集合的数据结构，它使用树结构记录集合中的字符串，每个节点包含一个字符，该节点的子节点表示有多少字符串是以该节点及之前节点为前缀的。
例如，集合["apple", "app", "banana", "bat"]的trie前缀表示为
root
/ \
a b
/ /
p a
/ / \
p★ n t ★
/ /
l a
/ /
e ★ n
/
a ★
说明：★标记表示有一个以该节点为结尾的字符串我们这里依然使用数组来表示这棵树用一个二维数组来表示，其中每个元素有26列，分别对应26个字母（这里假设字符串都是由小写字母组成的），数组的每个值表示下一个节点的行下标。代码实现如下：
#include <iostream>
using namespace std;
const int N = 100010;
/*
cnt[i]表示以i号节点结尾的字符串有多少个，idx表示下一次插入应该使用哪个下标
0号下标既表示根节点，又表示空节点，当节点没有子节点时，其子节点下标就是默认的0，也就是空节点
*/
int t[N][26], cnt[N], idx = 0;
// 向树中插入一个字符串
void insert(char[] str) {
int p = 0; // 当前遍历到的节点的下标
for (int i = 0; str[i]; i ++){
// 将字符串中的字符映射的0-26；
int u = str[i] - 'a';
// 如果该节点还没有值，也就是还未被插入，则插入，下标使用++ idx是因为0下标是根节点，不能被使用
if (!t[p][u]) t[p][u] = ++ idx;
p = t[p][u];
}
cnt[p] ++;
}
// 查找一个字符串在集合中出现的次数
int query(char[] str) {
int p = 0;
for (int i = 0; str[i]; i ++) {
int u = str[i] - 'a';
if (!t[p][u]) return 0; // 节点为空直接返回0
p = t[p][u];
}
return cnt[p];
}Trie树在实际使用场景中并不多，其本身用途已经表明了使用场景：存储和快速查找字符串集合。其时间复杂度为O(m)，m为传入的字符串长度，比传统的暴力比较的算法（O(mn)）要好得多。
5.并查集
并查集是一种高效地维护多个集合的数据结构，其可以快速完成一个多个集合之间的操作，比如判断两个元素是否在同一集合中、将两个集合合并等操作。
基本原理：每个集合使用一棵树表示，树的根节点编号等于其自己，表示该集合的编号，子节点的编号是父节点的编号。
在实现并查集的时候，我们需要解决三个问题：
如何判断两个元素是否在同一个集合中 ？
如何快速寻找一个元素在哪个集合中 ？
如何合并两个集合
对于问题一和问题二，定义一个find函数，返回值为当前元素所在的集合编号，其会判断当前元素的值是否等于下标，如果等于说明当前元素就是根节点，则直接返回下标，即元素编号。如果不等于下标，则递归地查找父节点的编号。
对于问题三，直接寻找到两个集合中任意一个的根节点，将该根节点的值设置为另一个集合的编号即可。
代码实现
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int p[N]; // 存储树的数组、
// 并查集核心操作：查找一个元素所在的数组编号
int find(int x) {
/*
这里涉及到并查集的优化：路径压缩
在递归查找过程中，如果我们发现某一节点或其父节点不是根节点，我们就将它直接指向节点。
这种优化可以使后续再次查找该元素所在集合的时间复杂度降低为O(1)。
*/
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 合并a，b两个元素所在的集合，直接使用find函数查找到ab两个元素所在根节点，然后将其中一个根节点加入到另一个集合中即可
void merge(int a,int b){
p[find(a)] = find(b);
}
// 初始化函数，开始时所有元素本身就是一个集合，每个下标的元素都是它自己
void init() {
cin >> n;
for (int i = 0; i < n; i ++) a[i] = i;
}并查集扩展
在多数情况下，只用并查集是不能解决问题的，很多时候我们还需要额外维护一些信息，例如集合元素的数量或元素到根节点的距离等等，下面的示例代码就展示了如何维护每个集合的元素数量。
#include <iostream>
using namespace std;
const int N = 10010;
// 只有根节点的size值代表本集合的元素个数
int size[N], p[N], n;
// 查找一个元素的根节点
int find(int x) {
if (!p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 将a和b所在集合合并
void merge(int a, int b) {
// a和b不在同一集合内才需要合并
if (find(a) != find(b)) {
// 将a元素所在的集合接到b元素所在集合中
p[find(a)] = find(b);
// 将a元素集合个数加到b元素的根节点中
size[find(b)] += size[find(a)];
}
}
void init() {
cin >> n;
for (int i = 0; i < n; i ++) {
p[i] = i;
size[i] = 1; // 初始时每个集合的元素个数都是1
}
}解决并查集问题的关键在于找到其中的并查集模型并选择合适的方式维护并查集的信息
6.堆
堆是一种特殊的完全二叉树，其所有节点都满足一个性质：左右节点的值都小于等于或大于等于当前节点的值。显然根节点永远是整个堆最小或最大的值。
我们这里依然使用数组模拟堆，主要实现如下几个操作：
快速寻找整个集合中的最小值
快速删除整个集合中的最小值
如何删除堆中指定元素
向堆中插入一个数
修改堆中任意一个元素
在使用数组表示二叉树的过程中，如果一个节点的下标是x，则它的左子节点下标为2x，右子节点的下标是2x + 1。
对于实现一个堆，最重要的是实现两个操作：up(x)和down(x)。up(x)表示将 x 下标的节点上浮，down(x)表示将下标为 x 的节点下沉。通过这两个操作我们便可以实现上述五个操作。
代码实现
#include <iostream>
using namespace std;
const int N = 1010;
// h[]表示堆（这里选择小根堆），size表示堆的大小，即元素个数
int h[N];
int n, size;
// 下沉操作
void down(int x) {
int u = x; // u记录该节点及其左右节点三个节点中最小的那个节点
if (2 * x <= size && h[2 * x] < h[u]) u = 2 * x;
if (2 * x + 1 <= size && h[2 * x + 1] < h[u]) u = 2 * x + 1;
if (u != x) {
swap(h[u], h[x]); // 将三个节点中最小的放在父节点
down(u);
}
}
// 上浮操作
void up(int x) {
while (x / 2 && h[x / 2] > h[x]) {
swap(h[x], h[x / 2]);
x /= 2;
}
}
// 返回集合中的元素最小值
int top() {
return h[1];
}
// 删除堆中的最小值，因为我们使用数组来模拟堆，因此删除第一个元素是很复杂的，但是删除最后一个元素很简单，只需要执行size --即可，因此这里删除最小值的思路就是先将头节点和最后一个元素交换，然后执行一遍down操作即可
void pop() {
swap(h[size], h[1]);
size --;
down(1);
}
// 删除堆中指定下标元素，思路和删除最小值一样，不同的是我们需要根据该下标元素和最后一个元素的大小来判断需要上浮还是下沉，由于上浮和下沉的操作只会触发一个，因此down一遍up一遍即可
void remove(int x) {
swap(h[size], h[x]);
size --;
down(x);
up(x);
}
// 向堆中插入一个元素，新来的元素先进入堆底部，然后上浮即可
void push(int v) {
h[++ size] = v;
up(size);
}
// 修改堆中指定下标的元素，修改完之后down一遍up一遍即可
void update(int x, int v) {
h[x] = v;
down(x);
up(x);
}
int main () {
cin >> size;
// 这里下标从1开始是因为选择0作根节点的话，会导致其左子节点(2x)也是0，避免需要特判
for (int i = 1; i <= size; i ++) cin >> h[i];
// 将数组建成堆，时间复杂度为O(n);
/*
建堆原理：所有叶子节点的编号是1~n/2，所有叶子节点已经是堆。
从倒数第二层开始的原因：先处理下层节点，下层的节点的左右子树都已经是合法的堆了，此时执行down操作相当于将该节点也加入堆，通过计算等比数列可以得到该建堆方式的时间复杂度是O(n)。
*/
for (int i = size / 2; i; i --) down(i);
return 0;
}堆的使用场景还是比较多的，在需要持续插入数据并且还要保证集合元素的有序性的场景下基本都会用到堆。
7.c++ STL使用技巧
c++的STL帮助我们实现了很多数据结果，简化了我们代码的编写，虽然我们前面还是用数组实现了很多数据结构，但是大多数情况下我们还是会优选选择STL节省时间，因为STL已经帮助我们完成了很多操作，遇到STL不能完成的操作时，再选择使用数组实现，本节介绍一下STL最常用的几个容器的使用方法。
vector
vector是一种变长数组，即其长度是可变的，当我们需要经常向数组中插入或删除元素时候，使用vector通常比数组更好。
其变长原理是倍增思想，操作系统为某一个进程分配空间时，花费的时间与申请空间大小无关，只与分配次数有关。所以vector为了节省时间采用倍增思想，即减少申请空间的次数，一次性申请较大的空间。例如初始时可能会默认分配32个空间，当该空间被占满时，会申请当前空间两倍的空间（64），然后将原vector中的元素copy到新数组中。因此我们如果向一个空数组中插入n个元素时，大概会申请log(n)次空间和对应次数的copy。因此可以近似看作vector插入元素的时间复杂度是O(1)的，因为 log(n) / n -> 0；
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 初始化vector的几种方式
void init() {
// 初始化一个空vector
vector<int> a;
// 初始化指定容量的vector，其中所有元素都是默认值，int默认值为0
vector<int> a(10);
// 初始化指定容量的vector，所有元素初始化为第二个参数
vector<int> a(10, 3);
// 定义一个二维vector，支持下标访问，如a[3][5];
vector<vector<int>> a;
}
// vector 的常用函数
void demo(vector<int> v) {
// 获取集合元素个数，所有STL容器都有size和empty方法来获取容器元素个数和判断容器是否为空
int sz = v.size();
// 判断集合元素是否为空，等价于 v.size() == 0
bool vector = v.empty();
// 获取集合第一个元素，即v[0]
int first = v.front();
// 获取集合最后一个元素，即v[v.size() - 1]
int last = v.back();
// 向容器最后添加一个元素
v.push_back(1);
// 移除容器最后一个元素
v.pop_back();
// 清空集合元素
v.clear();
}
// 遍历vector的几种方式
void for_each(vector<int> v) {
// 由于vector支持随机访问，因此可以使用下标直接访问容器元素
for (int i = 0; i < v.size() ; i ++) cout << v[i] << endl;
// STL所有容器都支持迭代器访问，begin()获取的是数组第一个元素的迭代器，end()返回是最后一个元素的下一个迭代器
// 迭代器可以简单当成指针来使用，*it即可获取到迭代器指向的元素
for (vector<int>::iterator it = v.begin(); it != v.end(); it ++) cout << *it << endl;
// vector还支持范围for循环遍历
for (auto i : v) cout << i << endl;
}pair<class1, class2>
pair是c++定义的一个二元组，每个pair元素都包含了两个对象，这两个对象不需要是同一个类型的，但是必须符合pair定义时传入的类型。获取pair的第第一个元素使用first，第二个元素使用second。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
pair<int ,int> p1, p2;
// pair的两种初始化方式，可以使用make_pair函数，也可以直接显式声明
p1 = make_pair(4, 2);
p2 = {3, 5};
// pair支持比较运算，first是第一个优先级，first相同再比较second，通常将需要进行比较的元素放在first，不需要比较的元素放在second位置
cout << (p1 < p2) << endl;
}queue
queue就是队列，先进先出的队列
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void dmeo(queue<int> q) {
// 向队尾插入元素
q.push(1);
q.push(3);
q.push(5);
// 获取队头元素
int first = q.front();
// 获取队尾元素
int last = q.back();
// 元素出队
q.pop();
// queue没有clear方法
// q.clear();
}priority_queue
priority_queue是优先队列，就是我们前面实现过的堆，他总是会将队列中的元素按照从大到小进行排序，插入删除元素之后依然保持有序，且队头是最大元素（对应大根堆的根元素），优先队列默认是大根堆。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void demo(priority_queue<int> q) {
// 向优先队列中插入元素
q.push(1);
q.push(2);
q.push(3);
// 获取优先队列的队头元素，即堆的根节点
int root = q.top();
// 根元素出队
q.pop();
// 定义小根堆，优先队列默认大根堆
priority_queue<int, vector<int>, greater<int>> bq;
}stack
stack就是我们前面实现过的栈，满足先进后出原则。
#include <iostream>
#include <alghrithm>
#include <stack>
using namespace std;
void demo(stack<int> s) {
// 向栈顶压入元素
s.push(2);
s.push(4);
// 获取栈顶元素
int top = s.top();
// 栈顶元素出栈
s.pop();
}deque
deque是一个加强版的queue或者vector，或者叫双端队列，其队头队尾都可以插入或弹出元素，可以在容器两端进行插入或删除操作。可以看到deque的功能很强大，但是代价是deque的速度很慢，在对时间要求比较高或数据量卡的比较严格的场景中一般不会选择。
deque支持随机下标访问，如d[3]；
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
void demo(deque<int> d) {
// 向队头或队尾插入元素
d.push_back(3);
d.push_back(4);
d.push_front(8);
// 获取队头元素
int first = d.front();
// 获取队尾元素
int last = d.back();
// 队尾元素出队
d.pop_back();
// 队头元素出队
d.pop_front();
}set/multiset
set是一种无序集合，其最大的特点是元素不能重复，如果插入重复元素那么这个操作就会被忽略，所以set最大的用处是用来去重。set和multiset的区别就是multiset不会自动去重，即可以存储重复元素。set是有序的，支持区间查找
multiset特点（与set区别）：
元素自动排序，默认按值从小到大排序
不能直接修改元素，否则会破坏有序性，想要修改必须先删除再插入元素
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
void demo(set<int> s) {
// 向集合中插入一个元素，时间复杂度O(log n)
s.insert(3);
s.insert(4);
s.insert(7);
// 查找集合中是否存在某个元素，如果存在返回该元素的迭代器(set<int>::iterator)，如果不存在返回end()迭代器
auto it = s.find(3);
// 查找一个元素在集合中出现的次数，在set中只会是0和1，在multi-set中不一定(multi-set允许元素重复)
int count = s.count(3);
// erase传入的参数如果是一个值，那么会删除所有等于该值的元素
// 传入的参数如果是一个迭代器，那么只会删除该迭代器对应的元素
s.erase(3);
s.erase(s.begin());
// 获取第一个大于等于x的元素的迭代器
set<int>::iterator x = s.lower_bound(3);
// 获取第一个大于x的迭代器
set<int>::iterator y = s.upper.bound(6);
// 清空集合，即删除集合中所有元素
s.clear();
}map
map维护了一个pair数组，它可以实现两种不同类型元素之间的映射。map中元素的顺序是按照key的大小升序排列的。
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
// 这里展示操作一个将字符串映射成整数的map，map中的key是唯一的，multimap中的key可以重复
void demo(map<string, int> m) {
// 向map中插入元素，使用insert函数直接插入一个pair元组，也可以直接使用下标
m.insert({"wuxiaoliang", 1});
m["qinxi"] = 2;
m["wangfengshan"] = 3;
// 删除map中指定的元素，经常传入的参数是key，也可以传入迭代器
m.erase("wuxiaoliang");
m.erase(m.begin());
// map最强大的地方在于它可以被当成数组来使用，可以直接通过下标来访问元素，但是不同的是map的访问时间复杂度是O(log n)
cout << m["qinxi"] << endl;
}unordered_xxx
包含unordered_map、unordered_set、unordered_multiset、unordered_multimap，和上面介绍的map、set等容器用法相同，不同的是增删改查的时间复杂度都是O(1)，非常快，而普通的STL容器（如set、map）增删改查时间复杂度都是O(log n)，但是缺点就是不支持lower_bound()\upper_bound()操作，因为其中的元素不会自动按顺序排序了，因为底层采用哈希表实现，顺序是随机的。同时也不支持迭代器的++和--了。
bitset
bitset是位图，再我们需要压位的时候经常会用到。因为我们是用位来存储数据的，而每一位的值只有0和1两个数值，因此适用于研究的对象一般只有两个状态。使用的空间是bool数组的八分之一，因为一个bool变量占一个字节，而我们这里是按位存储的。
我们在使用过程中可以将bitset直接当作一个很大的int来使用，bitset支持~，&，|，^等位运算，也可以进行>>，<<左移右移运算，也可以通过[x]访问对应下标的数字。
常用方法：
count()：返回位图中有多少个1.
any()：返回值为bool类型，当位图中至少有一个1时返回true
none()：判断位图中是否全为0，若为0则返回true。
set()：将位图中所有位设置成1.
set(int k, int v)：将第k位设成v。
reset()：将所有位设成0。
flip()：将所有位取反，等价于~。
flip(int k)：将第k位取反。