STL之queue

发布时间:2024年01月11日

目录

queue队列

常用的deque函数

priority_queue队列(非常重要)

priority_queue常用函数

优先队列修改比较函数的方法

1.仿函数方法

2.自定义比较函数

deque双端队列

常用的函数

例题1

题目描述

输入描述

输出描述

示例输入输出

例题2

题目描述

输入描述

输出描述

输入输出示例

输入

输出


queue队列

queue是一种先进先出(FIFO)的数据结构。

queue提供了一组函数来操作和访问元素,但它的功能相对较简单。

queue的定义和结构如下:

template<class T,class Container = deque<T>>
class queue;

T:表示存储在queue中的元素类型。

Container:表示底层容器的类型,默认为queue。也可以使用其他容器类型,如list。

queue内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。

常用的deque函数

函数??????????????????????? 描述??????????????????????? 时间复杂度

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按照元素的值从大到小进行排序,即最大元素位于队列的前面。

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的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。

priority_queue常用函数

函数??????????????????????? 描述??????????????????????? ????????时间复杂度

push(x)??????????? 在队尾插入到优先队列中????????? O(logn)

pop()?????????? ? ?? 弹出优先队列中的顶部元素????? O(logn)

top()?????????? ?? ? 返回优先队列中的顶部元素?????? O(1)

empty()??????????? 检查优先队列是否为空???????????? O(1)

size()?????????????? 返回优先队列中元素的个数?????? O(1)

优先队列是个十分重要的数据结构

优先队列修改比较函数的方法

1.仿函数方法

struct Compare
{
    bool operator()(int a,int b)
    {
        //自定义的比较函数,按照逆序排列
        return a>b;
    }
};
int main()
{
    std::priority_queue<int,std::vector<int>,Compare>pq;
}

2.自定义比较函数

auto compare = [](int a,int b)
{
    return a>b;
};
std::priority_queue<int,std::vector<int>,decltype(compare)>pq(compare);

deque双端队列

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)

例题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;
}

例题2

题目描述

在一个果园里,多多已经将所有的果子打下来了,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合到一起,消耗的体力等于两堆果子重量之和。可以看出,所有的果子经过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;
}

文章来源:https://blog.csdn.net/weixin_63201442/article/details/135505151
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。