【C++指南】STL queue 完全解读（一）：原理剖析与实战应用-EW帮帮网

.
💓 博客主页：倔强的石头的CSDN主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《C++指南》
期待您的关注

文章目录

引言

队列（queue）的规则，严格遵循"先进先出"（FIFO）的规则传递数据。
从操作系统调度到网络数据包处理，从广度优先搜索到异步任务处理，队列始终是不可或缺的核心角色。
本文将深入探讨C++ STL中的queue容器适配器，通过理论解析与实战代码演示，揭示其在现代编程中的独特价值。本文既可作为新手的入门指南，也可为资深开发者提供系统化的知识梳理。

关于队列的结构的详细介绍，可以参考我之前写的一篇用C语言手搓队列的讲解文章
👇
【数据结构与算法】使用单链表实现队列：原理、步骤与应用

一、C++ STL queue全景透视

1.1 容器适配器的设计哲学

queue是典型的容器适配器，其标准定义如下：

template <class T, class Container = deque<T> >
class queue;

访问限制：仅允许访问队列首尾元素
操作特性：所有基础操作时间复杂度均为O(1)
容器灵活性：支持底层容器切换（默认deque，可替换为list）

1.2 核心价值体现

数据缓冲：天然适合生产者-消费者模型
操作安全性：严格的访问控制防止越界操作
算法适配：完美契合广度优先搜索等经典算法
资源管理：自动内存管理简化开发流程

二、queue核心操作深度解析

2.1 基础操作矩阵

操作	语法	时间复杂度	说明
入队	push(const T& val)	O(1)	在队尾插入元素
出队	pop()	O(1)	移除队首元素
访问队首	front()	O(1)	返回队首元素的引用
访问队尾	back()	O(1)	返回队尾元素的引用
判空检测	empty()	O(1)	判断队列是否为空
容量查询	size()	O(1)	返回当前元素数量

2.2 实战代码演练

示例1：基础操作全流程

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 入队操作
    q.push(10);  // 队首 -> [10] <- 队尾
    q.push(20);  //        [10, 20]
    q.push(30);  //        [10, 20, 30]

    // 访问首尾元素
    std::cout << "Front: " << q.front() << std::endl;  // 输出10
    std::cout << "Back: " << q.back() << std::endl;    // 输出30

    // 出队操作
    q.pop();  // 移除10 → [20, 30]
    q.pop();  // 移除20 → [30]

    if (!q.empty()) {
        std::cout << "Current size: " << q.size();  // 输出1
    }
    return 0;
}

示例2：广度优先搜索（BFS）算法

void bfs(Node* root) {
    if (!root) return;

    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; ++i) {
            Node* current = q.front();
            q.pop();
            
            // 处理当前节点
            std::cout << current->val << " ";
            
            // 子节点入队
            for (auto child : current->children) {
                if (child) q.push(child);
            }
        }
        std::cout << std::endl;  // 分层输出
    }
}

// 树结构示例
struct Node {
    int val;
    std::vector<Node*> children;
};

三、高级应用场景

3.1 消息队列系统

template <typename T>
class MessageQueue {
private:
    std::queue<T> buffer;
    std::mutex mtx;
    std::condition_variable cv;

public:
    void push(const T& msg) {
        std::lock_guard<std::mutex> lock(mtx);
        buffer.push(msg);
        cv.notify_one();
    }

    T pop() {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, [this]{ return !buffer.empty(); });
        T msg = buffer.front();
        buffer.pop();
        return msg;
    }
};

3.2 打印机任务调度

struct PrintJob {
    int id;
    string content;
    time_t timestamp;
};

void printScheduler() {
    std::queue<PrintJob> printQueue;
    
    // 模拟任务添加
    printQueue.push({1, "Report.pdf", time(nullptr)});
    printQueue.push({2, "Image.png", time(nullptr)+5});

    while (!printQueue.empty()) {
        auto job = printQueue.front();
        printQueue.pop();
        // 执行打印操作
        std::cout << "Printing #" << job.id << ": " 
                  << job.content << std::endl;
    }
}

3.3 数据流处理

template <typename T>
class MovingAverage {
private:
    std::queue<T> window;
    size_t maxSize;
    T sum = 0;

public:
    MovingAverage(size_t size) : maxSize(size) {}

    double next(T val) {
        if (window.size() == maxSize) {
            sum -= window.front();
            window.pop();
        }
        window.push(val);
        sum += val;
        return static_cast<double>(sum) / window.size();
    }
};

// 使用示例
MovingAverage<int> ma(3);
cout << ma.next(1) << endl;  // 1.0
cout << ma.next(2) << endl;  // 1.5
cout << ma.next(3) << endl;  // 2.0
cout << ma.next(4) << endl;  // 3.0

结语

通过对STL queue的系统性探索，我们不仅掌握了队列的基本操作，更领略了其在算法设计中的独特魅力。
从基础的BFS算法到复杂的消息队列系统，queue始终以其严谨的FIFO特性保障着数据的有序流动。
然而，这些只是冰山一角——在下一篇文章中，我们将深入queue的实现底层，解析其容器适配器的设计奥秘，并亲手实现支持动态扩容的安全队列。届时，您将彻底理解STL设计者的匠心独运，并能够根据实际需求定制高性能队列。

下篇预告：《揭秘STL queue：从底层实现到高效队列设计》——深入源码分析queue的适配机制，实现支持环形缓冲的线程安全队列。

【C++指南】STL queue 完全解读（一）：原理剖析与实战应用