我要评论1. 简介：容器适配器
在 c++ stl 中，queue（队列）和 priority queue（优先队列）都被归类为容器适配器，而非标准容器。所谓适配器模式，就是将特定容器类封装作为其底层容器类，并提供一组特定的成员函数来访问其元素。
- queue（队列）：专门用于 fifo（先进先出）上下文，元素的流动规则是“队尾入，队头出”。
- priority queue（优先队列）：底层类似堆（heap）结构。它并不遵循先进先出，而是根据严格的弱排序标准，保证每次出队的元素都是当前队列中最大（或最小）的元素。
2. 核心接口与基本使用
2.1 queue 的基本使用
queue 的底层容器应至少支持：empty、size、front、back、push_back、pop_front。默认情况下，使用 deque。
| 接口名称 | 功能说明 |
|---|---|
| push(val) / pop() | 队尾入队 / 队头出队 |
| front() / back() | 返回队头元素的引用 / 返回队尾元素的引用 |
| empty() / size() | 检测队列是否为空 / 返回有效元素个数 |
2.2 priority queue 的基本使用
priority queue 的底层容器必须支持随机访问迭代器（如 empty、size、front、push_back、pop_back），因为它需要借助堆算法（make_heap, push_heap, pop_heap）来维护结构。默认情况下，使用 vector 作为底层容器，且默认是大根堆（max-heap）。
| 接口名称 | 功能说明 |
|---|---|
| push(val) | 在优先队列中插入元素，并自动调整堆结构 |
| pop() | 删除优先队列中最大（或最小）的堆顶元素 |
| top() | 返回堆顶元素（最大或最小元素） |
| empty() / size() | 检测是否为空 / 返回元素个数 |
#include <iostream>
#include <queue>
using namespace std;
void test_priority_queue() {
// 默认是大堆（输出：9 8 7 6 ...）
priority_queue<int> max_pq;
max_pq.push(3);
max_pq.push(9);
max_pq.push(1);
cout << "max heap top: " << max_pq.top() << endl; // 输出 9
}
3. priority queue 的仿函数与自定义类型
在使用优先队列时，我们常常需要改变默认的大根堆行为，或者存储自定义的数据类型。
3.1 切换为小根堆
要创建小根堆，需要引入 <functional> 头文件，并将第三个模板参数替换为 greater<t>。
#include <queue> #include <functional> // greater 算法的头文件 // 创建小根堆，底层按照大于号比较 std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
3.2 自定义类型的比较
如果优先队列中存放自定义类型，用户需要在自定义类型中提供 > 或者 < 的重载，或者传入自定义的仿函数（functor）。
class date {
public:
date(int year, int month, int day) : _year(year), _month(month), _day(day) {}
// 大根堆需要重载 <
bool operator<(const date& d) const {
if (_year != d._year) return _year < d._year;
if (_month != d._month) return _month < d._month;
return _day < d._day;
}
private:
int _year, _month, _day;
};
void test_custom_type() {
std::priority_queue<date> q;
q.push(date(2023, 10, 1));
q.push(date(2023, 11, 11)); // 这个会成为堆顶
}
4. 经典算法实战
4.1 queue 实战：
思路：使用两个队列（q1, q2）模拟栈。入栈直接进非空队列；出栈时，将非空队列前 n-1 个元素倒入空队列，弹出最后剩下的那个元素即可。
class mystack {
public:
void push(int x) {
q1.empty() ? q2.push(x) : q1.push(x);
}
int pop() {
std::queue<int>& emptyq = q1.empty() ? q1 : q2;
std::queue<int>& nonemptyq = q1.empty() ? q2 : q1;
while (nonemptyq.size() > 1) {
emptyq.push(nonemptyq.front());
nonemptyq.pop();
}
int topelement = nonemptyq.front();
nonemptyq.pop();
return topelement;
}
// top() 和 empty() 逻辑省略...
private:
std::queue<int> q1, q2;
};
4.2 priority queue 实战：
思路：将数组元素全部放入大根堆（优先队列）中，然后执行 k-1 次 pop()，此时的堆顶元素就是第 k 大的元素。
class solution {
public:
int findkthlargest(vector<int>& nums, int k) {
// 将数组中的元素先放入优先级队列中 (o(n) 建堆)
std::priority_queue<int> p(nums.begin(), nums.end());
// 将前 k-1 个最大的元素删除
for(int i = 0; i < k - 1; ++i) {
p.pop();
}
return p.top();
}
};
5. 为什么 queue 默认 deque，而 priority queue 默认 vector？
queue 为什么默认 deque 而不支持 vector？
queue 强依赖头删（pop_front）和尾插（push_back）。deque 在头部删除和尾部插入时效率极高，时间复杂度为 o(1)。若用 vector 封装，每次头删都需要挪动后续所有数据，时间复杂度骤降为 o(n)。
priority queue 为什么默认 vector？
优先队列本质是一个堆（完全二叉树的数组实现）。堆的维护依赖大量的随机访问（例如通过父节点索引 i 访问左右孩子 2i+1, 2i+2）。vector 提供了极致的随机访问性能和极高的空间缓存命中率，因此是优先队列的最佳拍档。
附录：适配器的模拟实现 (封装)
queue 的封装
#pragma once
#include <deque>
namespace bit {
template<class t, class container = std::deque<t>>
class queue {
public:
void push(const t& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const t& back() { return _con.back(); }
const t& front() { return _con.front(); }
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
private:
container _con;
};
}
priority queue 的封装
借用 stl 的堆算法（push_heap, pop_heap）即可极其优雅地实现优先队列适配器。
#pragma once
#include <vector>
#include <algorithm> // 包含堆算法
#include <functional>
namespace bit {
template<class t, class container = std::vector<t>, class compare = std::less<t>>
class priority_queue {
public:
priority_queue() {}
template<class inputiterator>
priority_queue(inputiterator first, inputiterator last) : _con(first, last) {
// 建堆
std::make_heap(_con.begin(), _con.end(), comp);
}
void push(const t& x) {
_con.push_back(x);
std::push_heap(_con.begin(), _con.end(), comp); // 向上调整
}
void pop() {
std::pop_heap(_con.begin(), _con.end(), comp); // 将堆顶移到末尾，向下调整
_con.pop_back(); // 真正删除
}
const t& top() const {
return _con.front();
}
bool empty() const {
return _con.empty();
}
size_t size() const {
return _con.size();
}
private:
container _con;
compare comp; // 比较器对象
};
}
到此这篇关于c++中queue与priority queue的实现的文章就介绍到这了,更多相关c++ queue与priority queue内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论