STL—queue(队列) 详解

首先,在STL中 queue 和 stack 其实并不叫容器(container)，而是叫适配器(adapter)，他们是对容器的再封装.

队列queue：

队列，简称对，是一种操作受限的线性表。限制为：只允许在队首删除（出队），队尾插入（入队)，其特点是先进先出。在STL中，queue作为一种适配器，其底层容器一般为deque(双端队列)和list(双向链表)，其中deque为默认底层容器。

头文件

#include<queue>

创建queue对象：

模板：queue<数据类型，容器类型> q;

数据类型：可以是int、double等基本类型，也可以是自定义的结构体。
容器类型：一般为deque（双端列队）或者list（双向链表），可省略，省略时以deque为默认容器。
q：队列名。

声明代码如下：

queue<int> q;  //使用默认的双端队列为底层容器创建一个空的queue队列对象q，数据元素为int类型。

queue<int> q[20];  //规定队列元素数量

queue<int,list<int>> q1;
queue<int,list<int>> q2(q1);
//复制构造函数(queue(const queue&))，用一个queue对象创建新的queue对象。 
//利用queue对象q1，创建一个以双向链表为底层容器的queue对象q2

基本操作：

在文章结尾处有代码示例

q.push(x);      //入队，将元素 x 从队尾插入（尾插法）
q.pop();        //出队，删除对首元素，并返回其值
q.size();       //返回队中元素个数
q.front();      //返回对首元素
q.back();       //返回队尾元素
q.empty();      //判断是否为空（空返回 1，非空返回 0）

优先队列priority_queue

优先队列是一种会按照默认或自定义的优先级进行自动排序的队列，其特点是优先级高的元素排在队首，低的排在队尾。头文件#include< queue > 中提供了两种可直接引用的优先规则（排序规则）：greater、less；其中，less是默认优先规则，表示数字大的优先级大（字符型用ASCLL码比较），放在队首；greater表示数字小的优先级大，放在队首。

头文件

#include<queue>

创建priority_queue对象：

模板：priority_queue< 数据类型，容器类型，优先规则> pq;

数据类型：可以是int、double等基本类型，也可以是自定义的结构体。
容器类型：一般为deque（双端列表）、vector（向量容器），可省略，省略时以vector为默认容器。
pq：优先队列名。

声明代码如下：

默认声明：

priority_queue<int> pq;

手动声明：

priority_queue<int,vector<int>,less<int> > pq;   //以less为排列规则（大顶堆，表示顶堆元素比其他都大）
priority_queue<int,vector<int>,greater<int> > pq; //以greater为排列规则（小顶堆，表示顶堆元素比其他都小）

利用重载操作符定义优先级（其实也是递增和递减两种排序规则）

非结构体

struct lei
{       
    bool operator () (const int &a,const int &b)
    {           
        return a>b;   //相当于greater，a<b则相当于less      
    }
}；
另：
struct lei
{   
    bool operator()(int a,int b)
    {
        return a>b;   //相当于greater，（小顶堆）；a<b相当于less
    }
}；
引用方式：priority_queue<int,vector<int>,lei> pq;

结构体：

struct lei
{
    int n;   
    double m;   
    friend bool operator < (lei a,lei b)
    {      
        return a.n>b.n;   //以n做优先级比较，相当于greater
    }
}a,b；
另：
struct lei
{   
     int n;   
     double m;  
     bool operator < (const lei &a) const
     {
          return a.n>n;    //以n做优先级比较，相当于greater
     }
}a;
另：
struct lei
{
     int n;
     double m;
}a,b;
struct mop
{
     feiend bool operator<(lei a,lei b)
     {
     return a.n>b.n
     }
}；
引用方式：priority_queue<lei > pq;

struct lei
{   
    int n;
    double m;
}a,b;
struct mop
{    
    bool operator ()(lei a,lei b)    
    {       
        return a.n>b.n;//相当于greater(小顶堆)    
    }
};
引用方式：priority_queue<lei,vector<lei>,mop> pq;

多重优先级定义

struct lei
{
    int x,y,z;
};
struct begin
{
    bool operator () (const lei &a,const lei &b)const
    {
        if(a.x!=b.x) return a.x<b.x;
        else
        {
            if(a.y!=b.y) return a.y<b.y;
            else
            {
                return a.z<b.z;
            }
        }
     }
};
//优先比较 x, x 相等的情况下比较 y,y 仍相等则比较 z
引用方式：priority_queue<lei,vector<lei>,mop> pq;

基本操作

pq.push();    //入队
pq.pop();     //出队
pq.size()     //返回当前对中元素个数
pq.top();     //优先队列   取队首元素
pq.empty();   //判断是否为空（空返回 1，非空返回 0）

队列的代码示例

#include<iostream>
#include<queue>
using namespace std;
int main()
{
   queue<int> q;
   q.push(1);
   q.push(2);
   q.push(3);
   printf("\n判断队列是否为空(空为真:1，非空为假:0)：\n");
   cout<<q.empty()<<endl;
   printf("返回队列元素个数：\n");
   cout<<q.size()<<endl;
   printf("\n读取队首元素：\n");
   cout<<q.front()<<endl;
   printf("所有元素出队（删除所有元素）：\n");  
   while(q.empty()!=true) 
   {
        cout<<q.front()<<endl;
        q.pop();
   }   
   printf("\n判断队列是否为空(空为真:1，非空为假:0)：\n")； 
   cout<<q.empty()<<endl;
   return 0;
}

输出结果：

优先队列代码示例

#include<iostream>
#include<queue>
using namespace std;
struct lei            //定义优先级
{
    bool operator ()(int a,int b)
    {
         return a<b; //大顶堆，相当于less
    }
};
int main()
{
    priority_queue<int,vector<int>,lei> pq;
    printf("入队操作：1,2,3\n\n");
    pq.push(1);
    pq.push(2);
    pq.push(3);
    printf("\n判断队列是否为空(空为真:1，非空为假:0)：\n");
    cout<<pq.empty()<<endl;
    printf("返回队列元素个数：\n");
    cout<<pq.size()<<endl;
    printf("\n读取队首元素：\n");
    cout<<pq.top()<<endl;
    printf("所有元素出队（删除所有元素）：\n");
    while(pq.empty()!=true)
    {
         cout<<pq.top()<<endl;
         pq.pop();
    }
    printf("\n判断队列是否为空(空为真:1，非空为假:0)：\n");
    cout<<pq.empty()<<endl;
    cout<<endl;
    return 0；
}

输出结果：