STL的神奇容器之队列

1、队列

在了解优先队列之前，我们先了解一下队列：

想象有一群人，他们排好队在食堂打饭，众所周知，打饭这事儿，还得遵循一个先来后到吧，所以，最早来的人，也是最早出去的，这就是队列

那我们如何定义一个队列呢？

首先，写一个头文件 #include <queue>

或者可以直接使用万能头文件 <bits/stdc++.h>

然后使用初始化命令：queue<int>vis 即初始化了一个新的队列 vis

那队列有说明基本操作呢？

队列和栈类似，有如下五种常见操作：

1. 入队 vis.push(x) 将x压入vis队列中
2. 出队 vis.pop() 将队首的元素弹出
3. 判断队列是否为空 vis.empty() ，如果队列为空，则会返回 true 否则会返回 false，常常和取非（~）符号一起使用
4. 获取队列中元素的数量 vis.size()，会返回队列元素的数量
5. 获取队首元素 vis.front()，这个和栈不一样，栈获取首元素是调用 .top方法

2.优先队列

优先队列和队列类似，但是优先队列和队列又是不同的，他们的数据结构不相同，优先队列更像是一个堆，因而他添加新元素的时候，时间复杂度为 O(n) ，这也使得优先队列相比于队列有一个优势，那就是放入的元素会被自动排序

类似于平衡二叉树（不知道是不是叫这个名字），而因为他的特性而常常被用于贪心算法，详见洛谷训练栏贪心算法内容...几乎全是可以用优先队列解决的问题

那我们如何定义一个优先队列呢？

首先，我们需要一个头文件 <quene> 和队列相同

亦可以使用万能头文件

然后，我们再写入初始化命令

priority_queue <int,vector<int>,greater<int> > q;

注意：“”> >“”不要连在一起

（我的编辑器 clion2019.3.1 推荐使用 priority_queue <int,vector<int>,greater<> > q，但是好像一些编译器无法编译？）

于是，我们便生成了一个新的优先队列

greater-->升序排列

less-->降序排列

刚好与 sort()函数相反

那我们来看看优先队列的基本操作吧！

和队列、栈类似，有如下五种常见操作：

1. 查看优先队列的元素个数q.size()，返回的是一个整数
2. 查看优先队列是否为空 q.empty()，返回的是一个布尔值，为空则返回 true，否则返回 false ，一般和取非符号搭配使用
3. 在队列中插入元素 q.push()，元素会到合适自己的地方去
4. 弹出优先队列中最小的元素q.pop()
5. 返回优先队列中最小的元素 q.top() ，注意与队列的区别

优先队列的自定义cmp函数

要想优先队列使用自定义的排序函数

需要这样定义函数：

typedef long long ll;
struct node{
    int x,y;
    ll sum;
};
bool operator < (const node &s1,const node &s2){
    return s1.sum>s2.sum;
}
priority_queue<node,vector<node> >q;

注意：

自定义函数的写法有多种，本文只列举几种常见的，不代表其他的写法是错误的

例题：
洛谷P1090 合并果子
洛谷P1233 排队接水