目录
queue是一种先进先出(FIFO)的数据结构。
queue提供了一组函数来操作和访问元素,但它的功能相对较简单。
queue的定义和结构如下:
template<class T,class Container = deque<T>>
class queue;
T:表示存储在queue中的元素类型。
Container:表示底层容器的类型,默认为queue。也可以使用其他容器类型,如list。
queue内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。
函数??????????????????????? 描述??????????????????????? 时间复杂度
push(x)??????????? 在队尾插入元素x???????? ??????? O(1)
pop()?????????? ? ?? 弹出队尾元素????????????????????? O(1)
front()????????????? 返回队首元素?????????????????????? O(1)
back()????????????? 返回队尾元素????????????? ? ?????? O(1)
empty()??????????? 检查队列是否为空??????????????? O(1)
size()?????????????? 返回队列中元素的个数???????? O(1)
priority_queue与普通队列不同,priority_queue中的元素是按照一定的优先级进行排序的。默认情况下,priority_queue按照元素的值从大到小进行排序,即最大元素位于队列的前面。
priority_queue的定义和结构如下:
template<class T,class Container = vector<T>>,
class Compare = less<typename Container::value_type>>
class priority_queue;
T:表示存储在priority_queue中的元素类型。
Container:表示底层容器的类型,默认为vector。也可以使用其他容器类型,如deque。
Compare:表示元素之间的比较函数对象的类型,默认为less,即按照元素的值进行比较。
priority_queue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。
函数??????????????????????? 描述??????????????????????? ????????时间复杂度
push(x)??????????? 在队尾插入到优先队列中????????? O(logn)
pop()?????????? ? ?? 弹出优先队列中的顶部元素????? O(logn)
top()?????????? ?? ? 返回优先队列中的顶部元素?????? O(1)
empty()??????????? 检查优先队列是否为空???????????? O(1)
size()?????????????? 返回优先队列中元素的个数?????? O(1)
优先队列是个十分重要的数据结构
struct Compare
{
bool operator()(int a,int b)
{
//自定义的比较函数,按照逆序排列
return a>b;
}
};
int main()
{
std::priority_queue<int,std::vector<int>,Compare>pq;
}
auto compare = [](int a,int b)
{
return a>b;
};
std::priority_queue<int,std::vector<int>,decltype(compare)>pq(compare);
deque(双端队列)是一种容器,它允许在两端进行高效的插入和删除操作。deque是由一系列连续的存储块(缓冲区)组成的,每个存储块都存储了多个元素。这使得deque能够在两端进行快速的插入和删除操作,而不需要移动其他元素。
函数??????????????????????????????? 描述??????????????????????????????? 时间复杂度
push_back(x)??????????? 在尾部插入元素x???????? ??????? 平摊O(1)
push_front(x) ???????? ?? 在头部插入元素x ??????????????? 平摊O(1)
pop_front()???????????????? 弹出头部元素?????????????????????? O(1)
pop_back()?????????????? ? 弹出尾部元素 ???????????? ? ?????? O(1)
front()????????????? ???????? ? 返回头部元素?????????????????????? O(1)
back()??????????????????? ? ?? 返回尾部元素????????????? ? ?????? O(1)
empty()??????????? 检查deque是否为空??????????????????????? O(1)
size()?????????????? 返回deque中元素的个数???????????????? O(1)
clear()??????????? 清空deque中的所有元素 ?????? ? ? ?????? O(1)
ZZB银行有两个窗口,VIP窗口和普通窗口,VIP用户进入VIP窗口排队,剩下的进入普通窗口排队。现有M次操作,操作有四种类型如下:
IN name v:表示一名叫name的用户到VIP窗口排队
OUT v:表示VIP窗口队头的用户离开排队
IN name N:表明一名叫name的用户到普通窗口排队
OUT N:表明普通窗口队头的用户离开排队
求M次操作后VIP窗口队列和普通队列中的姓名
第一行是一个整数M(1<=M<=1000),表示一共有M次操作,
第二行到第M+1行输入操作格式如下:
IN name v
OUT v
IN name N
OUT N
输出M次操作后VIP窗口队列和普通队列中的姓名(从头到尾),先输出VIP窗口队列后输出普通窗口队列。
输入:
5
IN xiaoming N
IN adel V
IN LAOZHAO N
OUT N
IN CLZ V
输出:
adel
CLZ
LAOZHAO
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int m; cin >> m;
queue<string>V, N;
while (m--)
{
string op; cin >> op;
if (op == "IN")
{
string name,q; cin >> name>>q;
if (q == "V")
{
V.push(name);
}
else
{
N.push(name);
}
}
else
{
string q; cin >> q;
if (q == "V")
{
V.pop();
}
else
{
N.pop();
}
}
}
while (V.size())
{
cout << V.front() << endl;
V.pop();
}
while (N.size())
{
cout << N.front() << endl;
N.pop();
}
return 0;
}
在一个果园里,多多已经将所有的果子打下来了,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合到一起,消耗的体力等于两堆果子重量之和。可以看出,所有的果子经过n-1次合并之后,就剩下一堆了,多多在合并果子是总共消耗的体力等于每次合并消耗体力之和。
设计合并次序方案,获取体力消耗最小值。
输入两行
第一行是一个整数n(1<=n<=10^4),表示果子的种类数。
第二行包含n个整数,表示每种果子的数量。
输出一个整数,体力最小值,输入数据保证这个值小于2^33.
3
1 2 9
15
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
using LL = long long;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
priority_queue<LL, vector<LL>,greater<LL>> pq;
for (int i = 1; i <= n; i++)
{
LL x; cin >> x;
pq.push(x);
}
LL ans = 0;
while (pq.size() >= 2)
{
LL x = pq.top(); pq.pop();
LL y = pq.top(); pq.pop();
ans += x + y;
pq.push(x + y);
}
cout << ans << endl;
return 0;
}