C++queue介绍及详细使用示例（源代码）

deque（双端队列）是C++标准模板库（STL）中的一个容器，它支持在序列的两端（前端和后端）快速插入和删除元素。deque 通常在需要快速地在两端添加或移除元素，但又不想承受像 list 那样的额外开销时使用。 deque的主要特性： 双端操作：deque 允许在序列的前端和后端快速插入和删除元素。 内部引用：deque 通常不会将所有元素都存储在连续的内存块中，而是将元素存储在多个较小的、独立的内存块中，并通过内部引用机制来管理这些内存块。这使得 deque 在进行前端插入和删除操作时比 vector 更高效，因为 vector 在这些操作时需要移动所有元素。 迭代器：deque 支持双向迭代器，可以向前或向后遍历元素。 随机访问：尽管 deque 的元素不是连续存储的，但它仍然支持通过索引直接访问元素（类似于 vector）。 ### C++ deque（双端队列）介绍及详细使用示例 #### 一、deque简介 deque 是 C++ 标准模板库（STL）中的一个重要容器类型，它结合了数组和链表的优点，能够在序列的两端高效地插入和删除元素。与标准的 vector 相比，deque 在进行前端插入和删除时更为高效，因为不需要移动大量的数据。下面将详细介绍 deque 的主要特性和基本用法。 #### 二、deque的主要特性 1. **双端操作**：deque 支持在序列的前端和后端快速插入和删除元素。这使得 deque 成为处理需要频繁进行前后端操作的数据结构的理想选择。 2. **内部引用机制**：deque 不会将所有元素都存储在一个连续的内存块中，而是将它们分散存储在多个较小的、独立的内存块中，并通过内部引用机制来管理这些内存块。这种方式使得 deque 在前端插入和删除元素时更高效，因为不需要像 vector 那样移动整个内存块中的元素。 3. **双向迭代器**：deque 支持双向迭代器，这意味着可以从前向后或者从后向前遍历 deque 中的元素。 4. **随机访问**：虽然 deque 的元素不是连续存储的，但它仍然支持通过索引直接访问元素。这意味着可以像使用 vector 一样使用下标运算符 [] 来访问和修改 deque 中的元素。 #### 三、deque的基本用法 下面通过一个简单的 C++ 示例代码来展示 deque 的基本用法： ```cpp #include <iostream> #include <deque> int main() { // 创建一个空的 deque<int> std::deque<int> myDeque; // 向 deque 的两端添加元素 myDeque.push_back(1); // 在后端添加元素 1 myDeque.push_front(0); // 在前端添加元素 0 // 使用迭代器遍历 deque std::cout << "遍历 deque 的元素: "; for (std::deque<int>::iterator it = myDeque.begin(); it != myDeque.end(); ++it) { std::cout << *it << " "; // 输出当前迭代器指向的元素 } std::cout << std::endl; // 换行 // 使用范围基于的 for 循环遍历 deque（C++11 及更高版本） std::cout << "使用范围基于的 for 循环遍历 deque 的元素: "; for (int num : myDeque) { std::cout << num << " "; // 输出每个元素 } std::cout << std::endl; // 换行 // 修改 deque 中的元素（通过索引） myDeque[1] = 100; // 修改索引为 1 的元素为 100（注意：索引从 0 开始） // 输出修改后的 deque std::cout << "修改后的 deque: "; for (int num : myDeque) { std::cout << num << " "; // 输出每个元素 } std::cout << std::endl; // 换行 // 在 deque 的两端删除元素 myDeque.pop_front(); // 删除前端的元素 myDeque.pop_back(); // 删除后端的元素 // 输出删除元素后的 deque std::cout << "删除元素后的 deque: "; for (int num : myDeque) { std::cout << num << " "; // 输出每个元素 } std::cout << std::endl; // 换行 // 获取 deque 的大小 std::cout << "deque 的大小: " << myDeque.size() << std::endl; // 输出 0 return 0; } ``` ### 四、注意事项 1. **随机访问性能**：虽然 deque 支持通过索引直接访问元素，但由于其内部实现方式，在进行大量随机访问时，vector 通常会比 deque 更高效，因为 vector 的元素是连续存储的。 2. **空间分配**：deque 在创建时会预先分配一定的内存空间来存储元素。当需要更多的内存空间时，deque 会重新分配更大的内存空间并复制已有的元素到新的内存区域，这个过程可能会导致一定的性能开销。 3. **效率比较**：对于频繁的前端插入和删除操作，deque 比 vector 和 list 更加高效；但对于频繁的中间插入和删除操作，list 通常更加高效。 4. **迭代器失效**：在 deque 中进行插入和删除操作时，可能会影响其他迭代器的有效性。特别是当插入或删除操作导致 deque 重新分配内存时，所有迭代器都将失效。 通过以上内容，我们了解了 deque 的主要特点和基本使用方法。在实际编程中，根据具体的应用场景选择合适的容器类型是非常重要的。