「C/C++」C++ STL容器库 之 std::queue 队列容器

std::queue容器详解

上图截取自黑马C++教程

1. 引用头文件

在C++中，要使用std::queue容器，首先需要包含<queue>头文件。这个头文件提供了std::queue类的定义，该类是一个容器适配器，提供了基于队列（FIFO, First-In-First-Out）的数据结构。

#include <queue>

2. 函数构造与对象初始化

std::queue类模板的构造函数有几种形式，包括默认构造函数、通过底层容器对象进行构造、使用std::allocator对象作为参数进行构造等。最常用的构造函数是默认构造函数和通过底层容器对象进行构造。

#include <iostream>
#include <queue>
#include <deque>
#include <list>

int main() {
    // 默认构造函数，创建一个空的队列
    std::queue<int> intQueue;

	// 拷贝构造
    std::queue<int> c2(intQueue);

    // 使用std::deque作为底层容器的队列
    std::deque<int> dequeElements = {1, 2, 3, 4, 5};
    std::queue<int, std::deque<int>> dequeQueue(dequeElements);

    // 使用std::list作为底层容器的队列
    std::list<int> listElements = {10, 20, 30, 40};
    std::queue<int, std::list<int>> listQueue(listElements);

    // 输出队列大小
    std::cout << "Size of intQueue: " << intQueue.size() << std::endl;
    std::cout << "Size of dequeQueue: " << dequeQueue.size() << std::endl;
    std::cout << "Size of listQueue: " << listQueue.size() << std::endl;

    return 0;
}

注意：虽然std::queue可以使用不同的底层容器（如std::deque和std::list），但通常默认使用std::deque，因为它在大多数情况下提供了更好的性能。

3. 元素访问

std::queue提供了front()和back()成员函数来访问队列中的元素。front()返回队列中第一个元素的引用（即最早进入队列的元素），而back()返回队列中最后一个元素的引用（即最晚进入队列的元素）。如果队列为空，调用这些函数会导致未定义行为。

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // 访问队列中的第一个元素
    int frontElement = myQueue.front();
    std::cout << "Front element: " << frontElement << std::endl;

    // 访问队列中的最后一个元素
    int backElement = myQueue.back();
    std::cout << "Back element: " << backElement << std::endl;

    return 0;
}

4. 迭代器

std::queue不支持普通的迭代器，因为它是一个适配器，其设计目的是提供队列的行为，而不是提供遍历功能。然而，可以通过底层容器的迭代器来间接访问队列元素，但这通常不是推荐的做法，因为它破坏了队列的抽象。

#include <cassert>
#include <iostream>
#include <queue>
 
int main()
{
    std::queue<int> q;
 
    q.push(0); // 后端推入 0
    q.push(1); // q = 0 1
    q.push(2); // q = 0 1 2
    q.push(3); // q = 0 1 2 3
 

    // 打印并移除所有元素。
    // 注意 std::queue 并不支持 begin()/end()，因而不能使用范围 for 循环。
    std::cout << "q: ";
    for (; !q.empty(); q.pop())
        std::cout << q.front() << ' ';
    std::cout << '\n';
}

5. 容器

std::queue本身不拥有数据存储，而是利用其他容器（如std::deque、std::list）作为其底层，来存储和管理元素。默认情况下，std::queue使用std::deque作为其底层容器。

#include <algorithm>
#include <iostream>
#include <queue>
 
int main()
{
    std::cout << std::boolalpha;
 
    std::queue<int> queue;
 
    std::cout << "起初, queue.empty(): " << queue.empty() << '\n';
 
    queue.push(42);
    std::cout << "添加元素后, queue.empty(): " << queue.empty() << '\n';
}

6. 修改器

std::queue提供了push()和pop()成员函数来修改队列中的元素。push()函数在队列的末尾插入元素，而pop()函数移除队列的第一个元素。

#include <iostream>
#include <queue>

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

    // 向队列中添加元素
    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    // 移除队列中的第一个元素
    myQueue.pop();

    // 访问并打印队列中的元素
    std::cout << "Front element after pop: " << myQueue.front() << std::endl;
    std::cout << "Back element after pop: " << myQueue.back() << std::endl;

    return 0;
}

7. 元素比较

std::queue本身不提供元素比较功能，但可以通过比较队列中的元素来间接实现元素比较。需要注意的是，在比较之前应确保队列不为空，并且比较的元素是有效的。

#include <iostream>
#include <queue>

int main() {
    std::queue<int> queue1;
    std::queue<int> queue2;

    queue1.push(10);
    queue2.push(20);

    if (!queue1.empty() && !queue2.empty()) {
        if (queue1.front() < queue2.front()) {
            std::cout << "queue1 front is less than queue2 front" << std::endl;
        } else {
            std::cout << "queue1 front is greater than or equal to queue2 front" << std::endl;
        }
    }

    return 0;
}

总结与应用

std::queue是一个简单且易于使用的容器适配器，提供了基于队列的数据结构，适用于许多不同的编程场景。它的主要优点是先进先出（FIFO）的特性，使得它在实现任务调度、广度优先搜索（BFS）算法、消息队列、生产者-消费者问题等需要FIFO数据结构的场景中非常有用。

在使用std::queue时，需要注意以下几点：

• 默认情况下，std::queue使用std::deque作为其底层容器，但也可以根据需要选择其他容器（如std::list）。
• 在调用front()、back()、pop()等函数之前，应确保队列不为空，以避免未定义行为。
• std::queue不支持迭代器，因此不能通过迭代器来遍历队列元素。如果需要遍历队列，可以考虑使用其他容器（如std::deque或std::list），并在需要时将其转换为队列。