STL-deque双端队列

STL-deque学习了解

deque（double-ended queue）名为双端队列，deque 是具有动态大小的序列容器，可以在两端进行扩展或者收缩。它具有 [vector](STL-vector顺序表 | HappyLadySauce) 和 [list](STL-list 链表 | HappyLadySauce) 相结合的功能，最早 deque 的出现是为了取代 [vector](STL-vector顺序表 | HappyLadySauce) 和 [list](STL-list 链表 | HappyLadySauce) 但是结果不尽人意。

deque 相比 [vector](STL-vector顺序表 | HappyLadySauce) 极大地缓解了扩容问题和头插头删问题，但是它的 [] 运算符效率很低，这就导致了 deque 中间部分数据的读写效率低。

deque 相比 [list](STL-list 链表 | HappyLadySauce) 它可以支持 [] 运算符进行下标访问，而且 deque 的内存空间是多段连续的，对 CPU 的高速缓存来说效率不错，但是中间段插入删除效率很低。

deque 的物理结构

那么 deque 的物理结构是怎样支持它做到这些功能的呢？

deque 有一个中控（指针数组）用于存储指向数据段的指针，deque 中存在多段数据段，每段数据段（buff）的长度都相同，并且每一段的数据段内存空间是连续的。deque 的结构就像是一个二维数组。

deque 的实现结构远比它的物理结构复杂，图中上半部分是实现结构，下半部分是物理结构。可以看到 deque 的迭代器封装了 4 个指针，cur 用于指向数据段中最新元素，first 用于指向数据段的开始，last 用于指向数据段的末尾，node 则是指向中控中数据段的位置。

同时 deque 的头尾操作比较特殊。deque 的头插是倒着插入的，举个例子：

我们需要头插入两个数据，第一次头插应该插入到下标为 3 的位置，第二次头插应该插入到下标为 2 的位置。

相似的 deque 的尾插是顺着插入的：

我们需要尾插入两个数据，第一次头插应该插入到下标为 8 的位置，第二次头插应该插入到下标为 9 的位置。

deque 的致命问题

deque 中要是涉及在其中大量访问元素那一定是一场灾难，头尾还好说，中间区域那就是难透了。在 deque 中我们需要查找下标为 i 的元素，首先在头数据段中查找，如果没有则 i -= headSize（头部元素长度） 再 i / numberSize（数据段长度） 得出 i 具体在哪个数据段，然后再执行 i % numberSize（数据段长度） 得出 i 在数据段中的具体位置。

这个过程相比 [list](STL-list 链表 | HappyLadySauce) 和 [vector](STL-vector顺序表 | HappyLadySauce) 的访问操作繁琐了很多，这也就是 deque 操作元素效率低下的原因，所以 deque 容器我们使用得很少。

那么 deque 这个容器现在有什么存在的意义呢？因为 deque 的头尾操作效率还可以，而且内存空间相对 [list](STL-list 链表 | HappyLadySauce) 更加的连续，常用于需要频繁头尾操作的场景，比如说：作为 stack（栈） 和 queue（队列） 的底层容器。

deque 总结

deque 结合了 [vector](STL-vector顺序表 | HappyLadySauce) 和 [list](STL-list 链表 | HappyLadySauce) 的部分特性，支持随机访问（通过[]运算符），但中间部分的插入和删除效率较低。

deque 的优势：

• 多段连续内存：deque由多个固定大小的内存块（数据段）组成，这些数据段通过一个中控指针数组管理。
• 高效的头尾操作：支持在头部和尾部快速插入和删除元素，时间复杂度为O(1)。
• 随机访问支持：通过[]运算符可以随机访问元素，尽管效率不如[vector]([STL-vector顺序表 | HappyLadySauce](https://www.happyladysauce.cn/STL-vector%E9%A1%BA%E5%BA%8F%E8%A1%A8_C++_STL/))，但优于[list]([STL-list 链表 | HappyLadySauce](https://www.happyladysauce.cn/STL-list%E9%93%BE%E8%A1%A8_C++_STL/))。
• 内存连续性：相比[list]([STL-list 链表 | HappyLadySauce](https://www.happyladysauce.cn/STL-list%E9%93%BE%E8%A1%A8_C++_STL/))，deque的内存空间相对更连续，对CPU缓存更友好。

deque 的劣势：

• 中间操作效率低：在deque的中间部分插入或删除元素效率较低，因为需要跨多个数据段操作。
• 随机访问效率低：虽然支持随机访问，但访问中间元素时需要先定位到具体的数据段，效率不如[vector]([STL-vector顺序表 | HappyLadySauce](https://www.happyladysauce.cn/STL-vector%E9%A1%BA%E5%BA%8F%E8%A1%A8_C++_STL/))。

deque 是一种功能强大的STL容器，适合在需要频繁头尾操作的场景中使用。它结合了 [vector](STL-vector顺序表 | HappyLadySauce) 和 [list](STL-list 链表 | HappyLadySauce) 的优点，但在中间操作和随机访问效率上有所不足，适用于需要频繁在头部和尾部插入或删除元素的场景，例如实现队列（queue）和栈（stack）的底层容器。