普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有*先出的行为特征。我们来说一下C++的STL queue库中优先队列的使用方法。STL默认使用<操作符来确定对象之间的优先级关系，所以如果要使用自定义对象，需要重载<操作符。优先队列有两种，一种是最大优先队列；一种是最小优先队列；每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。
使用头文件queue。
优先队列的操作：
q.empty() 判断是否为空
q.size() 返回队列中元素的个数
q.pop() 删除队首元素，但不返回其值
q.top() 返回具有最高优先级的元素值，但不删除该元素
q.push() 在基于优先级的适当位置插入新元素
默认优先级为最大优先，除此之外共有3种自定义优先级方式。
#include <iostream>
#include <functional>
#include <queue>
#include <vector> using namespace std; struct cmp1//定义比较结构
{
bool operator ()(int &a,int &b)
{
return a>b;//最小值优先
}
}; struct cmp2
{
bool operator ()(int &a,int &b)
{
return a<b;//最大值优先
}
}; struct number1//自定义数据结构
{
int x; bool operator < (const number1 &a) const
{
return x>a.x;//最小值优先
}
}; struct number2
{
int x; bool operator < (const number2 &a) const
{
return x<a.x;//最大值优先
}
}; int main()
{
int n;
cin>>n;
int a[];
number1 num1[];
number2 num2[];
for(int i=;i<n;i++)
{
cin>>a[i];
num1[i].x=a[i];
num2[i].x=a[i];
}
cout<<endl;
priority_queue<int>Q0;//采用默认优先级构造队列
priority_queue<int,vector<int>,cmp1>Q1;//最小值优先
priority_queue<int,vector<int>,cmp2>Q2;//最大值优先
priority_queue<int,vector<int>,greater<int> >Q3;//一定要有空格“> >”,“>>”会被认为错误
priority_queue<int,vector<int>,less<int> >Q4;////最大值优先
priority_queue<number1>Q5; //最小优先级队列
priority_queue<number2>Q6; //最大优先级队列
int i;
for(i=; i<n; i++)
{
Q0.push(a[i]);
Q1.push(a[i]);
Q2.push(a[i]);
Q3.push(a[i]);
Q4.push(a[i]);
}
for(i=; i<n; i++)
Q5.push(num1[i]);
for(i=; i<n; i++)
Q6.push(num2[i]);
//采用默认优先关系 (priority_queue<int>que）
cout<<"Queue0:"<<endl;
while(!Q0.empty())
{
cout<<Q0.top()<<" ";
Q0.pop();
}
cout<<endl<<endl;
//采用结构体自定义优先级方式一 (priority_queue<int,vector<int>,cmp>que)
cout<<"Queue1:"<<endl;
while(!Q1.empty())
{
cout<<Q1.top()<<" ";
Q1.pop();
}
cout<<endl;
cout<<"Queue2:"<<endl;
while(!Q2.empty())
{
cout<<Q2.top()<<" ";
Q2.pop();
}
cout<<endl<<endl;
//采用头文件functional内定义优先级 (priority_queue<int,vector<int>,greater<int>/less<int> >que)
cout<<"Queue3:"<<endl;
while(!Q3.empty())
{
cout<<Q3.top()<<" ";
Q3.pop();
}
cout<<endl;
cout<<"Queue4:"<<endl;
while(!Q4.empty())
{
cout<<Q4.top()<<" ";
Q4.pop();
}
cout<<endl<<endl;
//采用结构体自定义优先级方式二 (priority_queue<number>que)
cout<<"Queue5:"<<endl;
while(!Q5.empty())
{
cout<<Q5.top().x<<" ";
Q5.pop();
}
cout<<endl;
cout<<"Queue6:"<<endl;
while(!Q6.empty())
{
cout<<Q6.top().x<<" ";
Q6.pop();
}
cout<<endl;
return ;
}
运行结果：
