- 外文名
- queue
- 属 于
- 编程
- 类 别
- 计算机
- 中文名
- 队列
- 性 质
- 科学
-
queue
2020-08-18 17:07:04queue简介 queue是队列容器,是一种“先进先出”的容器。 queue是简单地装饰deque容器而成为另外的一种容器。 queue没有迭代器,不允许遍历。 queue采用模板类实现,queue对象的默认构造形式:queue<T> ...queue简介
- queue是队列容器,是一种“先进先出”的容器。
- queue是简单地装饰deque容器而成为另外的一种容器。
- queue没有迭代器,不允许遍历。
queue采用模板类实现,queue对象的默认构造形式:queue<T> queT; 如:
queue<int> queInt; //一个存放int的queue容器。
queue<float> queFloat; //一个存放float的queue容器。
queue<string> queString; //一个存放string的queue容器。
queue的push()与pop()方法 queue.push(elem); //往队尾添加元素 queue.pop(); //从队头移除第一个元素 queue<int> queInt; queInt.push(1);queInt.push(3); queInt.push(5);queInt.push(7); queInt.push(9);queInt.pop(); queInt.pop(); 此时queInt存放的元素是5,7,9 queue对象的拷贝构造与赋值 queue(const queue &que); //拷贝构造函数 queue& operator=(const queue &que); //重载等号操作符 queue<int> queIntA; queIntA.push(1); queIntA.push(3); queIntA.push(5); queIntA.push(7); queIntA.push(9); queue<int> queIntB(queIntA); //拷贝构造 queue<int> queIntC; queIntC = queIntA; //赋值
queue的数据存取
- queue.back(); //返回最后一个元素
- queue.front(); //返回第一个元素
queue<int> queIntA; queIntA.push(1); queIntA.push(3); queIntA.push(5); queIntA.push(7); queIntA.push(9); int iFront = queIntA.front(); //1 int iBack = queIntA.back(); //9 queIntA.front() = 11; //11 queIntA.back() = 19; //19
queue的大小
- queue.empty(); //判断队列是否为空
- queue.size(); //返回队列的大小
queue<int> queIntA; queIntA.push(1); queIntA.push(3); queIntA.push(5); queIntA.push(7); if (!queIntA.empty()) { int iSize = queIntA.size(); //4 }
-
Queue
2018-02-26 17:37:08QueuePython3.5中,队列是线程间最常用的交换数据的形式。Queue模块是提供队列操作的模块1、Python Queue模块详解2、 python3学习笔记:多进程分布式小例子3、理解Queue队列中join()与task_done()的关系...Queue
Python3.5中,队列是线程间最常用的交换数据的形式。Queue模块是提供队列操作的模块
-
c++优先队列(priority_queue)用法详解
2018-04-14 10:58:07queue>优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的 定义:priority_queue<Type, Container, Functional> Type 就是数据类型,...既然是队列那么先要包含头文件
#include <queue>
, 他和queue
不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的
和队列基本操作相同:
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
定义:
priority_queue<Type, Container, Functional>
Type 就是数据类型,Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆
一般是://升序队列 priority_queue <int,vector<int>,greater<int> > q; //降序队列 priority_queue <int,vector<int>,less<int> >q; //greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)
- 基本类型例子:
#include<iostream> #include <queue> using namespace std; int main() { //对于基础类型 默认是大顶堆 priority_queue<int> a; //等同于 priority_queue<int, vector<int>, less<int> > a; // 这里一定要有空格,不然成了右移运算符↓ priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆 priority_queue<string> b; for (int i = 0; i < 5; i++) { a.push(i); c.push(i); } while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; while (!c.empty()) { cout << c.top() << ' '; c.pop(); } cout << endl; b.push("abc"); b.push("abcd"); b.push("cbd"); while (!b.empty()) { cout << b.top() << ' '; b.pop(); } cout << endl; return 0; }
输出
4 3 2 1 0 0 1 2 3 4 cbd abcd abc
2.pari的比较,先比较第一个元素,第一个相等比较第二个
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<pair<int, int> > a; pair<int, int> b(1, 2); pair<int, int> c(1, 3); pair<int, int> d(2, 5); a.push(d); a.push(c); a.push(b); while (!a.empty()) { cout << a.top().first << ' ' << a.top().second << '\n'; a.pop(); } }
输出
2 5 1 3 1 2
3.对于自定义类型
#include <iostream> #include <queue> using namespace std; //方法1 struct tmp1 //运算符重载< { int x; tmp1(int a) {x = a;} bool operator<(const tmp1& a) const { return x < a.x; //大顶堆 } }; //方法2 struct tmp2 //重写仿函数 { bool operator() (tmp1 a, tmp1 b) { return a.x < b.x; //大顶堆 } }; int main() { tmp1 a(1); tmp1 b(2); tmp1 c(3); priority_queue<tmp1> d; d.push(b); d.push(c); d.push(a); while (!d.empty()) { cout << d.top().x << '\n'; d.pop(); } cout << endl; priority_queue<tmp1, vector<tmp1>, tmp2> f; f.push(c); f.push(b); f.push(a); while (!f.empty()) { cout << f.top().x << '\n'; f.pop(); } }
输出
3 2 1 3 2 1
-
【原创】优先队列 priority_queue 详解
2017-04-25 17:50:01c++ 的 stl 里的 优先队列 priority_queue 的声明和基本操作优先队列
重要通知!!!!!!!!!!!!!
优先队列没有back()操作!!!!!
误人子弟Crloss已经自毙了!!!!!
同时更正了一些小问题。
——2018.11.03引入
优先队列是一种特殊的队列,在学习堆排序的时候就有所了解,点“击”查看。
那么优先队列是什么呢?
说白了,就是一种功能强大的队列。如果不太清楚队列,可以看看我这篇博客。它的功能强大在哪里呢?
四个字:自动排序。优先队列的头文件&&声明
首先,你需要
#include<queue> using namespace std;//这个不是头文件但我也不晓得叫什么专业定语反正要和头文件一起开就是了!
这两个
头文件东西。using namespace std; 这句话,代表,使用一个叫做“std”的namespace,namespace里面封存了一系列东西,比方说奇异的数据结构和奇异的函数。当打开了namespace以后,就跟打开了头文件的本质是一样的,都是可以直接用它里面封存的函数。
不同之处在什么地方?就是不开namespace的使用,在你想用的(以std为例)函数面前加上“std::”即可。
例如,std::sort(a+1,a+1+N); 之类的。
感谢 @龙征天 的评论指点!其次,一个优先队列声明的基本格式是:
priority_queue<结构类型> 队列名;
比如:priority_queue <int> i; priority_queue <double> d;
不过,我们最为常用的是这几种:
priority_queue <node> q; //node是一个结构体 //结构体里重载了‘<’小于符号 priority_queue <int,vector<int>,greater<int> > q; //不需要#include<vector>头文件 //注意后面两个“>”不要写在一起,“>>”是右移运算符 priority_queue <int,vector<int>,less<int> >q;
我们将在下文来讲讲这几种声明方式的不同。
优先队列的基本操作
与队列的基本操作如出一辙。
如果想要了解请点击这里,看关于队列的介绍。以一个名为q的优先队列为例。
q.size();//返回q里元素个数 q.empty();//返回q是否为空,空则返回1,否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素
优先队列的特性
上文已经说过了,自动排序。
怎么个排法呢?
在这里介绍一下:默认的优先队列(非结构体结构)
priority_queue <int> q;
这样的优先队列是怎样的?让我们写程序验证一下。
#include<cstdio> #include<queue> using namespace std; priority_queue <int> q; int main() { q.push(10),q.push(8),q.push(12),q.push(14),q.push(6); while(!q.empty()) printf("%d ",q.top()),q.pop(); }
程序大意就是在这个优先队列里依次插入10、8、12、14、6,再输出。
结果是什么呢?14 12 10 8 6
也就是说,它是按从大到小排序的!默认的优先队列(结构体,重载小于)
先看看这个结构体是什么。
struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } };
这个node结构体有两个成员,x和y,它的小于规则是x小者小。
再来看看验证程序:#include<cstdio> #include<queue> using namespace std; struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } }k; priority_queue <node> q; int main() { k.x=10,k.y=100; q.push(k); k.x=12,k.y=60; q.push(k); k.x=14,k.y=40; q.push(k); k.x=6,k.y=80; q.push(k); k.x=8,k.y=20; q.push(k); while(!q.empty()) { node m=q.top(); q.pop(); printf("(%d,%d) ",m.x,m.y); } }
程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。
再来看看它的输出:(14,40) (12,60) (10,100) (8,20) (6,80)
它也是按照重载后的小于规则,从大到小排序的。
↑好好康康这句话!(摘眼镜)less和greater优先队列
还是以int为例,先来声明:
priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q;
再次强调:“
>
”不要两个拼在一起。话不多说,上程序和结果:
#include<cstdio> #include<queue> using namespace std; priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q; int a[5]={10,12,14,6,8}; int main() { for(int i=0;i<5;i++) p.push(a[i]),q.push(a[i]); printf("less<int>:"); while(!p.empty()) printf("%d ",p.top()),p.pop(); printf("\ngreater<int>:"); while(!q.empty()) printf("%d ",q.top()),q.pop(); }
结果:
less<int>:14 12 10 8 6 greater<int>:6 8 10 12 14
所以,我们可以知道,less是从大到小,greater是从小到大。
作个总结
为了
装13方便,在平时,建议大家写:priority_queue<int,vector<int>,less<int> >q; priority_queue<int,vector<int>,greater<int> >q;
平时如果用从大到小不用后面的
vector<int>,less<int>
,可能到时候要改成从小到大,你反而会搞忘怎么写greater<int>
,反而得不偿失。另一种排序方法
有可能遇到这种情况:
心情不好不想用重载小于一个结构体的优先队列,要按照各种不一样的规则排序。当然,如果不是优先队列而是数组,我们就会多写几个bool函数塞到sort里面来改变它的小于规则,比如:
struct node { int fir,sec; }arr[2030]; bool cmp1(node x,node y) { return x.fir<y.fir; //当一个node x的fir值小于另一个node y的fir值时,称x<y } bool cmp2(node x,node y) { return x.sec<y.sec; //当一个node x的sec值小于另一个node y的sec值时,称x<y } bool cmp3(node x,node y) { return x.fir+x.sec<y.fir+y.sec; //当一个node x的fri值和sec值的和小于另一个node y的fir值和sec值的和时,称x<y } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d %d",&arr[i].fir,&arr[i].sec); puts("\n--------------------"); sort(arr+1,arr+1+n,cmp1); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec); } puts("\n--------------------"); sort(arr+1,arr+1+n,cmp2); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec); } puts("\n--------------------"); sort(arr+1,arr+1+n,cmp3); for(int i=1;i<=n;i++) printf("%d. {%d %d}\n",i,arr[i].fir,arr[i].sec); }
因为不是整体所以就省略了验证环节(也就是说上面那个代码的正确性不保证)
但是优先队列可没有sort那么灵活想用什么作小于规则用什么作小于规则,它只会用一个固定的小于规则。
所以如果想把一个队列按不同的方式优先,就要:#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; struct node { int fir,sec; void Read() {scanf("%d %d",&fir,&sec);} }input; struct cmp1 { bool operator () (const node &x,const node &y) const { return x.fir<y.fir; } };//当一个node x的fir值小于另一个node y的fir值时,称x<y struct cmp2 { bool operator () (const node &x,const node &y) const { return x.sec<y.sec; } };//当一个node x的sec值小于另一个node y的sec值时,称x<y struct cmp3 { bool operator () (const node &x,const node &y) const { return x.fir+x.sec<y.fir+y.sec; } };//当一个node x的fri值和sec值的和小于另一个node y的fir值和sec值的和时,称x<y priority_queue<node,vector<node>,cmp1> q1; priority_queue<node,vector<node>,cmp2> q2; priority_queue<node,vector<node>,cmp3> q3; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) input.Read(),q1.push(input),q2.push(input),q3.push(input); printf("\ncmp1:\n"); while(!q1.empty()) printf("(%d,%d) ",q1.top().fir,q1.top().sec),q1.pop(); printf("\n\ncmp2:\n"); while(!q2.empty()) printf("(%d,%d) ",q2.top().fir,q2.top().sec),q2.pop(); printf("\n\ncmp3:\n"); while(!q3.empty()) printf("(%d,%d) ",q3.top().fir,q3.top().sec),q3.pop(); }
读入:
7 1 2 2 1 6 9 9 6 -100 100 -500 20 4000 -3000
输出:
cmp1: (4000,-3000) (9,6) (6,9) (2,1) (1,2) (-100,100) (-500,20) cmp2: (-100,100) (-500,20) (6,9) (9,6) (1,2) (2,1) (4000,-3000) cmp3: (4000,-3000) (6,9) (9,6) (1,2) (2,1) (-100,100) (-500,20)
我们可以发现啊,
priority_queue <int,vector<int>,less<int> > p;
的那个less<int>
其实就代表这个优先队列的小于规则,所以把这个换成cmp1
就会有上述效果,desu~
所以说,所以说啦,一定要记得写全称!
搞定!总结
优先队列到此就作了个小结。
其实不管是队列,还是优先队列,都不仅仅只有我讲的这些,还有更多可以探索。应该入门级别都讲得差不多了,之后呢,在下就期待诸君的表演了。
学,无止境。UPD (2019.10.31)
可持久化阅读博客,点此查看历史版本
现在你百度“优先队列”搜到的第一条,就是我UPD之前的历史版本了。
其实是此人不动声色地把我标题里的“【原创】”拿掉了,挂了个转载就转走了。话说在很久以前的很长一段时间,我啊一直是百度“优先队列”的第一条。不晓得是因为我改了名还是我修正了没有back操作的错误还是我的自定义栏目被csdn拿掉了,就刷下去了。
当然看到我的历史版本很快顶替了这个位置我还是很高兴呢,我也把人们被那篇博客的称赞看作是对我自己的称赞,更喜的是一位哥们在那篇博客里评论了一句之后又点进超链接到我的博客下面又评论了一句一模一样的的。真的xswl。
我之所以要写这几句话只是因为我最近太高兴了,几乎感觉不到压力,压力很小呢,就爱把正能量发泄出去。真的没有任何批评指责的意思,你看我这句话都没加粗。
做人理应宽容大度,别人打你左脸还要伸右脸,亲亲,这边建议您把我的那些个超链接链接到的东西都转载过去哦。反正是小事。
一个小人物因为自己的小成就被另一个小人物取代了而在这里无意义的悻悻,传播正能量。
xswlxswlxswl,wxslwxslwxsl。 -
Queue 详解
2018-06-07 21:46:39(讲得很详细,刚好在用queue,不熟,找到这篇博文好好学习了下。) https://www.cnblogs.com/lemon-flm/p/7877898.html Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构 Queue接口与List、Set... -
springboot整合rabbitmq,动态创建queue和监听queue
2018-03-30 15:46:501、pom.xml添加如下依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter</artifactId&...... -
queue.queue是什么
2018-10-15 15:55:09Queue Queue是python标准库中的线程安全的队列(FIFO)实现,提供了一个适用于多线程编程的先进先出的数据结构,即队列,用来在生产者和消费者线程之间的信息传递 基本FIFO队列 class Queue.Queue(maxsize=0) ... -
Python: queue.Queue
2018-11-23 15:43:53class Queue.Queue(maxsize=0):FIFO队列的构造函数(先进先出)。maxsize是一个整数,用于设置可放在队列中的项数上限。一旦达到此大小,插入将阻塞,直到使用队列项为止。如果maxsize小于或者等于0,则队列大小为.... -
Python 队列(Queue)用法
2019-04-10 19:10:36一、队列(Queue) Python的Queue模块中提供了同步的、线程安全的队列类,包括FIFO(先入先出)队列Queue,LIFO(后入先出)队列LifoQueue,和优先级队列PriorityQueue。这些队列都实现了锁原语,能够在多线程中直接... -
Gstreamer-element-queue/queue2/multiqueue
2019-01-10 09:50:32queue/queue2/multiqueue queue: queue只有一个src pad和一个sink pad,会在src pad上创建一个线程,减少src和sink的关联。queue有三个限制参数buffers、bytes、time(单位纳秒ns)。有最大... -
C++ queue(STL queue)
2019-10-28 17:29:52只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素,只能从头部移除元素。 许多程序都使用了 queue 容器。queue 容器可以用来表示超市的结账队列或服务器上等待执行的数据库... -
Py之Queue:python库之Queue的简介、安装、使用方法之详细攻略
2018-05-29 21:03:29Py之Queue:python库之Queue的简介、安装、使用方法之详细攻略 目录 Queue的简介 Queue的安装 Queue的使用方法 1、queue模块有三种队列及构造函数 Queue的简介 python标准库中带有一个Queue模块,... -
queue函数
2018-05-23 16:49:22如果要用queue函数要在开始输入#include<queue>queue<类型>名称。比如:定义queue<string>a queue<int>a struct node{ int a[4];};queue<node&... -
Python multiprocessing.Queue() 和 queue.Queue区别
2018-07-11 20:03:43Queue.Queue是进程内非阻塞队列。multiprocess.Queue是跨进程通信队列。多进程前者是各自私有,后者是各子进程共有。 -
multiprocessing.Queue()和queue.Queue()的区别
2018-04-02 17:26:36from multiprocessing import Pool, Process, Queue # from Queue import Queuequeue.Queue是进程内非阻塞队列,multiprocess.Queue是跨进程通信队列。1.from queue import Queue 这个是普通的队列模式,类似于普通... -
C++ queue
2019-04-02 21:56:26queue符合先进后出(First In Last Out,FILO),不提供遍历功能 构造函数 方法 描述 queue queT; 默认构造形式: queue(const queue &que); 拷贝构造函数 API 方法 描述... -
RabbitMQ queue
2017-01-06 15:02:10amqp queue -
Python3中multiprocessing.Queue()和queue.Queue()的区别
2019-03-03 16:36:50from multiprocessing import Pool, Process, Queue from Queue import Queue Queue.Queue是进程内非阻塞队列,multiprocess.Queue是跨进程通信队列。 1.from queue import Queue 这个是普通的队列模式,类似于... -
Pycharm中Queue与queue的使用区别
2019-06-13 17:27:19Pycharm中Queue与queue的使用区别 1.Queue或者queue是python自带的标准库,直接import就可以 2.python 2.x 中第一个字母大写是: import Queue q = Queue.Queue(maxsize = 10) 3.python 3.x 中第一个字母小写是: ... -
C++ 队列queue的用法
2016-07-15 16:52:06头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。 C++队列Queue是一种容器适配器,它给予程序员一种先进先出(F... -
Queue.queue 退出与阻塞
2016-06-03 09:50:22Queue 默认的也是阻塞方式读取数据,设置属性,改变成非阻塞方式。 或者用 Queue.get_nowait()或 Queue.pet_nowait() 代替。 -
Queue的一般用法
2014-05-09 14:45:24Queue -
queue:queue清空的方法?
2018-09-14 22:18:34C++中的queue自身是不支持clear操作的,但是双端队列deque是支持clear操作的。 方法一 直接用空的队列对象赋值 queue<int> q1; // process // ... q1 = queue<int>(); 方法二 ... -
Python import Queue ImportError: No module named 'Queue'
2018-10-07 22:50:14python3 中引入Queue 会报出这个问题 python3 中这样引入 import queue python2 中这样引入 import Queue 为了兼容 可以这样 import sys if sys.version > '3': import queue as Queue else: import ... -
Erlang Queue
2013-06-02 17:17:27Queue 是Erlang的队列,它的内部实现充分考虑到了效率,值得学习.估计"如何用链表高效实现Queue"这个也会在面试题目中频繁出现吧.queue模块中除了len/1, join/2, split/2, filter/2 and member/2复杂度是O(n)之外... -
Python Queue、multiprocessing.Queue、multiprocessing.Manager().Queue()三种消息队列的区别
2020-04-12 23:09:13import Queue 用于线程间的消息队列 from multiprocessing import Queue 用于子进程间的消息队列。但是用于线程间好像也没有问题 from multiprocessing import Manager,Pool msg_queue = Manager.Queue() 用于进程池...
-
memcache的源代码.zip感觉自己水平高的,可以下载研究研究
-
基于MVC的宠物商店前台加后台
-
关于博途不同版本同时安装在同一台电脑的问题.docx
-
【2021】UI自动化测试Selenium3
-
thinkphp5.1博客后台实战视频
-
swiftScan-master.zip
-
Mysql求留存率(困难)——游戏玩法分析Ⅲ
-
旅游门户网站01
-
(新)备战2021软考系统集成基础知识套餐
-
python学习之pandas
-
第2章 Python如何运行程序(可选,但推荐看一下)
-
pyechart数据可视化
-
KKB :Spring IOC如何优化原代码(指的是service-dao-bean模式)
-
CAD坐标标注智能插件
-
(新)备战2021软考网络工程师历年真题培训套餐
-
转行做IT-第2章 HTML入门及高级应用
-
智联万物,京东IoT技术创新与实践
-
LeetCode 必刷题
-
three.js入门速成
-
flask写的接口处理跨域问题