简介： CSDN博客专家，专注Android/Linux系统，分享多mic语音方案、音视频、编解码等技术，与大家一起成长！

优质专栏：Audio工程师进阶系列【原创干货持续更新中……】🚀
优质专栏：多媒体系统工程师系列【原创干货持续更新中……】🚀
优质视频课程：AAOS车载系统+AOSP14系统攻城狮入门实战课【原创干货持续更新中……】🚀

人生格言： 人生从来没有捷径，只有行动才是治疗恐惧和懒惰的唯一良药.

更多原创,欢迎关注：Android系统攻城狮

🌻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;
}