STL中优先队列的使用

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。我们来说一下C++的STL queue库中优先队列的使用方法。STL默认使用<操作符来确定对象之间的优先级关系,所以如果要使用自定义对象,需要重载<操作符。优先队列有两种,一种是最大优先队列;一种是最小优先队列;每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。

使用头文件queue。

优先队列的操作:

q.empty() 判断是否为空

q.size() 返回队列中元素的个数

q.pop() 删除队首元素,但不返回其值

q.top() 返回具有最高优先级的元素值,但不删除该元素

q.push() 在基于优先级的适当位置插入新元素

默认优先级为最大优先,除此之外共有3种自定义优先级方式。

  1 #include <iostream>
  2 #include <functional>
  3 #include <queue>
  4 #include <vector>
  5
  6 using namespace std;
  7
  8 struct cmp1//定义比较结构
  9 {
 10     bool operator ()(int &a,int &b)
 11     {
 12         return a>b;//最小值优先
 13     }
 14 };
 15
 16 struct cmp2
 17 {
 18     bool operator ()(int &a,int &b)
 19     {
 20         return a<b;//最大值优先
 21     }
 22 };
 23
 24 struct number1//自定义数据结构
 25 {
 26     int x;
 27
 28     bool operator < (const number1 &a) const
 29     {
 30         return x>a.x;//最小值优先
 31     }
 32 };
 33
 34 struct number2
 35 {
 36     int x;
 37
 38     bool operator < (const number2 &a) const
 39     {
 40         return x<a.x;//最大值优先
 41     }
 42 };
 43
 44 int main()
 45 {
 46     int n;
 47     cin>>n;
 48     int a[50];
 49     number1 num1[50];
 50     number2 num2[50];
 51     for(int i=0;i<n;i++)
 52     {
 53         cin>>a[i];
 54         num1[i].x=a[i];
 55         num2[i].x=a[i];
 56     }
 57     cout<<endl;
 58     priority_queue<int>Q0;//采用默认优先级构造队列
 59     priority_queue<int,vector<int>,cmp1>Q1;//最小值优先
 60     priority_queue<int,vector<int>,cmp2>Q2;//最大值优先
 61     priority_queue<int,vector<int>,greater<int> >Q3;//一定要有空格“> >”,“>>”会被认为错误
 62     priority_queue<int,vector<int>,less<int> >Q4;////最大值优先
 63     priority_queue<number1>Q5; //最小优先级队列
 64     priority_queue<number2>Q6;  //最大优先级队列
 65     int i;
 66     for(i=0; i<n; i++)
 67     {
 68         Q0.push(a[i]);
 69         Q1.push(a[i]);
 70         Q2.push(a[i]);
 71         Q3.push(a[i]);
 72         Q4.push(a[i]);
 73     }
 74     for(i=0; i<n; i++)
 75         Q5.push(num1[i]);
 76     for(i=0; i<n; i++)
 77         Q6.push(num2[i]);
 78     //采用默认优先关系 (priority_queue<int>que)
 79     cout<<"Queue0:"<<endl;
 80     while(!Q0.empty())
 81     {
 82         cout<<Q0.top()<<" ";
 83         Q0.pop();
 84     }
 85     cout<<endl<<endl;
 86     //采用结构体自定义优先级方式一 (priority_queue<int,vector<int>,cmp>que)
 87     cout<<"Queue1:"<<endl;
 88     while(!Q1.empty())
 89     {
 90         cout<<Q1.top()<<" ";
 91         Q1.pop();
 92     }
 93     cout<<endl;
 94     cout<<"Queue2:"<<endl;
 95     while(!Q2.empty())
 96     {
 97         cout<<Q2.top()<<" ";
 98         Q2.pop();
 99     }
100     cout<<endl<<endl;
101     //采用头文件functional内定义优先级 (priority_queue<int,vector<int>,greater<int>/less<int> >que)
102     cout<<"Queue3:"<<endl;
103     while(!Q3.empty())
104     {
105         cout<<Q3.top()<<" ";
106         Q3.pop();
107     }
108     cout<<endl;
109     cout<<"Queue4:"<<endl;
110     while(!Q4.empty())
111     {
112         cout<<Q4.top()<<" ";
113         Q4.pop();
114     }
115     cout<<endl<<endl;
116     //采用结构体自定义优先级方式二 (priority_queue<number>que)
117     cout<<"Queue5:"<<endl;
118     while(!Q5.empty())
119     {
120         cout<<Q5.top().x<<" ";
121         Q5.pop();
122     }
123     cout<<endl;
124     cout<<"Queue6:"<<endl;
125     while(!Q6.empty())
126     {
127         cout<<Q6.top().x<<" ";
128         Q6.pop();
129     }
130     cout<<endl;
131     return 0;
132 }

