Processing math: 16%
NOIP学习小站
西安交通大学附属中学航天学校

容器适配器之队列queue和优先队列priority_queue

一、queue简介

前面已经介绍过队列(线性表——队列),队列(queue)是一种典型的FIFO(first in first out,先进先出)线性表结构,STL中有专门的queue容器。其实queue是一种容器适配器,默认情况下内部是基于deque容器实现的。

要使用queue,需要先包引入头文件#include<queue>。queue同样也有和stack类似的push()、pop()成员函数。区别在于,queue的push()发生在队尾,pop()发生在队首。此外,还有front()返回队首元素,back()返回队尾元素。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> q;
cout<<q.size()<<endl; //队列元素数量
q.push(1); //入队
q.push(2); //入队
cout<<q.front()<<endl; //取队首元素
cout<<q.back()<<endl; //取队尾元素
q.pop(); //出队
cout<<q.front()<<endl;
cout<<q.back()<<endl;
for(int i=1;i<=10;i++) q.push(i);
//所有元素出队
while(!(q.empty())){
cout<<q.front()<<" ";
q.pop();
}
cout<<endl;
//判断队列是否为空
if(q.empty()) cout<<"empty"<<endl;
return 0;
}
#include<iostream> #include<queue> using namespace std; int main() { queue<int> q; cout<<q.size()<<endl; //队列元素数量 q.push(1); //入队 q.push(2); //入队 cout<<q.front()<<endl; //取队首元素 cout<<q.back()<<endl; //取队尾元素 q.pop(); //出队 cout<<q.front()<<endl; cout<<q.back()<<endl; for(int i=1;i<=10;i++) q.push(i); //所有元素出队 while(!(q.empty())){ cout<<q.front()<<" "; q.pop(); } cout<<endl; //判断队列是否为空 if(q.empty()) cout<<"empty"<<endl; return 0; }
#include<iostream>
#include<queue>
using namespace std;
int main()
{
	queue<int> q;
	cout<<q.size()<<endl;		 //队列元素数量 
	
	q.push(1);					//入队 
	q.push(2);					//入队 
	cout<<q.front()<<endl;		//取队首元素 
	cout<<q.back()<<endl;		 //取队尾元素 
	
	q.pop();					  //出队 
	cout<<q.front()<<endl;
	cout<<q.back()<<endl;
	
	for(int i=1;i<=10;i++) q.push(i);
	
	//所有元素出队 
	while(!(q.empty())){
		cout<<q.front()<<" ";
		q.pop();
	}
	cout<<endl;
	
	//判断队列是否为空 
	if(q.empty()) cout<<"empty"<<endl;
	return 0;
}

因为队列LIFO的特点,常将queue用于广度优先搜索。

二、经典例题

1.约瑟夫问题

可以用队列解决约瑟夫问题,每次数数,就是前m-1个人从队首依次来到队尾,然后第m个人出队:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) q.push(i);
while(!(q.empty())){
//m-1人从队首来到队尾(取出队首元素入队,队首元素出队)
for(int i=1;i<m;i++){
q.push(q.front());
q.pop();
}
//输出队首元素
cout<<q.front()<<" ";
//第m个人(正好在队首)出队
q.pop();
}
return 0;
}
#include<iostream> #include<queue> using namespace std; int main() { queue<int> q; int n,m; cin>>n>>m; for(int i=1;i<=n;i++) q.push(i); while(!(q.empty())){ //m-1人从队首来到队尾(取出队首元素入队,队首元素出队) for(int i=1;i<m;i++){ q.push(q.front()); q.pop(); } //输出队首元素 cout<<q.front()<<" "; //第m个人(正好在队首)出队 q.pop(); } return 0; }
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    queue<int> q;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) q.push(i);
    while(!(q.empty())){
    	//m-1人从队首来到队尾(取出队首元素入队,队首元素出队) 
    	for(int i=1;i<m;i++){
			q.push(q.front());
			q.pop();
		}
    	//输出队首元素 
    	cout<<q.front()<<" ";
    	//第m个人(正好在队首)出队 
    	q.pop();
	}
    return 0;
}

2.Blah数集

