哈,我豁出去了,没想到会这没早地写优先队列。
说优先队列,其实算不上是队列,更像是一个数组,每一次,你给他sort()一下,完全违背了FIFO(先进先出)的规则。而且这个sort,还是默认大到小的。
那我就来说说吧。
1.头文件,跟基本队列一样
#include<queue>
或者说,你可以一把捞所有的头文件,真是方便
#include<bits/stdc++.h>
我的话,更倾向于后者,懒人懒办法。
2.定义
给个格式,找了我半天
priority_queue<Type, Container, Functional>;
看不懂也没事,我也有些看不懂。
正常人一点的,是这样的
priority_queue<类型,两个奇葩(说不清)> 名字;
再说明白一点,就是——
升序:
priority_queue<类型,vector<类型>,greater<类型> >名字;
降序:
priority_queue<类型,vector<类型>,less<类型> >名字;
注意两个"> >"之间的空格,别打成">>"了。
给个样例——
升序队列:
priority_queue <int,vector<int>,greater<int> > q;
降序队列:
priority_queue <int,vector<int>, less<int> >q;
3.然后是操作
跟普通的FIFO特像,如果读过我的前一篇文章,你会很明白为什么是“特像”,却不是“一样”。
先给张表,这是优先队列的
top() 访问队头元素
empty() 队列是否为空
size() 返回队列内元素个数
push() 插入元素到队尾 (并排序)
pop() 弹出队头元素
再来看看我之前的那次,这是普通队列的——
empty() 如果队列为空返回true,否则返回false
size() 返回队列中元素的个数
pop() 删除队列首元素但不返回其值
front() 返回队首元素的值,但不删除该元素
back() 返回队列尾元素的值,但不删除该元素
push() 在队尾压入新元素
区别就在这儿
一个是
top() 返回队首元素的值
一个是
front() 返回队首元素的值
back() 返回队列尾元素的值
优先队列,没有求队尾元素值的函数。
样例嘛
q.top() 访问队头元素
q.empty() 队列是否为空
q.size() 返回队列内元素个数
q.push() 插入元素到队尾 (并排序)
q.pop() 弹出队头元素
加个q就行了,打字的同志说,简单的很!
4.好勒,总结一下
优先队列,不是FIFO,而是FI,“best”O,简单的很,会了queue,priority也不怕。