当前位置：首页 > news >正文

C++ - deque

news 2025/6/29 6:56:20

博客主页：【夜泉_ly】
本文专栏：【C++】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

文章目录

💡双端队列简介
- 1. 基本特性
- 2. 与其他容器的比较
- - 与 `vector`
  - 与 `list`
- 3. 中控数组的设计
- 4. 优缺点
- - 优点
  - 缺点
- 5. 应用场景
- 6. 结论

💡双端队列简介

双端队列（deque）是一种特殊的容器，它允许在两端进行插入和删除操作。
虽然它的名称中有“队列”二字，但它的行为并不完全符合传统队列的先进先出（FIFO）原则，因此严格来讲，双端队列不是队列。
下面将介绍双端队列的特性、与其他容器的比较、以及它的应用场景。

1. 基本特性

双端队列是一种支持在头部和尾部同时进行插入和删除操作的容器。

在这里插入图片描述
观察它的接口，可以看见它的接口设计允许：

在头部和尾部进行高效的插入和删除操作。
进行随机访问，支持通过下标访问任意元素。

⭕虽然 deque 看起来非常灵活且功能强大，但在实际使用中，仍需对其存在的潜在问题保持警惕。
这也解释了为什么许多数据结构书籍更多地介绍列表（list）和向量（vector），而不单独强调双端队列。

2. 与其他容器的比较

首先来回顾一下顺序表和链表的区别：

特性	链表（list）	顺序表（vector）
可任意位置插入删除	是	否（头、中部插入效率低）
按需申请释放	是	需处理扩容问题
支持随机访问	否	是（可用下标随机访问）

与 `vector`

插入和删除效率：
deque 在头部和尾部的插入和删除操作效率较高，而 vector 在这些操作中性能较差。
扩容问题：
扩容方面，deque更优秀。
vector 在扩容时需要将所有数据拷贝到一个新数组中，然后释放旧的数组，这在元素较多时会造成性能损失。
相比之下，deque 使用多个小数组，扩容时只需添加新的数组，避免了大规模的数据拷贝。
随机访问：
vector的效率更高。因为双端队列随机访问时要计算位置。

与 `list`

插入和删除效率：
list更优秀。
deque 在头部和尾部的插入和删除操作效率较高，而在中间插入删除性能较差。因为需要保证小数组的长度，不能直接扩容，以免加大随机访问时的计算量，大大降低随机访问的效率。
扩容问题：
扩容方面，deque更优秀。
list虽然不会浪费空间，但大量分散的节点会让内存碎片化。而deque使用小数组极大改善了这个问题。
随机访问：
deque更优。因为list根本不支持随机访问🤣。

双端队列在一定程度上结合了两者的优点，允许在两端高效插入和删除，同时也支持下标随机访问。但是在单方面上不如两者极致。

3. 中控数组的设计

在 deque 的实现中，数据通常是以多个小数组的形式存储。这些小数组被一个称为中控数组（或指针数组）的结构连接在一起。中控数组从中间位置开始放置小数组，提供了更灵活的内存管理。由于中控数组只存储小数组的指针，扩容时只需拷贝指针，避免了移动实际数据的开销。

4. 优缺点

优点

高效支持头部和尾部的插入与删除。
随机访问性能良好，适合频繁需要访问数据的场景。

小数组长度固定，计算位置时，先减去头或尾数组的数据个数，然后一除就能得到位置。
适合用作 stack 和 queue 的默认容器。C++ -stack、queue

适合用于需要频繁在两端插入和删除数据的场景

缺点

在中间位置插入或删除操作的效率较低，因为 deque 不支持单独小数组的大小调整。
随机访问时的计算不如 vector 高效。

但如果数据量较小其实还好。

下面这段代码，对vector和deque进行排序，用于比较vector和deque在随机访问的效率上的区别：

void TestOP()
{srand(time(0));const int N = 10000000;vector<int> v;deque<int> dq;for (int i = 0; i < N; ++i){int tmp = rand();v.push_back(tmp);dq.push_back(tmp);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();printf("vector:%d\n", end1 - begin1);printf("deque:%d\n", end2 - begin2);
}
int main()
{TestOP();return 0;
}