大数学家高斯小时候偶然间发现一种有趣的自然数集合 Blah,对于以 a 为基的集合 Ba 定义如下:
(1) a 是集合 Ba 的基,且 a 是 Ba 的第一个元素;
(2) 如果 x 在集合 Ba 中,则 2x+1 和 3x+1 也都在集合 Ba 中;
(3) 没有其他元素在集合 Ba 中了。
现在提供 a 和 N,小高斯想知道如果将集合 Ba 中元素按照升序排列,第 N 个元素会是多少?

【思路】对于最开始的 a,产生的两个新元素放入到队列中,从队列里取出最小的数再产生新的两个元素,……这样的话,要考虑如何从队列中找最小的元素,并且还要避免产生重复的数,这两个问题都不容易处理。其实可以用三个队列,队列 q 用来记录产生的数,队列 q2 用来记录 2x+1 规则产生的数,队列 q3 用来记录 3x+1 规则产生的数,取 q 的队头元素记为 x,那么将 2x+1 入队列 q2,将 3x+1 入队列 q3,然后将 q2 队首和 q3 队首较小的那个数入队列 q,这样就可以保证 q 中的元素一直从小到大排列,并且不会出现重复。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int a,n;
cin>>a>>n;
queue<long long> q2,q3,q;
q.push(a);
int i;
for(i=1;i<n;i++){
q2.push(q.front()*2+1); //2x+1 入队q2
q3.push(q.front()*3+1); //3x+1 入队q3
q.pop();
//q新入队元素 是 q2和q3较小的队首元素
if (q2.front() < q3.front()) //q2队首元素小
q.push(q2.front()),q2.pop();
else if (q2.front() > q3.front()) //q3队首元素小
q.push(q3.front()),q3.pop();
else //q2和q3队首元素相等
q.push(q2.front()),q2.pop(),q3.pop(); //q2,q3均出队,避免重复
}
cout<<q.front()<<endl;
return 0;
}
#include<iostream> #include<queue> using namespace std; int main() { int a,n; cin>>a>>n; queue<long long> q2,q3,q; q.push(a); int i; for(i=1;i<n;i++){ q2.push(q.front()*2+1); //2x+1 入队q2 q3.push(q.front()*3+1); //3x+1 入队q3 q.pop(); //q新入队元素 是 q2和q3较小的队首元素 if (q2.front() < q3.front()) //q2队首元素小 q.push(q2.front()),q2.pop(); else if (q2.front() > q3.front()) //q3队首元素小 q.push(q3.front()),q3.pop(); else //q2和q3队首元素相等 q.push(q2.front()),q2.pop(),q3.pop(); //q2,q3均出队,避免重复 } cout<<q.front()<<endl; return 0; }
#include<iostream>
#include<queue>
using namespace std; 
int main()
{
	int a,n;
	cin>>a>>n; 
	queue<long long> q2,q3,q; 
	q.push(a);
	int i;
	for(i=1;i<n;i++){
		q2.push(q.front()*2+1);		//2x+1 入队q2 
		q3.push(q.front()*3+1);		//3x+1 入队q3
		q.pop();
		
		//q新入队元素 是 q2和q3较小的队首元素 
		if (q2.front() < q3.front())		//q2队首元素小 
			q.push(q2.front()),q2.pop();
		else if (q2.front() > q3.front())   //q3队首元素小
			q.push(q3.front()),q3.pop();
		else								//q2和q3队首元素相等 
			q.push(q2.front()),q2.pop(),q3.pop();   //q2,q3均出队,避免重复
	}
	cout<<q.front()<<endl;
	return 0;
}

