蓝桥杯集训之STL和algorithm

配套视频

蓝桥杯集训之Algorithm库函数: https://www.bilibili.com/video/BV1ia411B7U2

蓝桥杯集训之STL演示：https://www.bilibili.com/video/BV1Z3411v72U

蓝桥杯集训之Algorithm库函数：https://www.bilibili.com/video/BV1Y34y1z7uX

一、 STL部分 1.1 queue （FIFO） 1.1.1 头文件

使用该容器需要#include头文件

1.1.2 定义

queue que;//这个int可以更换成自己想要的数据

1.1.3 基本操作

1.que.size() 返回队列元素数量

2.que.empty() 返回队列是否为空(空返回true,反之false)

3.que.push() 加入队列

4.que.pop() 出队

5.que.front() 返回队首

6.que.back() 返回队尾

1.1.4 应用

队列广泛引用在广度优先搜索（BFS）里、约瑟夫环问题等

1.2 stack （FILO） 1.2.1 头文件

使用该容器需要#include头文件

1.2.2 定义

stack S;

1.2.3 基本操作

1.S.size() 返回栈里元素个数

2.S.empty() 返回栈是否为空(空返回true,反之false)

3.S.push() 压入一个元素进栈

4.S.pop() 从栈弹出一个元素

5.S.top() 返回栈顶

1.2.4 应用

逆波兰表达式等

1.3 priority_queue 1.3.1 头文件

使用该容器需要#include头文件

1.3.2 定义

priority_queue que;

默认大顶堆，通过添加greater就能获得小顶堆

但是要注意这里如果想使用自定义的数据结构的话，需要手写排序规则：

eg：

struct Node  //运算符重载
{
    int a,b;
    int val;
    bool friend operator y.val;
    }
};
priority_queue que;

1.3.3 基本操作

1.que.size() 返回队列元素数量

2.que.empty() 返回队列是否为空(空返回true,反之false)

3.que.push() 加入队列

4.que.pop() 出队

5.que.top() 返回队首

1.3.4 应用

应用在一些贪心的算法上面，优化dijkstra复杂度等

1.3.5 重载代码

pq.push(item):添加元素 O(logn)
pq.pop():使优先级最高的出队O(logn)
pq.top():获取优先级最高的元素O(1)
pq.size():获取元素个数O(1)
pq.empty():是否为空O(1)
优先队列的定义：
priority_queue q1; //默认从大到小，大顶堆 
priority_queue q2; //降序队列，大顶堆 
priority_queue q3; //升序队列，小顶堆
对于结构体定义：
struct T1{//法一 强烈推荐 
	int x,y;
	friend bool operator