C++ STL熟悉并巩固（十六）------queue和priority_queue

本文中的一些重要概念摘自C语言中文网
链接：http://c.biancheng.net/view/396.html

queue其实就是队列，队列这种数据结构我们也在数据结构课程中学过了，它就是一种“先进先出”的数据结构，跟我们平时排队时的情况一样（文明，不插队）。queue也有push pop top等成员函数，但是与stack不同的是，queue的push操作是在队尾进行的，而queue的pop和top操作是在队头进行的。

同样使用queue时要包含头文件queue

priority_queue 是“优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。

在默认情况下，要放入 priority_queue 的元素必须是能用“<”运算符进行比较的，而且 priority _queue 保证以下条件总是成立：对于队头的元素 x 和任意非队头的元素 y，表达式“x<y”必为 false。

和 set/multiset 不同，priority_queue 是使用“堆排序”技术实现的，其内部并非完全有序，但却能确保最大元素总在队头。因此，priority_queue 特别适用于“不停地在一堆元素中取走最大的元素”这种情况。priority_queue 插入和删除元素的复杂度都是 O(log(n))。虽然用 set/multiset 也能完成此项工作，但是 priority_queue 比它们略快一些。

priority_queue 队头的元素只能被查看或者修改，不能被删除。

以下是priority_queue的测试程序：

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(30);
    pq.push(115);
    pq.push(100);
    pq.push(11);

    while(!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}

测试程序输出结果：

本节完