运行结果:

时间: 11-18

STL中优先队列的使用的相关文章

STL中优先队列的使用 转

队列的特点是先进先出.通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西.但是优先队列有所不同,它不遵循先进先出的规则,而是根据队列中元素的优先权,优先权最大的先被取出.通常把优先队列比喻成现实生活中的打印.一个打印店里有很多打印机,每台机器的性能不一样,有的打印机打印很快,有的打印机打印速度很慢.当这些打印机陆陆续续打印完自己的任务时进入排队等候状态.如果我这个时候要打印一份文件,我选的不是第一个排队的打印机,而是性能最好,打印最快的打印机. 重点:优先级队列,是要看优先级的,

(转)C++STL中优先队列的使用

原文地址 说到队列,我们首先想到就是先进先出,后进后出:那么何为优先队列呢,在优先队列中,元素被赋予优先级,当访问元素时,具有最高级优先级的元素先被访问.即优先队列具有最高级先出的行为特征. 优先队列在头文件#include <queue>中: 其声明格式为:priority_queue <int> ans;//声明一个名为ans的整形的优先队列 基本操作有: empty( )  //判断一个队列是否为空 pop( )  //删除队顶元素 push( )  //加入一个元素 siz

STL中队列(queue)的使用方法

STL 中队列的使用(queue) 基本操作: push(x) 将x压入队列的末端 pop() 弹出队列的第一个元素(队顶元素),注意此函数并不返回任何值 front() 返回第一个元素(队顶元素) back() 返回最后被压入的元素(队尾元素) empty() 当队列为空时,返回true size() 返回队列的长度 使用方法: 头文件: #include <queue> 声明方法: 1.普通声明 queue<int>q; 2.结构体 struct node { int x, y

STL中栈和队列的使用方法

 STL 中优先队列的使用方法(priority_queu) 基本操作: empty() 如果队列为空返回真 pop() 删除对顶元素 push() 加入一个元素 size() 返回优先队列中拥有的元素个数 top() 返回优先队列对顶元素 在默认的优先队列中,优先级高的先出队.在默认的int型中先出队的为较大的数. 使用方法: 头文件: #include <queue> 声明方式: 1.普通方法: priority_queue<int>q; //通过操作,按照元素从大到小的顺

浅谈C++ STL中的优先队列(priority_queue)

从我以前的博文能看出来,我是一个队列爱好者,很多并不是一定需要用队列实现的算法我也会采用队列实现,主要是由于队列和人的直觉思维的一致性导致的. 今天讲一讲优先队列(priority_queue),实际上,它的本质就是一个heap,我从STL中扒出了它的实现代码,大家可以参考一下. 首先函数在头文件<queue>中,归属于命名空间std,使用的时候需要注意. 队列有两种常用的声明方式: std::priority_queue<T> pq; std::priority_queue<

STL中sort、priority_queue、map、set的自定义比较函数

STL中,sort的默认排序为less,也就是说从小到大排序:priority_queue默认是less,也就说大顶堆:map默认是less,也就说用迭代器迭代的时候默认是小的排在前面:set默认是less,也就是说用迭代器迭代的时候是从小到大排序的. 1.sort #include <stdio.h> #include <algorithm> #include <functional> using namespace std; bool comp(const int&

C++ STL中Map的按Key排序和按Value排序

原文  http://blog.csdn.net/iicy266/article/details/11906189 map是用来存放<key, value>键值对的数据结构,可以很方便快速的根据key查到相应的value.假如存储学生和其成绩(假定不存在重名,当然可以对重名加以区分),我们用map来进行存储就是个不错的选择. 我们这样定义,map<string, int>,其中学生姓名用string类型,作为Key:该学生的成绩用int类型,作为value.这样一来,我们可以根据学

STL中的nth_element()方法的使用

STL中的nth_element()方法的使用 通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置(从0开始,其位置是下标为 n的元素),并且比这个元素小的元素都排在这个元素之前,比这个元素大的元素都排在这个元素之后,但不能保证他们是有序的,下面是这个方法的具体使用方法. 1 #include <iostream> 2 3 #include <algorithm> 4 5 #include <functional>

STL中的Vector相关用法

STL中的Vector相关用法 标准库vector类型使用需要的头文件:#include <vector>. vector 是一个类模板,不是一种数据类型,vector<int>是一种数据类型. Vector的存储空间是连续的,list不是连续存储的. 1. 定义和初始化 vector< typeName > v1; //默认v1为空,故下面的赋值是错误的v1[0]=5;//v2是v1的一个副本,若v1.size()>v2.size()则赋值后v2.size()被