队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

顺序队列，循环队列。

以数组为例进行队列的实现

队列数据结构：

typedef struct queue
{
        int queuesize;   //数组的大小
        int head, tail;  //队列的头和尾下标
        int *q;          //数组头指针
}Queue;

队列初始化

void InitQueue(Queue *q)
{
        q->queuesize = 8;
        q->q = (int *)malloc(sizeof(int) * q->queuesize); //分配内存
        q->tail    = 0;
        q->head = 0;
}

进队列

void EnQueue(Queue *q, int key)
{
        int tail = (q->tail+1) % q->queuesize; 
        //取余保证，当quil=queuesize-1时，再转回0
        if (tail == q->head)                   //此时队列没有空间
        {
            printf("the queue has been filled full!");
        }
        else
        {
            q->q[q->tail] = key;
            q->tail = tail;
        }
}

出队列

int DeQueue(Queue *q)
{
        int tmp;
        if(q->tail == q->head)     //判断队列不为空
        {
            printf("the queue is NULL\n");
        }
        else
        {
            tmp = q->q[q->head];
            q->head = (q->head+1) % q->queuesize;
        }
        return tmp;
}
判断队列是否为空
int IsQueueEmpty(Queue *q)
{
        if(q->head == q->tail)
        {
            return 1;
        }
        else
        {
            return 0;
        }
}

以上这些只是自己实现一下，标准库里面都有标准的库函数

头文件为

队列提供了下面的操作

q.empty() //如果队列为空返回true，否则返回false

q.size() //返回队列中元素的个数

q.pop() //删除队列首元素但不返回其值

q.front() // 返回队首元素的值，但不删除该元素

q.push() // 在队尾压入新元素

q.back() // 返回队列尾元素的值，但不删除该元素

优先队列

优先队列：顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~

百度百科上这样描述的：优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

在优先队列中，优先级高的元素先出队列。

标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。

优先队列的用法，也是最常用的用法：priority_queue q;

通过<操作符可知在整数中元素大的优先级高。

故将2,3,5,6,9插入队列输出的话结果为9,6,5,3,2。

如果我们要把元素从小到大输出怎么办呢？

这时我们可以传入一个比较函数，使用functional(头文件)函数对象作为比较函数。

priority_queue, greater >q;

//注意“>>”会被认为错误，这是右移运算符，所以这里用空格号隔开

其中，第二个参数为容器类型，第三个参数为比较函数

所以这样定义之后，上面的输出就为2,3,5,6,9。

priority_queue,less >q;//最大值优先

当然了，其中的greater与less也可以自己定义

struct cmp1{

bool operator ()(int &a,int &b)\{  
    return a>b;//最小值优先  
\}

};

struct cmp2{

bool operator ()(int &a,int &b)\{  
    return a<b;//最大值优先  
\}

};

priority_queue,cmp1>q;//最小值优先

priority_queue,cmp2>q;//最大值优先

结构体自定义优先级方法

struct node

{

int w,id;
//node(int w=0,int id=0):w(w),id(id)\{\}//结构体的构造函数
//结构体默认的是不带参数的构造函数
bool operator < (const node& u)const
\{ 
    if(w!=u.w)return w < u.w;//最大值优先
    return id > u.id;//最小值优先
    //优先队列排序问题，w从大到小排列，
    //w相同就id由小到大排列
\}