deque底层数据结构以及和queue的异同

文章目录

- 底层数据结构原理
- - 关键组成部分
  - 操作效率
  - 与其他容器的对比
  - 适用场景
  - C++ STL中的实现细节
  - 总结
- deque和queue的异同
- - 相同点
  - 不同点

deque（双端队列）是一种具有高效两端插入和删除操作的数据结构，常见于C++标准库（STL）和其他编程语言中。它的底层实现结合了数组和链表的优势，既支持高效的随机访问，又能在两端快速插入/删除元素。

底层数据结构原理

deque 的核心思想是分段连续存储：

使用多个固定大小的块（通常是数组）存储元素。
这些块通过一个中控器（通常是指针数组）连接，形成逻辑上的连续序列。

在这里插入图片描述

关键组成部分

中控器（Map）
- 一个动态分配的数组，每个元素是指向数据块的指针。
- 当需要扩展容量时，中控器会重新分配并调整指针。
数据块（Buffer）
- 固定大小的连续内存块（数组），存储实际元素。
- 每个块的大小通常是编译时确定的（如C++ STL中默认大小为512字节）。
迭代器（Iterator）
- 智能指针，封装了当前元素在哪个块、块内的偏移量等信息。
- 通过重载运算符（如 ++, --, []）实现透明的随机访问。

操作效率

操作	时间复杂度	说明
两端插入/删除	O(1)	仅需调整中控器和块内指针
随机访问	O(1)	通过中控器和块内偏移量直接计算
中间插入/删除	O(n)	需要移动元素
内存扩展	O(n)	重新分配中控器并复制指针

与其他容器的对比

容器	随机访问	两端插入/删除	中间插入/删除	内存布局
`vector`	O(1)	尾部O(1)*	O(n)	连续内存
`deque`	O(1)	O(1)	O(n)	分段连续
`list`	O(n)	O(1)	O(1)	离散节点

*注：vector 尾部插入在需要扩容时为O(n)。

适用场景

需要频繁在两端插入/删除元素（如队列、栈）。
需要随机访问，但插入/删除操作不集中在中间位置。
避免 vector 扩容时的元素复制开销。

C++ STL中的实现细节

以下是STL中 deque 的简化伪代码，展示其结构：

template<typename T>
class deque {
private:// 中控器：指针数组，每个元素指向一个数据块T** map;size_t map_size;  // 中控器大小// 数据块相关size_t block_size;  // 每个块的元素数量iterator start;     // 指向第一个元素的迭代器iterator finish;    // 指向最后一个元素的下一个位置的迭代器// 迭代器实现（简化）struct iterator {T** node;       // 当前块在map中的位置T* cur;         // 当前元素在块内的指针T* first;       // 块的起始位置T* last;        // 块的结束位置// 重载运算符实现随机访问iterator& operator++() { /* ... */ }iterator& operator--() { /* ... */ }T& operator*() { return *cur; }// 其他运算符重载...};
};

总结

deque 通过分段连续存储的方式，平衡了随机访问和两端操作的效率，适合需要高效双端插入/删除且偶尔随机访问的场景。其实现复杂度高于 vector 和 list，但在特定场景下能提供更优的性能。

deque和queue的异同

deque（双端队列）和queue（队列）都是常见的数据结构，它们既有相似之处，也有不同点，以下是具体分析：

相同点

都是线性数据结构：二者都按照元素的先后顺序进行存储和操作，元素之间存在着明确的线性关系。
都支持一定的基本操作：都提供了添加元素和删除元素的操作，例如在queue中通常有enqueue（入队）和dequeue（出队）操作，在deque中也有类似的向队列两端添加和删除元素的操作。

不同点

操作限制
- queue：遵循先进先出（FIFO）原则，元素只能从队尾插入，从队头删除，就像现实生活中的排队一样，先到的人先接受服务。
- deque：双端队列允许在队列的两端进行插入和删除操作，更加灵活，既可以像栈一样在一端进行插入和删除，也可以像队列一样在一端插入另一端删除。
底层实现
- queue：通常可以用链表或者数组来实现。当使用数组实现时，需要考虑数组的扩容和元素的移动等问题；使用链表实现时，虽然插入和删除操作在表头和表尾的时间复杂度为 $O (1)$ ，但可能会有一定的空间开销用于存储节点的指针。
- deque：一般采用动态数组或者链表来实现。以动态数组实现为例，它可以通过扩展数组的方式来适应元素的增加，并且能够高效地在两端进行插入和删除操作，通常通过维护头指针和尾指针来确定队列的边界。
应用场景
- queue：常用于需要按照顺序处理任务的场景，如消息队列、任务调度等。例如，在一个多线程的应用程序中，任务可以被放入一个队列中，然后工作线程按照任务进入队列的顺序依次取出并执行。
- deque：适用于需要在序列两端进行频繁插入和删除操作的场景。例如，在实现一个文本编辑器的撤销和重做功能时，可以使用deque来存储操作历史，方便在两端进行操作的添加和删除。