【C++-STL 队列与优先队列用法详解】
1、队列queue
queue 模板类的定义在<queue>头文件中。
与stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类
型，元素类型是必要的，容器类型是可选的，默认为deque 类型。
定义queue 对象的示例代码如下：
queue<int> q1;
queue<double> q2;
queue 的基本操作有：
入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()
【示例代码１】
#include <iostream>#include <queue>
using namespace std;
int main() {
int e,m;
int len;
queue<int> q;
for(int i=0;i<10;i++){
q.push(i);//入队操作，q.push(x); 将x接到队列的末端
}
if(!q.empty()){//q.empty()，当队列空时，返回true
cout<<"队列非空"<<endl;
}
len=q.size();
cout<<"队列长度为："<<len<<endl;
e=q.front();//q.front()，即最早被压入队列的元素
m=q.back();//q.back()，即最后被压入队列的元素
cout<<e<<" "<<m<<endl;
q.pop();//出队操作，q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值
e=q.front();
cout<<e<<endl;
for(int j=0;j<len-1;j++)//循环出队
{
e=q.front();
cout<<e<<" ";
q.pop();
}
cout<<endl;
return 0;
}
２、优先队列
priority_queue<int> p;
【常用函数】
（1）priority_queue::empty
判断队列是否为空（也即是size是否为0），是则返回true，否则返回false。优先队列的此成员函数实际上调用底层容器的同名函数。
（2）priority_queue::size
返回队列中元素的个数。此函数实际上调用底层容器的同名函数。这个函数也可以用于判断队列是否为空。
（3）priority_queue::top
返回队头元素的常引用，队头元素是在所设定的比较关系下最大也即优先级最高的元素。此函数实际上调用底层容器的front函数。
（4）priority_queue::pop
清除队头元素。
（5）priority_queue::push给队列插入元素，新元素会按其优先级被排列到适当位置。
q.size();//返回q里元素个数q.empty();//返回q是否为空，空则返回1，否则返回0q.push(k);//在q的末尾插入kq.pop();//删掉q的第一个元素q.top();//返回q的第一个元素３、less和greater优先队列
优先队列是优先级高的在队首，定义优先级大小的方式是传入一个算子的参数比较a, b两个东西，返回true则a的优先级<b的优先级。
默认是less算子也就是返回a<b，也就是小的优先级也小，而greater算子返回a>b，小的优先级高。
如果是默认的less算子，值大的优先级高，自然默认的优先队列大的先出队。
如果是使用greater算子，值小的优先级高，优先队列小的先出队。
priority_queue <int,vector<int>,less<int> > p;priority_queue <int,vector<int>,greater<int> > q;
【默认less算子－－优先输出大数据】
priority_queue<Type, Container, Functional>模板类有三个模板参数，第一个Type是元素类型，第二个Container为容器类型，第三个Functional是比较算子。其中后两个都可以省略，默认容器为vector，默认算子为less：
less算子，即默认算子为：大的往前排，小的往后排（出队时队列头的元素出队，即大者先出队）。
#include<iostream> #include<queue> using namespace std; int main(){ priority_queue<int> p; p.push(1); p.push(2); p.push(8); p.push(5); p.push(43); while(!q.empty()){ cout<<p.top()<<endl; p.pop(); } return 0; }
【greater算子－－优先输出小数据】
greater算子，即默认算子为：小的往前排，大的往后排（出队时队列头的元素出队，即小者先出队）。
priority_queue<int, vector<int>, greater<int> > p;
#include<iostream> #include<queue> using namespace std; int main(){ priority_queue<int, vector<int>, greater<int> >p; p.push(1); p.push(2); p.push(8); p.push(5); p.push(43); while(!q.empty()){ cout<<p.top()<<endl; p.pop(); } return 0; }
【自定义算子－－重载默认的<符号】
#include <iostream>#include <queue>using namespace std;class T{ public: int x, y, z; T(int a, int b, int c):x(a), y(b), z(c) { }};bool operator < (const T &t1, const T &t2){ return t1.z < t2.z; // 按照z 的顺序来决定t1 和t2 的顺序}int main(){ priority_queue<T> q;//使用模板T的自定义比较方法 q.push(T(4,4,3)); q.push(T(2,2,5)); q.push(T(1,5,4)); q.push(T(3,3,6)); while (!q.empty()) { T t = q.top(); q.pop(); cout << t.x << " " << t.y << " " << t.z << endl; } return 0;}
个人更喜欢把自定义算子写成友元的，写进类里：struct情况类似
为了更好地理解自定义算子，下面给出了两个示例代码，
其中一个为上面例子中使用struct，且把自定义算子写进struct内部的情况
另一个为测试Dijkstra模板中HeapNode的测试代码；
【源代码１】
#include <iostream>#include <queue>using namespace std;struct T{ public: int x, y, z; T(int a, int b, int c):x(a), y(b), z(c) { } friend bool operator < (const T &t1, const T &t2)//自定义less算子，优先输出大数据 { ////z值小的往前排，z值大的往后排（出队时序列尾的元素出队，即z值大者先出队） return t1.z < t2.z; // 按照z 的顺序来决定t1 和t2 的顺序，优先输出z值大的大数据 // return t2.z > t1.z; }};int main(){ priority_queue<T> q;//使用模板T的自定义比较方法 q.push(T(4,4,3)); q.push(T(2,2,5)); q.push(T(1,5,4)); q.push(T(3,3,6)); while (!q.empty()) { T t = q.top(); q.pop(); cout << t.x << " " << t.y << " " << t.z << endl; } return 0;}
【测试结果１】
3 3 62 2 51 5 44 4 3
【源代码２】
#include <iostream>#include <queue>using namespace std;struct HeapNode //Dijkstra算法用到的优先队列的节点{ int d,u; HeapNode(int d,int u):d(d),u(u){} bool operator < (const HeapNode &rhs)const //自定义less算子，优先输出大数据 { //按照d的顺序来决定自身HeapNode和rhs的顺序，优先输出d值大的大数据 //return d > rhs.d; 这两种写法是一样的 return rhs.d<d; //d值小的往前排，d值大的往后排（出队时序列尾的元素出队，即d值大者先出队） }};int main(){ priority_queue<HeapNode> q;//使用模板T的自定义比较方法 q.push(HeapNode(4,3)); q.push(HeapNode(2,5)); q.push(HeapNode(1,4)); q.push(HeapNode(3,6)); while (!q.empty()) { HeapNode n = q.top(); q.pop(); cout << n.d << " " << n.u << endl; } return 0;}
【测试结果２】
1 42 53 64 3