std::queue

std::queue (队列) 和 std::stack 类似，也是 C++ 标准库中的一个容器适配器 (Container Adapter)。它将底层容器的功能限制在一个特定的访问模式上，以实现 FIFO (First-In, First-Out，先进先出) 的数据结构。

想象一下排队等候的队伍：第一个进入队伍的人也是第一个离开队伍的人。在 std::queue 中，元素从尾部（Back）进入，从头部（Front）离开。

1. 引入

#include <queue>

2. 存储方式与底层容器

std::queue 通过封装一个底层容器 (Underlying Container) 来存储数据。它只暴露了符合队列（FIFO）操作的方法：

入队 (Push)： 插入元素到队列的尾部（对应底层容器的 push_back()）。
出队 (Pop)： 移除队列的头部元素（对应底层容器的 pop_front()）。
查看 (Front/Back)： 访问头部/尾部元素。

默认底层容器：如果创建 std::queue 时不指定，它默认使用 std::deque<T>。

可选底层容器：底层容器必须同时支持在头部（前端）移除元素（pop_front()）和在尾部（后端）添加元素（push_back()）。

满足这些要求的标准容器有：

std::deque<T> (默认)：通常是最佳选择，因为它在两端操作（push_back 和 pop_front）都非常高效且 $O(1)$$。
std::list<T>：如果元素类型不可复制，或者需要频繁地插入/删除，这也是一个合适的选择，操作复杂度也是 $O(1)$$。

注意：std::vector<T> 不能作为 std::queue 的底层容器，因为它不支持高效地从头部移除元素（pop_front），std::vector 的 erase(begin()) 操作是 $O(N)$ 的。

声明带指定底层容器的队列：

// 使用 list 作为底层容器
std::queue<int, std::list<int>> queue_list;

// 使用默认的 deque 作为底层容器
std::queue<int> queue_deque;

3. 常用方法 (操作)

std::queue 同样不提供迭代器，因此不能像 std::vector 或 std::list 那样遍历所有元素。

(1) 构造方法

queue(): 创建一个空的 std::queue。
```
std::queue<int> q;
```

queue(const Container& cont): 使用一个已存在的底层容器副本进行初始化。

std::deque<int> d = {10, 20, 30}; // 10 是 front, 30 是 back
std::queue<int> q(d);             // q 变为 {10, 20, 30}

(2) 大小函数

size_t size() const: 返回 std::queue 中元素的个数。
bool empty() const: 检查 std::queue 是否为空。若为空返回 true。

(3) 元素访问函数

std::queue 允许访问队列的头部和尾部元素。

reference front(): 返回队列头部元素（即最先进入队列的元素）的引用。调用前必须确保队列不为空。

reference back(): 返回队列尾部元素（即最近进入队列的元素）的引用。调用前必须确保队列不为空。

std::queue<int> q;
q.push(10); // q: {10}
q.push(20); // q: {10, 20}
std::cout << q.front(); // 输出 10
std::cout << q.back();  // 输出 20

(4) 增加函数 (入队)

void push(const T& value): 将元素 value 复制或移动到队列的尾部。
template<class... Args> void emplace(Args&&... args): 在队列的尾部就地构造一个元素。这是首选的入队方式。
```
std::queue<std::string> q;
q.push("Apple"); // 尾部插入
q.emplace("Banana"); // 尾部就地构造
```
template<container-compatible-range R> void push_range(R&& rg) (C++23): 将一个范围（range）内的所有元素插入到队列的尾部。

(5) 删除函数 (出队)

void pop(): 移除队列头部的元素。此函数不返回被移除的元素。调用前必须确保队列不为空。

std::queue<int> q;
q.push(10);
q.push(20); // q: {10, 20}

// 要取出元素 10，需要两步操作：
int oldest = q.front(); // 访问头部 (10)
q.pop();                // 移除头部 (10)，q 变为 {20}

(6) 交换

void swap(queue& other): 交换两个 std::queue 的内容。

4. 示例 (FIFO 原则)

通过一个简单的例子来演示 FIFO 的工作原理：

#include <iostream>
#include <queue>

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

    // 入队 (Enroll)
    my_queue.push(100); // 100 先进
    my_queue.push(200);
    my_queue.push(300); // 300 后进

    std::cout << "队列头部 (Front/First-in): " << my_queue.front() << std::endl; // 输出 100
    std::cout << "队列尾部 (Back/Last-in): " << my_queue.back() << std::endl;   // 输出 300

    std::cout << "--------------------" << std::endl;

    // 出队 (Serve)
    while (!my_queue.empty()) {
        std::cout << "服务并移除: " << my_queue.front() << std::endl;
        my_queue.pop();
    }

    // 元素的移除顺序为 100, 200, 300，严格遵循先进先出。
    return 0;
}

输出:

队列头部 (Front/First-in): 100
队列尾部 (Back/Last-in): 300
--------------------
服务并移除: 100
服务并移除: 200
服务并移除: 300

Keyboard shortcuts

Note of C++