队列

队列是符合“先进先出”原则的“公平队列”。
STL队列定义在头文件<queue>中，可以用queue<int>s方式声明一个队列。

队列的声明

用queue<int>q可以声明一个整型队列。

基本操作

1.empty();若队列为空，返回真
2.front();返回第一个元素
3.pop()删除第一个元素
4.push()在队尾加入一个元素
5.size();返回队列中元素个数

优先队列

C++优先队列类似队列，但是在这个数据结构中返回的不是第一个元素，而是优先级最高的元素。

优先队列的声明

一个优先队列声明的基本格式是：
priority_queue<结构类型> 队列名;
比如

priority_queue <int> i;
priority_queue <double> d;

不过，我们最为常用的是这几种.

priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起，“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;

优先队列的基本操作

q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素

优先队列的特性

默认的优先队列是越大的数优先级越高的。如果是自定义类型，则需要重载运算符。
比如，我们定义一个以x为关键字的结构体。

struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
};

这个node结构体有两个成员，它的规则是x小者小。
验证程序

#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
}k;
priority_queue <node> q;
int main()
{
    k.x=10,k.y=100; q.push(k);
    k.x=12,k.y=60; q.push(k);
    k.x=14,k.y=40; q.push(k);
    k.x=6,k.y=80; q.push(k);
    k.x=8,k.y=20; q.push(k);
    while(!q.empty())
    {
        node m=q.top(); q.pop();
        printf("(%d,%d) ",m.x,m.y);
    }
}

输入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node
输出结果是(14,40) (12,60) (10,100) (8,20) (6,80)
它也是按照重载后的小于规则，从大到小排序的。

less和greater优先队列

以int为例子，先来声明

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

第一个优先队列的规则是大的先出，第二个优先队列的规则是小的先出