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

STL queue && priority_queue