队列与优先队列的总结

﹏ヽ暗。殇╰゛Y 2022-05-19 04:56 228阅读 0赞

# **队列** #

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

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

[c++][c][队列][Link 2][queue][][模板][Link 3][类][Link 4]的定义在<queue>[头文件][Link 5]中,queue 模板类需要两个模板[参数][Link 6]，一个是元素类型，一个[容器][Link 7]类型，元素类型是必要的，容器类型是可选的，默认为[deque][] 类型。

**C++队列Queue类成员[函数][Link 8]有:**

[back][]() 返回最后一个元素

[empty][]() 如果队列空则返回真

front() 返回[第一个][Link 9]元素

[pop][]() 删除第一个元素

[push][]() 在末尾[加入][Link 10]一个元素

[size][]() 返回队列中元素的个数

例如0-5，共5个元素，我们对其进行入队出队操作：

代码例：

#include<queue>
    #include<cstdio>
    using namespace std;
    int main()
    {
        queue <int> myQ;
        printf("现在队列中元素个数%d\n\n",myQ.size());
        for(int i =0; i<5 ; i++)
        {
            myQ.push(i);//入队
        }
        for(int i=0; !myQ.empty(); i++)
        {
            printf("队列剩余元素个数为:%d\n\n",myQ.size());
            printf("队列的第一个元素为:%d   队列最后一个元素为:%d\n\n",myQ.front(),myQ.back());
            myQ.pop();//出队
        }
        myQ.push(8);//在队列的最后一位添加一个元素
        printf("队列压入的元素为：%d\n",myQ.back());
        return 0;
    }

输出结果为

![70][]

优先队列：C++优先队列类似队列，但是在这个数据结构中的元素按照一定顺序排列。

成员函数有：  
1.empty() 如果优先队列为空，则返回真  
2.pop() 删除第一个元素  
3.push() 加入一个元素  
4.size() 返回优先队列中拥有的元素的个数  
5.top() 返回优先队列中有最高优先级的元素  
例代码：

#include<cstdio>
    #include<queue>
    using namespace std;
    int main()
    {
        priority_queue<int>Q;
        for(int i=1;i<=5;i++)
        {
            int x;
            scanf("%d",&x);//压入输入的元素
            Q.push(x);
        }
        for(int i=1;i<=5;i++)
        {
            printf("优先队列中最大元素为:%d\n\n",Q.top());//由于没有定义优先级，优先队列将按照元素大小来确定优先级
            Q.pop();
        }
        return 0;
    }

我们输入乱序的一堆数，在输出的时候我们可以看到，这些数是按照谁最大谁先输出

![70 1][]

现在对优先队列进行自定义安排优先级，这里我们自定义了两个队列，它们的优先级相反

代码：

#include<cstdio>
    #include<queue>
    #include<algorithm>
    using namespace std;
    struct node
    {
        int time;
        friend bool operator < (node n1, node n2)
        {
            return n1.time<n2.time;//自定义优先级从大到小
        }
    } a;
    struct node1
    {
        int time;
        friend bool operator <(node1 n1,node1 n2)
        {
            return n1.time>n2.time;//从小到大
        }
    } b;
    int main()
    {
        priority_queue<node>Q;
        priority_queue<node1>Q1;
        int i;
        for(i=0; i<5; i++)
        {
            int x;
            scanf("%d",&x);
            a.time=x;
            b.time=x;
            Q.push(a);
            Q1.push(b);
        }
        printf("队列1中优先级输出顺序为:\n");
        while(!Q.empty())
        {
            a=Q.top();
            Q.pop();
            printf("%d ",a);
        }
        printf("\n");
        printf("队列2中优先级输出顺序为:\n");
        while(!Q1.empty())
        {
            b=Q1.top();
            Q1.pop();
            printf("%d ",b);
        }
        return 0;
    }

运行结果

![70 2][]

[Link 1]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8
[c]: http://www.169it.com/tag/c++
[Link 2]: http://www.169it.com/tag/%E9%98%9F%E5%88%97
[queue]: http://www.169it.com/tag/queue
[Link 3]: http://www.169it.com/tag/%E6%A8%A1%E6%9D%BF
[Link 4]: http://www.169it.com/tag/%E7%B1%BB
[Link 5]: http://www.169it.com/tag/%E5%A4%B4%E6%96%87%E4%BB%B6
[Link 6]: http://www.169it.com/tag/%E5%8F%82%E6%95%B0
[Link 7]: http://www.169it.com/tag/%E5%AE%B9%E5%99%A8
[deque]: http://www.169it.com/article/7695150204126226105.html
[Link 8]: http://www.169it.com/tag/%E5%87%BD%E6%95%B0
[back]: http://www.169it.com/tag/back
[empty]: http://www.169it.com/tag/empty
[Link 9]: http://www.169it.com/tag/%E7%AC%AC%E4%B8%80%E4%B8%AA
[pop]: http://www.169it.com/tag/pop
[push]: http://www.169it.com/tag/push
[Link 10]: http://www.169it.com/tag/%E5%8A%A0%E5%85%A5
[size]: http://www.169it.com/tag/size
[70]: /images/20220519/f557ca4f152a4525b6ba94dedb48eda1.png
[70 1]: /images/20220519/1b8d95eb81d54b69afabfb5421fe9fdc.png
[70 2]: /images/20220519/b9aac4ca6a2c40a4a04b7701ce373a75.png