不用队列也能解决问题,请分析体会下面的程序:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
long long p[1000100]; //存储结果
long long blah(int a,int n){
p[1] = a; //第一个元素
//t是新元素记录到数组的位置
//t1是记录x*2+1规则产生新元素的x所在下标
//t2是记录x*3+1规则产生新元素的x所在下标
int t = 1,t1 = 1,t2 = 1; //三个下标
while(t<n){
long long x = p[t1]*2+1; //一种是乘2加1
long long y = p[t2]*3+1; //另外一种是乘3加1
//x,y只有3种情况
if(x>y)
p[++t] = y,t2++;
else if(y>x)
p[++t] = x,t1++;
else
p[++t] = x,t1++,t2++;
}
return p[t];
}
int main(){
int a,n;
cin>>a>>n;
cout<<blah(a,n)<<endl;
return 0;
}
#include<iostream> using namespace std; long long p[1000100]; //存储结果 long long blah(int a,int n){ p[1] = a; //第一个元素 //t是新元素记录到数组的位置 //t1是记录x*2+1规则产生新元素的x所在下标 //t2是记录x*3+1规则产生新元素的x所在下标 int t = 1,t1 = 1,t2 = 1; //三个下标 while(t<n){ long long x = p[t1]*2+1; //一种是乘2加1 long long y = p[t2]*3+1; //另外一种是乘3加1 //x,y只有3种情况 if(x>y) p[++t] = y,t2++; else if(y>x) p[++t] = x,t1++; else p[++t] = x,t1++,t2++; } return p[t]; } int main(){ int a,n; cin>>a>>n; cout<<blah(a,n)<<endl; return 0; }
#include<iostream>
using namespace std;
long long p[1000100];		//存储结果 
long long blah(int a,int n){
	p[1] = a;				//第一个元素
	//t是新元素记录到数组的位置
	//t1是记录x*2+1规则产生新元素的x所在下标
	//t2是记录x*3+1规则产生新元素的x所在下标 
	int t = 1,t1 = 1,t2 = 1;	//三个下标
	while(t<n){
		long long x = p[t1]*2+1;		//一种是乘2加1
		long long y = p[t2]*3+1;		//另外一种是乘3加1
		//x,y只有3种情况
		if(x>y)
			p[++t] = y,t2++;
		else if(y>x)
			p[++t] = x,t1++;
		else
			p[++t] = x,t1++,t2++;
	}
	return p[t];
}
int main(){
	int a,n;
	cin>>a>>n;
	cout<<blah(a,n)<<endl;
	return 0;
}

3.广度优先搜索

可以查看这里:

三、优先队列priority_queue

普通的队列queue是一种先进先出的数据结构,元素在队列尾追加,而从队首删除。在优先队列priority_queue中,元素被赋予优先级——当访问元素时,具有最高优先级的元素最先访问或者删除。优先队列具有最高级先出(first in largest out)的行为特征。priority_queue可以用vector或deque实现,默认情况下用vector实现。

priority_queue默认的元素比较器是less <T>。也就是说,在默认情况下,要放入priority_queue的元素必须是能用“<”运算符进行比较的(如果是结构体可以重载<运算符),而且priority _queue保证以下条件总是成立:对于队首的元素 x 和任意非队首的元素 y,表达式 x<y 必为false

priority_queue是使用“堆排序”技术实现的,其内部并非完全有序,但却能确保最优元素总在队首。因此,priority_queue特别适用于“不停地在一堆元素中取走最优的元素”这种情况。priority_queue插入和删除元素的复杂度都是O(log(n))

1.申明优先队列

要使用priority_queue,同样需要引入头文件#include<queue>。简单地申明优先队列时,其内部是基于vector实现的,默认是大根堆,也就是队首元素比其他元素都大:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
priority_queue<int> pq; //申明优先队列,默认是大根堆(队首元素比其他元素都大)
priority_queue<int> pq; //申明优先队列,默认是大根堆(队首元素比其他元素都大)
priority_queue<int> pq;   //申明优先队列,默认是大根堆(队首元素比其他元素都大)

也可以指定优先队列的内部实现容器,还可以提供一个比较函数(仿函数)来确定优先队列的优先规则:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//优先队列内部使用vector实现,比较函数是less<int>(优先队列默认比较函数就是less<T>),这里是大根堆
priority_queue<int,vector<int>,less<int> > pq1;
//优先队列内部使用vector实现,比较函数是greater<int>,这里是小根堆(队首元素比其他元素都小)
priority_queue<int,vector<int>,greater<int> > pq2;
//优先队列内部使用vector实现,比较函数是less<int>(优先队列默认比较函数就是less<T>),这里是大根堆 priority_queue<int,vector<int>,less<int> > pq1; //优先队列内部使用vector实现,比较函数是greater<int>,这里是小根堆(队首元素比其他元素都小) priority_queue<int,vector<int>,greater<int> > pq2;
//优先队列内部使用vector实现,比较函数是less<int>(优先队列默认比较函数就是less<T>),这里是大根堆
priority_queue<int,vector<int>,less<int> > pq1;
//优先队列内部使用vector实现,比较函数是greater<int>,这里是小根堆(队首元素比其他元素都小)
priority_queue<int,vector<int>,greater<int> > pq2;

