C++ queue和priority_queue

我会带着你远行 2023-07-16 03:44 28阅读 0赞

**queue 和 priority\_queue 都是容器适配器，要使用它们，必须包含头文件 。**

### queue ###

queue 就是“队列”。队列是先进先出的，和排队类似。队头的访问和删除操作只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。

queue 可以用 list 和 deque 实现，默认情况下用 deque 实现。

queue 的定义如下：

template < class T, class Cont = deque<T> >
    class queue{ 
        ...
    };

queue 同样也有和 stack 类似的 push、pop、top 函数。区别在于，queue 的 push 发生在队尾，pop 和 top 发生在队头。

### priority\_queue ###

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

priority\_queue 可以用 vector 和 deque 实现，默认情况下用 vector 实现。

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

priority\_queue 定义如下：

template < class T, class Container = vector <T>, class Compare = less<T> >
    class priority_queue{ 
        ...
    };

priority\_queue 的第三个类型参数可以用来指定排序规则。

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

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

priority\_queue的用法示例如下。

#include <queue>
    #include <iostream>
    using namespace std;
    int main()
    { 
        priority_queue<double> pq1;
        pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
        while(!pq1.empty()) { 
            cout << pq1.top() << " ";
            pq1.pop();
        } //上面输出 9.8 9.8 5.4 3.2
        cout << endl;
        priority_queue<double,vector<double>,greater<double> > pq2;
        pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
        while(!pq2.empty()) { 
            cout << pq2.top() << " ";
            pq2.pop();
        }
        //上面输出 3.2 5.4 9.8 9.8
        return 0;
    }

程序的输出结果是：

9.8 9.8 5.4 3.2
    3.2 5.4 9.8 9.8

pq2 的排序规则和 pq1 相反，因此元素出队的顺序也相反。