【C++】deque以及优先级队列

在C++中，deque是一种双向队列容器，它允许在容器的前面或者后面高效地插入和删除元素。而优先队列是一种特殊的队列，它按照一定的优先级顺序排序元素，使得队首元素总是最大或最小的。

以下是使用deque和优先队列的示例代码：

使用deque：

#include <iostream>
#include <deque>
 
int main() {
    std::deque<int> d; // 创建一个int类型的deque容器
 
    // 添加元素
    d.push_back(30);
    d.push_front(20);
    d.push_back(40);
    d.push_front(10);
 
    // 遍历deque
    for (int i : d) {
        std::cout << i << " "; // 输出：10 20 30 40
    }
 
    // 删除元素
    d.pop_front(); // 删除开头的10
    d.pop_back();  // 删除尾部的40
 
    return 0;
}

使用优先队列：

#include <iostream>
#include <queue>
 
int main() {
    std::priority_queue<int> pq; // 创建一个默认最大堆的优先队列
 
    // 添加元素
    pq.push(30);
    pq.push(20);
    pq.push(40);
    pq.push(10);
 
    // 队列中最大的元素在顶部，因此while循环会先打印40再打印30...
    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 输出：40 30 20 10
        pq.pop();
    }
 
    return 0;
}

在优先队列中，默认情况下，元素按照大于操作符所定义的优先级从高到低排序。如果想要创建一个最小堆，可以使用第二个模板参数指定比较函数，如下所示：

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

在这个例子中，std::greater<int>定义了一个比较函数，使得队列成为最小堆。