C++基础：（十五）queue的深度解析和模拟实现

_OP_CHEN

发布于 2026-01-14 09:58:21

1180

文章被收录于专栏：C++C++

前言

队列（queue）作为计算机科学中最基础的数据结构之一，在操作系统调度、网络数据包处理、打印机任务管理等场景中具有不可替代的作用。C++标准库中的queue容器适配器通过封装底层容器，提供了先进先出（FIFO）的严格数据管理机制。其设计哲学体现了STL的核心思想：将数据结构和算法分离，同时通过模板编程实现高度的可定制性。深入理解queue的底层实现机制，不仅能够帮助开发者更高效地使用标准库组件，更能为特定场景下的自定义队列实现提供设计范本。本文将系统分析STL queue的接口设计原理、性能特征，并给出符合STL规范的完整模拟实现方案。下面就让我们正式开始吧！

一、 queue 的概念与特性

queue（队列）是一种遵循 “先进先出”（FIFO，First In First Out）原则的线性数据结构。类似于日常生活中的排队：先排队的人先接受服务，后排队的人后接受服务。

queue 的核心操作集中在 “队头” 和 “队尾”：

只能在队尾插入元素（入队，push）；
只能在队头删除元素（出队，pop）；
可以访问队头元素（front）和队尾元素（back）。

queue 适用于需要 “顺序处理” 的场景，例如任务调度、消息队列、广度优先搜索（BFS）等。

二、 queue 的核心接口与使用示例

STL 为 queue 提供的常用成员函数如下表所示：

函数声明	接口说明
queue()	构造一个空的队列
empty()	检测队列是否为空，为空返回 true，否则返回 false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用（非 const 对象调用）
const T& front() const	返回队头元素的 const 引用（const 对象调用）
back()	返回队尾元素的引用（非 const 对象调用）
const T& back() const	返回队尾元素的 const 引用（const 对象调用）
push(const T& x)	将元素 x 插入队尾
pop()	删除队头元素（不返回元素值）

2.1 基本使用示例

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 构造空队列
    queue<int> q;
    
    // 入队操作
    q.push(10);
    q.push(20);
    q.push(30);
    
    cout << "队列的大小：" << q.size() << endl;  // 输出：3
    cout << "队头元素：" << q.front() << endl;    // 输出：10
    cout << "队尾元素：" << q.back() << endl;     // 输出：30
    
    // 出队操作
    q.pop();
    cout << "出队后队头元素：" << q.front() << endl;  // 输出：20
    cout << "出队后队列的大小：" << q.size() << endl;  // 输出：2
    
    // 遍历队列（通过出队方式）
    while (!q.empty()) {
        cout << "出队元素：" << q.front() << endl;
        q.pop();
    }
    cout << "队列是否为空：" << (q.empty() ? "是" : "否") << endl;  // 输出：是
    
    return 0;
}

2.2 注意事项

pop()函数只删除队头元素，不返回该元素的值。若需获取队头元素并删除，需先调用front()获取值，再调用pop()删除；
访问front()或back()前，必须确保队列不为空，否则会导致未定义行为；
queue 同样不支持遍历操作（没有迭代器），只能通过不断出队来访问所有元素。

三、 queue 的模拟实现

queue 的核心操作是 “尾插” 和 “头删”，因此底层容器需要支持push_back()（尾插）、pop_front()（头删）、front()（访问头元素）、back()（访问尾元素）等操作。

vector 的pop_front()操作效率极低（需要搬移所有元素，时间复杂度 O (n)），因此不适合作为 queue 的底层容器。STL 中 queue 的默认底层容器是 deque，也可以指定 list 作为底层容器。

3.1 基于 deque 的 queue 模拟实现

#include <deque>
#include <cassert>
namespace bite {
    template <class T, class Container = std::deque<T>>
    class queue {
    public:
        // 构造函数：默认构造
        queue() {}
        
        // 入队：调用底层容器的push_back
        void push(const T& x) {
            _container.push_back(x);
        }
        
        // 出队：调用底层容器的pop_front，需确保队列不为空
        void pop() {
            assert(!empty());
            _container.pop_front();
        }
        
        // 访问队头元素：调用底层容器的front，需确保队列不为空
        T& front() {
            assert(!empty());
            return _container.front();
        }
        
        // const版本的front
        const T& front() const {
            assert(!empty());
            return _container.front();
        }
        
        // 访问队尾元素：调用底层容器的back，需确保队列不为空
        T& back() {
            assert(!empty());
            return _container.back();
        }
        
        // const版本的back
        const T& back() const {
            assert(!empty());
            return _container.back();
        }
        
        // 获取队列大小
        size_t size() const {
            return _container.size();
        }
        
