c++queue和priority_queue

时间: 2023-11-06 08:06:39 浏览: 204

c stack_和_queue用法

### C++ STL 中 stack 和 queue 的使用方法 #### 一、引言在 C++ 编程语言中，标准模板库 (STL) 提供了一系列高效的数据结构和算法，极大地提高了程序员的工作效率。其中，`stack` 和 `queue` 是两种常见的线性数据结构，在程序设计中经常被用作辅助数据结构，帮助解决各种问题。本文将详细介绍 C++ STL 中 `stack` 和 `queue` 的使用方法，以及它们的一个变体 `priority_queue`。 #### 二、Stack (栈) ##### 2.1 定义与作用 `stack` 是一种先进后出 (Last In First Out, LIFO) 的数据结构。它通常用于需要按逆序访问元素的情况，例如函数调用堆栈或者表达式求值等场景。 ##### 2.2 使用方法 `stack` 的定义位于 `<stack>` 头文件中。其基本用法如下： ```cpp #include <stack> // 定义一个整数类型的栈 std::stack<int> s; // 入栈 s.push(5); s.push(10); // 出栈 s.pop(); // 访问栈顶元素 int topElement = s.top(); // 检查是否为空 bool isEmpty = s.empty(); // 获取栈大小 size_t size = s.size(); ``` #### 三、Queue (队列) ##### 3.1 定义与作用 `queue` 是一种先进先出 (First In First Out, FIFO) 的数据结构。它通常用于需要按顺序访问元素的情况，例如消息队列、任务调度等场景。 ##### 3.2 使用方法 `queue` 的定义位于 `<queue>` 头文件中。其基本用法如下： ```cpp #include <queue> // 定义一个整数类型的队列 std::queue<int> q; // 入队 q.push(5); q.push(10); // 出队 q.pop(); // 访问队首元素 int frontElement = q.front(); // 访问队尾元素 int backElement = q.back(); // 检查是否为空 bool isEmpty = q.empty(); // 获取队列大小 size_t size = q.size(); ``` #### 四、Priority Queue (优先队列) ##### 4.1 定义与作用 `priority_queue` 是一种特殊类型的队列，它可以自动根据元素的优先级进行排序。默认情况下，优先队列会将最大的元素放在队首，但可以通过自定义比较器来改变这种行为。 ##### 4.2 使用方法 `priority_queue` 的定义同样位于 `<queue>` 头文件中。其基本用法如下： ```cpp #include <queue> // 默认情况下，优先队列会将最大的元素放在队首 std::priority_queue<int> pq; // 可以通过传递第三个参数自定义比较器 std::priority_queue<int, std::vector<int>, std::greater<int>> pqMin; // 最小的元素放在队首 // 入队 pq.push(5); pq.push(10); pqMin.push(5); pqMin.push(10); // 出队 pq.pop(); pqMin.pop(); // 访问队首元素 int topElement = pq.top(); int minElement = pqMin.top(); // 检查是否为空 bool isEmpty = pq.empty(); bool isMinEmpty = pqMin.empty(); // 获取队列大小 size_t size = pq.size(); size_t minSize = pqMin.size(); ``` ##### 4.3 自定义类型及比较器对于非基本数据类型，我们需要提供自定义的比较器。例如，对于一个包含三个整数成员的自定义类 `T`，我们可以这样定义比较器： ```cpp #include <iostream> #include <queue> class T { public: int x, y, z; T(int a, int b, int c) : x(a), y(b), z(c) {} }; // 定义比较器 bool operator<(const T& t1, const T& t2) { return t1.z < t2.z; // 按照 z 的顺序来决定 t1 和 t2 的顺序 } int main() { std::priority_queue<T> q; q.push(T(4, 4, 3)); q.push(T(2, 2, 5)); q.push(T(1, 5, 4)); q.push(T(3, 3, 6)); while (!q.empty()) { T t = q.top(); q.pop(); std::cout << t.x << " " << t.y << " " << t.z << std::endl; } return 0; } ``` 输出结果为： ``` 3 3 6 2 2 5 1 5 4 4 4 3 ``` 以上是关于 C++ STL 中 `stack`、`queue` 和 `priority_queue` 的详细介绍。希望这篇文章能帮助读者更好地理解和使用这些数据结构。

queue 和 priority_queue 都是容器适配器，用于实现队列的数据结构。它们都可以通过包含 <queue> 头文件来使用。 queue 是一种先进先出（FIFO）的数据结构，支持在队尾插入元素，在队头取出元素。queue 的内部实现通常使用双向链表或动态数组。 priority_queue 是一种优先队列，也是一种队列，但是元素根据优先级来排序。priority_queue 使用堆排序技术来实现，内部并非完全有序，但能确保最大（或最小）元素总在队头。因此，priority_queue 特别适用于需要不断取出最大（或最小）元素的情况。priority_queue 的插入和删除元素的复杂度都是 O(log(n))。

阅读全文

c++queue和priority_queue

相关推荐

C++ STL容器适配器详解：stack, queue与priority_queue

C++进阶：STL容器适配器详解 - stack, queue与priority_queue

C++ 中"priority_queue" 优先级队列实例详解

C++ 中”priority_queue” 优先级队列实例详解

STL中的容器适配器：stack、queue和priority_queue

C++容器：priority_queue的优先级队列详解

容器适配器：stack、queue、priority_queue的应用场景

c++ multiset 和 priority_queue

c++ 如何输出priority_queue的内同

C++中priority_queue和queue的区别

C++如何遍历priority_queue> pq的内容

c++遍历priority_queue

C++ STL priority_queue

c++的priority_queue

c++中priority_queue

c+++priority_queue

c++ priority_queue

自定义最大堆实现优先队列(priority_queue)

STL优先级队列(priority_queue)详解：堆算法与容器应用

最新推荐

用于托管 Discord Overlay 的 DirectX 11 窗口.zip

MATLAB新功能：Multi-frame ViewRGB制作彩色图阴影

管理建模和仿真的文件

【实战篇：自定义损失函数】：构建独特损失函数解决特定问题，优化模型性能

在Flow-3D中如何根据水利工程的特定需求设定边界条件和进行网格划分，以便准确模拟水流问题？

XKCD Substitutions 3-crx插件：创新的网页文字替换工具

"互动学习：行动中的多样性与论文攻读经历"

【强化学习损失函数探索】：奖励函数与损失函数的深入联系及优化策略

在Flow-3D中，如何根据水利工程的特定需求设定边界条件和进行网格划分，以便准确模拟水流问题？

Python实现8位等离子效果开源项目plasma.py解读