deque queue

`deque` 和 `queue` 是 C++ 标准库中两个非常重要的容器或容器适配器。它们的功能和使用场景有所不同，下面详细介绍两者的区别、用法以及相关问题。 --- ### **1. deque（双端队列）** #### **(1) 定义** - `std::deque` 是一个双端队列（double-ended queue），允许在两端高效地插入和删除元素。 - 它支持随机访问迭代器，因此可以像数组一样通过索引访问元素。 #### **(2) 特点** - 在两端插入或删除元素的时间复杂度为 O(1)。 - 支持动态扩展，但不保证连续的内存存储。 - 提供了类似 `std::vector` 的功能，但更适合需要频繁在两端操作的场景。 #### **(3) 常用操作** ```cpp #include <iostream> #include <deque> using namespace std; int main() { deque<int> dq = {1, 2, 3}; // 在前端插入 dq.push_front(0); // 在后端插入 dq.push_back(4); // 访问元素 cout << "Front: " << dq.front() << endl; // 输出 0 cout << "Back: " << dq.back() << endl; // 输出 4 // 删除元素 dq.pop_front(); // 删除前端元素 dq.pop_back(); // 删除后端元素 // 遍历 for (int i : dq) { cout << i << " "; // 输出 1 2 3 } return 0; } ``` --- ### **2. queue（队列适配器）** #### **(1) 定义** - `std::queue` 是一个队列适配器，基于其他容器（如 `std::deque` 或 `std::list`）实现。 - 它遵循 FIFO（先进先出）原则，只允许在一端插入，在另一端删除。 #### **(2) 特点** - 只提供了有限的操作接口：`push`（入队）、`pop`（出队）、`front`（访问队首元素）、`back`（访问队尾元素）和 `empty`/`size`。 - 不支持随机访问，也不能直接遍历。 #### **(3) 常用操作** ```cpp #include <iostream> #include <queue> using namespace std; int main() { queue<int> q; // 入队 q.push(1); q.push(2); q.push(3); // 访问队首元素 cout << "Front: " << q.front() << endl; // 输出 1 // 出队 q.pop(); cout << "New Front: " << q.front() << endl; // 输出 2 // 检查是否为空 if (!q.empty()) { cout << "Queue is not empty" << endl; } // 获取队列大小 cout << "Size: " << q.size() << endl; // 输出 2 return 0; } ``` --- ### **3. deque 和 queue 的区别** | 特性 | `deque` | `queue` | |--------------------|-------------------------------------------|------------------------------------------| | 数据结构类型 | 容器 | 容器适配器 | | 插入/删除位置 | 两端均可 | 仅一端插入，另一端删除 | | 随机访问 | 支持（通过索引访问） | 不支持 | | 底层实现 | 动态分配的块 | 默认基于 `std::deque` 实现 | | 使用场景 | 需要在两端频繁操作的场景 | 遵循 FIFO 原则的场景 | --- ### **4. 解释** #### **(1) deque 的适用场景** - 当需要在两端频繁插入或删除元素时，`deque` 是更好的选择。 - 如果需要随机访问元素，`deque` 也比 `queue` 更灵活。 #### **(2) queue 的适用场景** - 当只需要实现简单的队列功能（FIFO）时，`queue` 提供了更简洁的接口。 - 由于 `queue` 是适配器，其功能受限，适合不需要复杂操作的场景。 --- ### **5. 总结** `deque` 和 `queue` 虽然都可以用于队列操作，但它们的设计目标和适用场景不同。`deque` 是一个功能强大的容器，支持随机访问和两端操作；而 `queue` 是一个简单的适配器，专注于 FIFO 操作。 ---