本文主要是介绍C++之容器:双端队列queue用法实例(二百七十二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长!
优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀
优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀
优质视频课程:AAOS车载系统+AOSP14系统攻城狮入门实战课【原创干货持续更新中……】🚀
人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药.
🍉🍉🍉文章目录🍉🍉🍉
- 🌻1.前言
- 🌻2.C++之queue介绍
- 🌻3.代码实例
- 🐓3.1 使用 queue 实现 Level Order 遍历二叉树
- 🐓3.2 使用 queue 解决广度优先搜索问题
- 🐓3.3 使用 queue 实现逆波兰表达式求值
🌻1.前言
本篇目的:C++之容器:双端队列queue用法实例
🌻2.C++之queue介绍
-
C++ 中的 deque 是一种容器,全称为 double-ended queue,即双端队列。它支持在两端进行元素的插入和删除操作,具有较高的效率。deque 是 C++ STL(标准模板库)中的一部分,使用时需要包含头文件 。
-
deque 的主要特点如下:
-
两端操作:deque 支持在两端进行元素的插入和删除。这意味着可以在队列的前端(头部)和后端(尾部)分别进行 push 和 pop 操作,类似于生活中的队列和栈。
-
动态数组:deque 内部采用动态数组实现,可以自动调整容量以适应元素数量的变化。当 deque 容量不足时,系统会自动为其分配更大的空间;当容量过剩时,系统会释放部分空间。
-
随机访问:deque 支持随机访问,即可以通过索引直接访问 deque 中的元素。这使得 deque 在查找元素时具有较高的效率。
-
迭代器:deque 支持迭代器,可以通过迭代器进行元素的遍历和操作。
-
在使用 deque 时,需要指定其元素类型。例如,创建一个整数类型的 deque,可以使用以下语法:
deque 的常用操作:
插入元素:
在前端插入元素:d.push_front(value)
在后端插入元素:d.push_back(value)
删除元素:
从前端删除元素:d.pop_front()
从后端删除元素:d.pop_back()
访问元素:
通过索引访问元素:d[index]
获取前端元素:d.front()
获取后端元素:d.back()
容量操作:
返回 deque 的容量:d.size()
清空 deque:d.clear()
返回 deque 的最大容量:d.max_size()
关系操作:
判断两个 deque 是否相等:d1 == d2
判断两个 deque 是否不等:d1 != d2
判断 deque 是否为空:d.empty()
🌻3.代码实例
🐓3.1 使用 queue 实现 Level Order 遍历二叉树
#include <iostream>
#include <queue>
#include <vector>struct TreeNode {int value;TreeNode *left;TreeNode *right;TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};void levelOrder(TreeNode *root) {if (root == nullptr) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode *node = q.front();q.pop();std::cout << node->value << " ";if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right);}
}int main() {TreeNode *root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);std::cout << "Level Order 遍历结果: ";levelOrder(root);return 0;
}
🐓3.2 使用 queue 解决广度优先搜索问题
#include <iostream>
#include <queue>
#include <vector>void BFS(int start, const std::vector<int>& graph) {std::queue<int> q;std::vector<bool> visited(graph.size(), false);q.push(start);visited[start] = true;while (!q.empty()) {int node = q.front();q.pop();std::cout << node << " ";for (int neighbor : graph[node]) {if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}
}int main() {std::vector<int> graph[] = {{1, 2}, {3}, {3}, {}};BFS(0, graph);return 0;
}
🐓3.3 使用 queue 实现逆波兰表达式求值
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>using namespace std;int precedence(char op) {if (op == '+' || op == '-') return 1;if (op == '*' || op == '/') return 2;return 0;
}int applyOp(int a, int b, char op) {switch (op) {case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b;}return 0;
}int evaluateRPN(string &rpn) {stack<int> values;std::queue<char> ops;for (int i = 0; i < rpn.length(); i++) {if (rpn[i] == ' ') continue;if (isdigit(rpn[i])) {values.push(stoi(string(1, rpn[i])));} else {ops.push(rpn[i]);}}while (!ops.empty()) {char op = ops.front();ops.pop();int b = values.top();values.pop();int a = values.top();values.pop();values.push(applyOp(a, b, op));}}return values.top();
}int main() {string rpn = "2 3 4 * + 5 6 / +";cout << "逆波兰表达式求值结果: " << evaluateRPN(rpn) << endl;return 0;
}
这篇关于C++之容器:双端队列queue用法实例(二百七十二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!