queue
先进先出容器
这一块在数据结构中详细介绍 不作具体累述
定义
queue<typename> name;
queue的访问
由于队列本身就是一种先进先出的限制性数据结构
只能通过front()来访问队首元素，或是back()来访问队尾元素
queue常用函数
- push()
push(x)将x进行入队 - front()、back()
front()来访问队首元素，或是back()来访问队尾元素 - pop()
pop()令队首元素出队 - empty()
检测queue是否为空，返回true则空，返回false则非空 - size()
返回queue内元素的个数
queue常见用途
当需要实现广度优先搜索，用queue作为代替
在使用front()和pop()函数前，必须用empty()判断队列是否为空
priority_queue
优先队列 其底层是用堆来实现的
在优先队列中，队首元素一定是当前队列中优先级最高的那一个
在任何时候往队列里加入(push)元素，优先队列底层的数据结构堆(heap)会随时调整结构，使得每次的队首元素都是优先级最大的
定义
priority_queue<typename> name;
访问
优先队列没有front()和back()函数，只能通过top()函数来访问队首元素
priority_queue 常用函数
- push() 入队
- top() 获取队首元素
- pop() 令队首元素出队
- empty() 检测优先队列是否为空， true 为空， false 为非空
- size() 优先队列内元素的个数
priority_queue内元素优先级的设置
定义优先队列内元素的优先级是运用好优先队列的关键
- 基本数据类型的优先级设置 int型、double型、char型等可以直接使用的数据类型，优先队列对它们的优先级设置是数字大的优先级越高
//以下两种等价
priority_queue<int> q;
priority_queue<int, vector<int>, less<int> > q;
vector<int>用来承载底层数据结构堆(heap)的容器， 如果前面是double或char 后面就是vector<double>, vector<char>
less<int>表示数字大的优先级越大， great<int>表示数字小的优先级越大，会把最小的元素放在队首
- 结构体的优先设置
struct fruit{
string name;
int price;
friend bool operator < (fruit f1, fruit f2) { //friend 友元 只对 < 进行重载，数学上来说只需要重载小于号
return f1.price < f2.price;
}
};
// priority_queue<fruit> q;
// 如果想以价格低的水果为优先级高，只需要把return中的 f1.price > f2.price 即可
// 与sort 的 cmp 顺序相反
// 可将great<>改成cmp
struct fruit {
string name;
int price;
}f1, f2, f3;
struct cmp{
bool operator() (fruit f1, fruit f2){
return f1.price > f2.price;
}
};
...
priority_queue<fruit, vector<fruit>, cmp> q;
...
当结构体内的数据较大（如出现了字符串或者数组），建议使用引用来提高效率，比较类需要加上"const", "&"
friend bool operator < (const fruit &f1, const fruit &f2){
return f1.price < f2.price;
}
bool operator () (const fruit &f1, const fruit &f2){
return f1.price < f2.price;
}
