MENU

STL的神奇容器之队列

April 4, 2020 • Read: 497 • 算法

1、队列

在了解优先队列之前,我们先了解一下队列:

想象有一群人,他们排好队在食堂打饭,众所周知,打饭这事儿,还得遵循一个先来后到吧,所以,最早来的人,也是最早出去的,这就是队列

那我们如何定义一个队列呢?

首先,写一个头文件 #include <queue>

或者可以直接使用万能头文件 <bits/stdc++.h>

然后使用初始化命令:queue<int>vis 即初始化了一个新的队列 vis

那队列有说明基本操作呢?

队列和栈类似,有如下五种常见操作:

  1. 入队 vis.push(x) 将x压入vis队列中
  2. 出队 vis.pop() 将队首的元素弹出
  3. 判断队列是否为空 vis.empty() ,如果队列为空,则会返回 true 否则会返回 false,常常和取非(~)符号一起使用
  4. 获取队列中元素的数量 vis.size(),会返回队列元素的数量
  5. 获取队首元素 vis.front(),这个和栈不一样,栈获取首元素是调用 .top方法

2.优先队列

优先队列和队列类似,但是优先队列和队列又是不同的,他们的数据结构不相同,优先队列更像是一个堆,因而他添加新元素的时候,时间复杂度为 O(n) ,这也使得优先队列相比于队列有一个优势,那就是放入的元素会被自动排序

类似于平衡二叉树(不知道是不是叫这个名字),而因为他的特性而常常被用于贪心算法,详见洛谷训练栏贪心算法内容...几乎全是可以用优先队列解决的问题

那我们如何定义一个优先队列呢?

首先,我们需要一个头文件 <quene> 和队列相同

亦可以使用万能头文件

然后,我们再写入初始化命令

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

注意:“”> >“”不要连在一起

(我的编辑器 <u>clion2019.3.1</u> 推荐使用 priority_queue <int,vector<int>,greater<> > q,但是好像一些编译器无法编译?)

于是,我们便生成了一个新的优先队列

greater-->升序排列

less-->降序排列

刚好与 sort()函数相反

那我们来看看优先队列的基本操作吧!

和队列、栈类似,有如下五种常见操作:

  1. 查看优先队列的元素个数q.size(),返回的是一个整数
  2. 查看优先队列是否为空 q.empty(),返回的是一个布尔值,为空则返回 true,否则返回 false ,一般和取非符号搭配使用
  3. 在队列中插入元素 q.push(),元素会到合适自己的地方去
  4. 弹出优先队列中最小的元素q.pop()
  5. 返回优先队列中最小的元素 q.top() ,注意与队列的区别

优先队列的自定义cmp函数

要想优先队列使用自定义的排序函数

需要这样定义函数:

typedef long long ll;
struct node{
    int x,y;
    ll sum;
};
bool operator < (const node &s1,const node &s2){
    return s1.sum>s2.sum;
}
priority_queue<node,vector<node> >q;

注意:

自定义函数的写法有多种,本文只列举几种常见的,不代表其他的写法是错误的

例题:
洛谷P1090 合并果子
洛谷P1233 排队接水

Last Modified: September 11, 2020
Archives Tip
QR Code for this page
Tipping QR Code