        // 检测队列是否为空
        bool empty() const {
            return _container.empty();
        }
        
    private:
        Container _container;  // 底层容器
    };
}

3.2 基于 list 的 queue 模拟实现

list 的push_back()和pop_front()操作均为 O (1) 时间复杂度，适合作为 queue 的底层容器。模拟实现如下：

#include <list>
#include <cassert>
namespace bite {
    template <class T, class Container = std::list<T>>
    class queue {
    public:
        queue() {}
        
        void push(const T& x) {
            _container.push_back(x);
        }
        
        void pop() {
            assert(!empty());
            _container.pop_front();
        }
        
        T& front() {
            assert(!empty());
            return _container.front();
        }
        
        const T& front() const {
            assert(!empty());
            return _container.front();
        }
        
        T& back() {
            assert(!empty());
            return _container.back();
        }
        
        const T& back() const {
            assert(!empty());
            return _container.back();
        }
        
        size_t size() const {
            return _container.size();
        }
        
        bool empty() const {
            return _container.empty();
        }
        
    private:
        Container _container;
    };
}

3.3 模拟实现的测试

#include <iostream>
#include "queue.hpp"
using namespace std;
using namespace bite;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << "size: " << q.size() << endl;        // 3
    cout << "front: " << q.front() << endl;      // 1
    cout << "back: " << q.back() << endl;        // 3
    
    q.pop();
    cout << "after pop, front: " << q.front() << endl;  // 2
    cout << "after pop, back: " << q.back() << endl;    // 3
    
    const queue<int> cq = q;
    cout << "const queue front: " << cq.front() << endl;  // 2
    cout << "const queue back: " << cq.back() << endl;    // 3
    
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    // 输出：2 3
    
    return 0;
}

四、 queue 的经典实战场景

queue 的 “先进先出” 特性使其在顺序处理场景中不可或缺，以下是几个典型应用。

4.1 用队列实现栈（LeetCode 225）

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

解题思路：

核心需求：用队列（FIFO）模拟栈（LIFO），关键是让每次入队的元素成为队头（即最后入队的元素最先出队）；
设计思路：
1. 用两个队列q1和q2，q1作为主队列，存储当前栈中的元素；
2. 压栈（push）：将元素入队到q2，然后将q1中的所有元素依次出队并入队到q2，最后交换q1和q2，使新元素成为q1的队头；
3. 出栈（pop）：直接弹出q1的队头元素（即栈顶元素）；
4. 访问栈顶（top）：返回q1的队头元素；
5. 检测为空（empty）：判断q1是否为空。

代码实现：

#include <queue>
#include <cassert>
using namespace std;

class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        queue<int> q2;
        // 新元素入队q2
        q2.push(x);
        // 将q1的所有元素转移到q2
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        // 交换q1和q2，q1成为主队列
        swap(q1, q2);
    }
    
    void pop() {
        assert(!empty());
        q1.pop();
    }
    
    int top() {
        assert(!empty());
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
    
private:
    queue<int> q1;  // 主队列，存储栈元素
};

// 测试代码
int main() {
    MyStack st;
    st.push(1);
    st.push(2);
    st.push(3);
    
    cout << st.top() << endl;  // 输出：3
    st.pop();
    cout << st.top() << endl;  // 输出：2
    st.pop();
    cout << st.top() << endl;  // 输出：1
    cout << (st.empty() ? "empty" : "not empty") << endl;  // 输出：not empty
    st.pop();
    cout << (st.empty() ? "empty" : "not empty") << endl;  // 输出：empty
    
    return 0;
}

4.2 广度优先搜索（BFS）示例

广度优先搜索是一种层级遍历算法，核心思想是 “先访问当前节点的所有邻接节点，再依次访问邻接节点的邻接节点”，queue 是实现 BFS 的理想数据结构。

示例：二叉树的层序遍历（LeetCode 102）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }
        
        queue<TreeNode*> q;
        q.push(root);  // 根节点入队
        
        while (!q.empty()) {
            int levelSize = q.size();  // 当前层的节点数
            vector<int> levelNodes;    // 存储当前层的节点值
            
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                
                levelNodes.push_back(node->val);
                
                // 左子节点入队
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                // 右子节点入队
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            
            result.push_back(levelNodes);
        }
        
        return result;
    }
};

// 测试代码
int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    Solution sol;
    vector<vector<int>> result = sol.levelOrder(root);
    
    // 输出层序遍历结果
    for (auto& level : result) {
        for (auto& val : level) {
            cout << val << " ";
        }
        cout << endl;
    }
    // 输出：
    // 3 
    // 9 20 
    // 15 7 
    
    return 0;
}