上面使用的less<T>greater<T>都是C++内置的两个“仿函数”,其实可以通过结构体来自定义仿函数:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Point{
double x,y;
Point(double x,double y){
this->x = x;
this->y = y;
}
};
//通过结构体自定义类似于less<T>和greater<T>的仿函数
struct cmp{
bool operator ()(const Point &a,const Point &b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
};
int main()
{
priority_queue<Point,vector<Point>,cmp> pq;
return 0;
}
#include<iostream> #include<vector> #include<queue> using namespace std; struct Point{ double x,y; Point(double x,double y){ this->x = x; this->y = y; } }; //通过结构体自定义类似于less<T>和greater<T>的仿函数 struct cmp{ bool operator ()(const Point &a,const Point &b){ return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y; } }; int main() { priority_queue<Point,vector<Point>,cmp> pq; return 0; }
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Point{
    double x,y;
    Point(double x,double y){
        this->x = x;
        this->y = y;
    }
};
//通过结构体自定义类似于less<T>和greater<T>的仿函数 
struct cmp{
	bool operator ()(const Point &a,const Point &b){
		return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
	}
}; 
int main()
{
    priority_queue<Point,vector<Point>,cmp> pq; 
    return 0;
}

使用仿函数定义优先队列大根堆/小根堆区别方法:如果仿函数用来排序是升序排序,那么用来作为优先队列的优先级规则时是大根堆(队首是排序结果的最大元素),和排序结果正好相反

对于元素是结构体的情况,还可以重载结构体运算符来申明优先队列:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Point{
double x,y;
Point(double x,double y){
this->x = x;
this->y = y;
}
void print() const{
cout<<"("<<x<<","<<y<<")";
}
};
//比较规则:坐标点到原点的距离
bool operator < (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
bool operator > (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
//return b<a; 亦可
}
int main()
{
//大根堆,需要使用到Point结构体重载的<运算
priority_queue<Point> pq1;
//priority_queue<Point,vector<Point>,less<Point> > pq1;
//小根堆,需要使用到Point结构体重载的>运算
priority_queue<Point,vector<Point>,greater<Point> > pq2;
double arrxy[5] = {1.2,2.3,3.4,4.5,5.6};
for(int i=0;i<5;i++){
pq1.push(Point(arrxy[i],arrxy[i]));
pq2.push(Point(arrxy[i],arrxy[i]));
pq1.top().print();
cout<<" ";
pq2.top().print();
cout<<endl;
}
return 0;
}
#include<iostream> #include<vector> #include<queue> using namespace std; struct Point{ double x,y; Point(double x,double y){ this->x = x; this->y = y; } void print() const{ cout<<"("<<x<<","<<y<<")"; } }; //比较规则:坐标点到原点的距离 bool operator < (const Point &a,const Point &b){ return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y; } bool operator > (const Point &a,const Point &b){ return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y; //return b<a; 亦可 } int main() { //大根堆,需要使用到Point结构体重载的<运算 priority_queue<Point> pq1; //priority_queue<Point,vector<Point>,less<Point> > pq1; //小根堆,需要使用到Point结构体重载的>运算 priority_queue<Point,vector<Point>,greater<Point> > pq2; double arrxy[5] = {1.2,2.3,3.4,4.5,5.6}; for(int i=0;i<5;i++){ pq1.push(Point(arrxy[i],arrxy[i])); pq2.push(Point(arrxy[i],arrxy[i])); pq1.top().print(); cout<<" "; pq2.top().print(); cout<<endl; } return 0; }
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Point{
    double x,y;
    Point(double x,double y){
        this->x = x;
        this->y = y;
    }
    void print() const{
		cout<<"("<<x<<","<<y<<")";
	}
};
//比较规则:坐标点到原点的距离 
bool operator < (const Point &a,const Point &b){
	return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
bool operator > (const Point &a,const Point &b){
	return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
	//return b<a; 亦可
}
int main()
{
    //大根堆,需要使用到Point结构体重载的<运算 
    priority_queue<Point> pq1;
    //priority_queue<Point,vector<Point>,less<Point> > pq1;
    
    //小根堆,需要使用到Point结构体重载的>运算
    priority_queue<Point,vector<Point>,greater<Point> > pq2;
	 
    double arrxy[5] = {1.2,2.3,3.4,4.5,5.6};
    
    for(int i=0;i<5;i++){
    	pq1.push(Point(arrxy[i],arrxy[i]));
    	pq2.push(Point(arrxy[i],arrxy[i]));
    	
    	pq1.top().print();
    	cout<<" ";
    	
    	pq2.top().print();
    	cout<<endl;
	}
    return 0;
}

priority_queue的成员函数和queue类似,不过没有front()和back(),取队首元素的成员函数是top()。

2.经典例题:priority queue练习题

问题见NOI OpenJudge:OpenJudge - 3345:priority queue练习题

可以申明两个优先队列,分别是大根堆和小根堆,每次操作过程中所有元素入队后再取队首元素并出队,可知每次取出的队首元素就是题目要求的优先级最高和最低的元素。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Num{
int n; //数字本身
int k; //质因数数量
Num(int n){
this->n = n;
k = 0;
int i = 2,t = n;
while(t!=1){
if(t%i==0){
if(i!=n) k++;
while(t%i==0) t/=i;
}
i++;
}
}
};
bool operator < (const Num &a,const Num &b){
if(a.k==b.k) return a.n<b.n;
return a.k<b.k;
}
bool operator > (const Num &a,const Num &b){
return b<a;
}
priority_queue<Num> pq1;
priority_queue<Num, vector<Num>, greater<Num> > pq2;
int main()
{
int n,m;
cin>>n;
//n次操作
while(n--){
//每次10个元素入队
for(int i=1;i<=10;i++){
cin>>m;
pq1.push(Num(m));
pq2.push(Num(m));
}
//取队首元素输出
cout<<pq1.top().n<<" "<<pq2.top().n<<endl;
//出队
pq1.pop();
pq2.pop();
}
return 0;
}
#include<iostream> #include<vector> #include<queue> using namespace std; struct Num{ int n; //数字本身 int k; //质因数数量 Num(int n){ this->n = n; k = 0; int i = 2,t = n; while(t!=1){ if(t%i==0){ if(i!=n) k++; while(t%i==0) t/=i; } i++; } } }; bool operator < (const Num &a,const Num &b){ if(a.k==b.k) return a.n<b.n; return a.k<b.k; } bool operator > (const Num &a,const Num &b){ return b<a; } priority_queue<Num> pq1; priority_queue<Num, vector<Num>, greater<Num> > pq2; int main() { int n,m; cin>>n; //n次操作 while(n--){ //每次10个元素入队 for(int i=1;i<=10;i++){ cin>>m; pq1.push(Num(m)); pq2.push(Num(m)); } //取队首元素输出 cout<<pq1.top().n<<" "<<pq2.top().n<<endl; //出队 pq1.pop(); pq2.pop(); } return 0; }
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Num{
	int n;		//数字本身 
	int k;		//质因数数量 
	Num(int n){
		this->n = n;
		k = 0;
		int i = 2,t = n;
		while(t!=1){
			if(t%i==0){
				if(i!=n) k++;
				while(t%i==0) t/=i;
			}
			i++;
		}
	}
};
bool operator < (const Num &a,const Num &b){
	if(a.k==b.k) return a.n<b.n;
	return a.k<b.k;
}
bool operator > (const Num &a,const Num &b){
	return b<a;
}
priority_queue<Num> pq1;
priority_queue<Num, vector<Num>, greater<Num> > pq2;
int main()
{
	int n,m;
	cin>>n;
	//n次操作 
	while(n--){
		//每次10个元素入队 
		for(int i=1;i<=10;i++){
			cin>>m;
			pq1.push(Num(m));
			pq2.push(Num(m));
		}
		//取队首元素输出 
		cout<<pq1.top().n<<" "<<pq2.top().n<<endl;
		//出队 
		pq1.pop();
		pq2.pop();
	}
	return 0;
}

登录

注册