C++ - deque

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

💡双端队列简介

双端队列（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;
}

运行结果如下图：

可以看到，在数据量较大时，deque随机访问的效率不如vector。

5. 应用场景

由于其灵活性和效率，deque 特别适合用于需要频繁在两端插入和删除数据的场景，因此，它是实现栈和队列的一个理想容器，提供了在高频数据操作时的良好性能。
这就是为什么，库中stack和queue的默认容器是deque：

6. 结论

双端队列是一种强大且灵活的数据结构，能够在多种情况下满足开发者的需求。尽管它在特定情况下可能不如列表和向量广泛使用，但了解其特性和应用场景，可以帮助开发者在设计高效算法时做出更明智的选择。

---

希望本篇文章对你有所帮助！并激发你进一步探索编程的兴趣！
本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！