STL(五)(queue篇)

• 我发现之前一版在电脑上看 常用函数部分 没有问题,由于是手打上去的,在手机上看会发生错位问题,现已将电脑原版 常用函数部分 截图改为图片形式,不会再发生错位问题,非常感谢大家的支持

• ### priority_queue优先队列出现频率非常高,尤为重要(是一定要掌握的数据结构)

1.queue队列

• queue是一种先进先出(FIFO)的数据结构
• queue提供了一组函数来操作和访问元素,但它的功能相对较简单

queue的定义和结构如下:?

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

• T:表示存储在queue中的元素的类型。
• Container:表示底层容器的类型,默认为deque,也可以使用其他容器类型,如list
• queue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素

以下是一些queue的常用函数:

### 这就像一个队伍
           ———————————————————————
pop出去 < ——  1  2  3  4  5  6  < —— push进来
           ———————————————————————

---

2.priority_queue优先序列

• priority_queue与普通的队列不同,priority_queue中的元素是按照一定的优先级进行排序的
• 默认情况下,priority_queue按照元素的值的从大到小进行排序,即最大元素位于队列的前面

priority_queue的定义和结构如下:

template <class T,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的常用函数：

---

### 介绍几种优先队列修改比较函数的方法

1.第一种

#include<bits/stdc++.h>
struct Compare{ //仿函数
	bool operator()(int a,int b){ //()重载 
		//自定义比较函数
		return a>b; //小根堆 
	}
};
int main(){
	std::priority_queue<int,std::vector<int>,Compare> pq;
	return 0;
}

• 默认的是大根堆

2. 第二种

#include<bits/stdc++.h>
auto compare=[](int a,int b){
	//自定义比较函数,按照逆序排列
	return a>b; 
};
int main(){
	std::priority_queue<int,std::vector<int>,decltype(compare)>pq(compare);
	return 0;
}

• ?### 如果优先队列中的元素类型比较简单,可以直接使用greater<T>来修改比较方法

• priority_queue<int,vector<int>,greaterr<int>> pq;
  //std::greater函数对象定义在<functional>头文件中

  ---

  3.deque双端队列

• ?deque(双端队列)是一种容器,它允许在两端进行高效的插入和删除操作
• deque是由一系列连续的存储块(缓冲区)组成的,每个存储块都存储了多个元素
• 这使得deque能够在两端进行快速的插入和删除操作,而不需要移动其他元素

deque的定义和结构如下:

template <class T,class Allocator=allocator<T>>
class deque;

• T:表示存储在deaue中的元素的类型
• Allocator:表示用于分配内存的分配器类型,默认为allocator,deque的内部实现使用了一系列的存储块(缓冲区),每个存储块存储了多个元素,并且通过指针进行连接
• 这种设计使得在两端进行插入和删除操作的时间复杂度为常数时间,即0(1)

###????????“单调队列”将使用双端队列来实现(单纯考察双端队列的并不常见)

以下是一些deque的函数：

• ### 10~12个并不常见?

---

4.例题讲解:

题号:lanqiao OJ 1113?

1.CLZ银行问题

#include<bits/stdc++.h>
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;
    //判断是否为来到窗口
    //IN情况,推入name
		if(op=="IN") {
			string name,q;
			cin>>name>>q;
			if(q=="V"){
				V.push(name);
			}
			else{
				N.push(name);
			} 
		}
    //out情况,弹出name
		else{
			string q;
			cin>>q;
			if(q=="V"){
				V.pop();
			}
			else{
				N.pop();
			}
		} 
	}
	//输出VIP窗口name
	while(V.size()){
		cout<<V.front()<<"\n"; 
		V.pop();
	} 
	//输出普通窗口name
	while(N.size()){
		cout<<N.front()<<"\n"; 
		N.pop();
	} 
	return 0;
}

• ?每次都会弹出,队列虽然是一种线性结构但它是不能遍历的

---

题号:lanqiao OJ 741

2.合并果子

• ### 这里用到一点点贪心
• 1.先将1和2合并就消耗了3点体力,再将3和9合并就消耗了12点体力,共消耗15点体力
• 2.先将2和9合并就消耗了11点体力,再将1和11合并就消耗了12点体力,共消耗23点体力
• 方案1更省体力
• 那么思路就是每次找到一大堆数字中拿出来最小的两个求和,再放回去(使用优先队列)
• ### 这道题注意要开long long(int大概是2e9可能会超范围)

#include<bits/stdc++.h>
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; //类型比较简单,默认是大根堆,要的是小根堆把less直接改成greater
	for(int i=1;i<=n;++i){
		ll x;
		cin>>x;
		pq.push(x);
	} 
	
	ll ans=0;
	while(pq.size()>=2){
		//这里pop出来两个最小的数,也就是小根堆顶部的两个数 
		ll x=pq.top();
		pq.pop();
		ll y=pq.top();
		pq.pop();
		ans+=x+y; //求和
		pq.push(x+y); //把最小数的和push回去 
	} 
	cout<<ans<<"\n"; 
	return 0;
}