C++标准模板库(STL)之队列及优先队列

一

queue翻译为队列,在STL中实现了一个先进先出的容器.

1.queue的定义

queue<typename> name;

2.queue容器内元素的访问

队列本身就是一种先进先出的限制性数据结构,因此在STL中只能通过front()来访问队首元素,或是通过back()来访问队尾元素.

3.queue常用函数

(1) push()

push(x)将x进行入队

(2) front(), back()

front()和back()可以分别获得队首元素和队尾元素.

(3) pop()

pop()令队首元素出队

(4) empty()

empty()检查queue是否为空,空则返回true,非空则返回false.

(5) size()

size()返回queue内元素的个数.

应用举例:

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	queue<int> q;
	for(int i=1;i<+9;i++)
        q.push(i);        //入队 
    while(!q.empty())
    {
    	cout<<"当前队列里有"<<q.size()<<"个元素,队首为 "<<q.front()<<",队尾为 "<<q.back()<<endl;
    	q.pop();          //出队 
		 
	}
	cout<<"测试结束!!!";
    return 0;
}

二

priority_queue又称为优先队列，其底层是用堆来进行实现的.

优先队列中，队首元素一定是当前队列中优先级最高的那个.

1. priority_queue的定义

priority_queue<typename> name;

2. priority_queue容器内元素的访问

只能通过top()函数来访问队首元素，也就是优先级最高的元素.

3.priority_queue常用函数

(1) push()

push(x)将x进行入队

(2) top()

top()可以分别获得队首元素.

(3) pop()

pop()令队首元素出队

(4) empty()

empty()检查优先队列是否为空,空则返回true，非空则返回false.

(5) size()

size()返回优先队列内元素的个数.

4.优先队列内元素优先级的设置

(1)基本数据类型的优先级设置

默认的优先级设置是数字大或字典序大的优先级高.下面两种优先队列的定义是等价的:

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

可以看出,第二种定义方式的尖括号内多了两个参数，其中vector<int>填写的是来承载底层数据结构堆(heap)的容器，如果第一个参数是double型或char型，则此处只需要填写vector<double>或vector<char>；而第三个参数则是对第一个参数的比较类，less<int>表示数字大的优先级大，而greater<int> 表示数字小的优先级大.

(2)结构体的优先级设置

举一个水果的例子

#方法一:通过友元函数重载小于号(第一种定义方式定义优先队列)

#include <iostream>
#include <queue>
using namespace std;
struct fruit
{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2)
	{
		return f1.price>f2.price;
	}
};
int main()
{
    priority_queue<fruit> q;
    fruit f[]={"桃子",3,"梨子",4,"苹果",1,"杏子",2};
	for(int i=0;i<=3;i++)
       q.push(f[i]);
	cout<<q.top().name<<" "<<q.top().price<<endl; 
    return 0;
}

#方法二:cmp函数实现(第二种定义方式定义优先队列)

#include <iostream>
#include <queue>
using namespace std;
struct fruit
{
	string name;
	int price;
};
struct cmp
{
	bool operator () (fruit f1,fruit f2) 
	{
	return  f1.price>f2.price;
    }
};
int main()
{
    priority_queue<fruit,vector<fruit>,cmp> q;
    fruit f[]={"桃子",3,"梨子",4,"苹果",1,"杏子",2};
	for(int i=0;i<=3;i++)
       q.push(f[i]);
	cout<<q.top().name<<" "<<q.top().price<<endl; 
    return 0;
}