c++ STL 队列:queue 优先队列priority_queue
发布日期:2021-06-21 03:12:42 浏览次数:7 分类:技术文章

本文共 2248 字,大约阅读时间需要 7 分钟。

<quequ队列>

C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。

头文件:#include<queue> 

常用语句: size() 返回元素个数

             empty()如果为空则返回true

             push(k) 在队列末尾插入k

            pop()删除队列的第一个元素

            top()返回队列的第一个元素

            back()返回队列的末尾元素

            front()返回队列顶部元素

特别注意:优先队列priority_queue没有front和back,而只能通过top或pop访问堆顶元素

<priority_queue优先队列>

功能强大在哪里?自动排序。

less和greater优先队列

priority_queue <int,vector<int>,less<int> > p; less队列从大到小排序

priority_queue <int,vector<int>,greater<int> > q; greater队列从小到大排序

exp(我举一个默认优先队列和两种优先队列的例子):

#include<iostream>

#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#define long long LL
using namespace std;
int main()
{
priority_queue<int >q;
q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
while(!q.empty())
{
cout<<q.top()<<" "<<endl;;
q.pop(); 
int k;
priority_queue<int,vector<int>,less<int> >p;
for(int i=0;i<5;i++)
{
cin>>k;
p.push(k);
}
 
while(!p.empty())
{
cout<<p.top()<<" "<<endl;
p.pop();
}
 
priority_queue<int ,vector<int >,greater<int > >pp;
for(int i=0;i<5;i++)
{
cin>>k;
pp.push(k);
}
 
while(!pp.empty())
{
cout<<pp.top()<<" "<<endl;
pp.pop();
}
return 0;

}

输入:

5 2 3 1 4

5 2 3 1 4

输出:

14

12

10

8

6

//默认队列

5

4

3

2

1

//less队列

1

2

3

4

5

//greater队列

为了装13方便,在平时,建议大家写:

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

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

平时如果用从大到小不用后面的vector<int>,less<int>,可能到时候要改成从小到大,

你反而会搞忘怎么写greater<int>,反而得不偿失

优先队列的例题:

牛客网:

链接:https://www.nowcoder.com/acm/contest/121/C

代码:

 /*

 qq:1239198605
 ctgu_yyf
 
3
1 3 4
3 4
5
3 4 5 2 4
3 2 2 2
        */
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#define long long LL
using namespace std;
int a[1005],b[1005];
priority_queue <int ,vector<int>, less<int> >q; 
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++)
cin>>b[i];
int ans=0,c=3;
for(int i=0;i<n-1;i++)
{
q.push(a[i]);
if(ans<b[i])
{
while(c>0&&!q.empty())
{
ans+=q.top();
q.pop();
c--;
if(ans>=b[i])
break;
}
}
ans-=b[i];
if(ans<0)
break;
}
if(ans>=0)
{
q.push(a[n-1]);
while(c>0&&!q.empty())
{
ans+=q.top();
q.pop();
c--;
}
}
if(ans<0)
ans=-1;
cout<<ans<<endl;
return 0;
}

转载地址:https://blog.csdn.net/k_koris/article/details/80353708 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:网络中的A类、B类、C类地址的划分
下一篇:NYOJ 58-最少步数 DFS或者BFS

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年04月08日 08时03分52秒