queue
queue就是队列，在STL中是实现了一个先进先出的容器，要使用queue，需要在加上queue这个头文件。
queue的定义，queue<typename> q;其中typename可以为任何类型或容器。
queue的访问，由于队列是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或是通过back()来访问队尾元素。
? ? ? ? queue<`int`> q ;
? ? for(int i=1;i<5;i++){
? ? ? ? q.push(i) ;
? ? }
? ? cout << q.front() << endl ;
? ? cout << q.back() << endl ;
? ? 输出结果：1
4
Queue常用函数
（1） push(),push(x)将x入队，时间复杂度O(1)
（2） front(),访问队首元素,back()访问队尾元素，时间复杂度O(1)。
（3） pop(),令队首元素出队，时间复杂度O(1)。
queue<int> q ;
? ? for(int i=1;i<5;i++){
? ? ? ? q.push(i) ;
? ? }
? ? q.pop() ;
? ? cout << q.front() << endl ;
? ? cout << q.back() << endl ;
输出结果：2
4
（4） empty(),判断队列是否为空，如果是空则返回true，否则返回false。
（5） size(),返回queue内元素的个数，时间复杂度为O(1)。
? ? queue<int> q ;
? ? for(int i=1;i<5;i++){
? ? ? ? q.push(i) ;
? ? }
? ? if(!q.empty()){
? ? ? ? cout << q.size() ;
? ? }
输出结果：4
Queue的常见用途：
? ? 当需要实现广度优先搜索时，可以不用自己手工实现一个队列。在使用front()和pop()函数前，必须使用empty()判断队列是否为空，否则可能因为队空而出现错误。
?
priority_queue
priority_queue又称优先队列，其底层是用堆来进行实现的。在优先队列中，队首的元素一定是当前队列中优先级最高的那一个。C++中的堆默认是大跟堆。
priority_queue的定义，priority_queue<typename> q,typename可以为任意类型的元素。要使用优先队列，应先添加头文件#include[HTML_REMOVED]。
Priority_queue只能通过top()函数来访问队首元素(堆顶元素)，也就是优先级最高的元素。
priority_queue<int> q ;
? ? q.push(3) ;
? ? q.push(1) ;
? ? q.push(5) ;
? ? cout << q.top() << endl ;
输出结果：5
Priority_queue常用函数
（1） push(x)，时间复杂度O(logN),N是堆中元素的个数。
（2） top(),top()可以获得队首元素，时间复杂度O(1)
（3） pop(),令堆顶元素出队，时间复杂度O(logN),其中N是堆中的元素个数。
priority_queue<int> q ;
? ? q.push(3) ;
? ? q.push(1) ;
? ? q.push(5) ;
? ? cout << q.top() << endl ;
? ? q.pop() ;
? ? cout << q.top() << endl ;
输出结果：5
3
（4） empty(),判断队列是否为空，为空返回true，否则返回false。
（5） size(),返回优先队列中元素的个数，时间复杂度O(1)
priority_queue<int> q ;
? ? q.push(3) ;
? ? q.push(1) ;
? ? q.push(5) ;
? ? if(!q.empty()){
? ? ? ? cout << q.size() << endl ;
? ? }
输出结果：3
Priority_queue内元素的优先级设置
? ? 如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍几本数据类型和结构体类型的优先级设置方法。
（1）基本数据类型的优先级设置
基本数据类型的优先级设置方法是类似的，这里用int举例。在C++中默认情况下是大根堆，所以下面两种优先队列的定义是等价的。
Priority_queue<int> q,priority_queue<int,vector<int>,less<int>> q;
可以发现第二种定义方式，后面多了两个参数，一个是vector<int>,另一个是less<int>。其中vector<int>填写的是来承载底层数据结构heap(堆)的容器；第三个参数less<int>则是对第一个参数的比较类，less[HTML_REMOVED]表示数字越大优先级越高，而greater<int>表示数字越小的优先级越大。因此，C++中定义小根堆的方式是,priority_queue<int,vector<int>,greater<int>> q。
priority_queue<int,vector<int>,greater<int>> q ;
? ? q.push(3) ;
? ? q.push(1) ;
? ? q.push(5) ;
? ? cout << q.top() << endl ;
输出结果：1
（2） 结构体的优先级设置
对结构体进行优先级设置有两种方式，第一种是在结构体内部重载小于号“<”，第二种方式是在结构体外部重载“()”,下面对这两种情况分别举个例子来说明
重载小于号“<”
struct fruit{
? ? string name ;
? ? int price ;
? ? friend bool operator < (fruit f1,fruit f2){
? ? ? ? return f1.price > f2.price ;
? ? }
};
priority_queue<fruit> q ;
? ? q.push({"apple",8}) ;
? ? q.push({"orange",7}) ;
? ? q.push({"banana",9}) ;
? ? auto ele = q.top() ;
? ? cout << ele.name << ' ' << ele.price << endl ;
输出结果：orange 7
这种情况下优先队列只能采用第一种定义方式。
重载小括号“()”
struct fruit{
? ? string name ;
? ? int price ;
};
struct cmp{
? ? bool operator () (fruit f1,fruit f2){
? ? ? ? return f1.price > f2.price ;
? ? }
};
int main(){
? ? priority_queue<fruit,vector<fruit>,cmp> q ;
? ? q.push({"apple",8}) ;
? ? q.push({"orange",7}) ;
? ? q.push({"banana",9}) ;
? ? auto ele = q.top() ;
? ? cout << ele.name << ' ' << ele.price << endl ;
? ? return 0 ;
}
输出结果：orange 7
这里的优先队列只能采用第二种定义方式。
小结，即使是基本数据类型或者STL容器，也可以通过同样的方式来定义优先级。
注意：如果结构体内的数据比较庞大，建议使用引用来提高效率，此时比较类的参数中需要加上“const”和“&”，如下所示：
friend bool operator < (const fruit& f1,cosnt fruit& f2){
? ? ? ? return f1.price > f2.price ;
? ? }
bool operator () (const fruit& f1,const fruit& f2){
? ? ? ? return f1.price > f2.price ;
? ? }
Priority_queue的常见用途
? ? Priority_queue可以解决一些贪心问题，也可以对dijkstra进行优化(因为优先队列的本质是堆)，在使用top()函数前