1.双端队列介绍双端队列(dequeue) 与vector很类似采用线性表顺序存储结构且支持随机访问即可以直接用下标来访问元素。但与vector有区别:deque采用分块的线性存储结构来存储数据每块的大小一般为512B将之称为deque块;所有的deque块使用一个map块进行管理每个map数据项记录各个deque块的首地址,所以允许较为快速的随机访问;即它不像vector 把所有的对象保存在一块连续的内存块而是采用多个连续的存储块并且在一个映射结构中保存对这些块及其顺序的跟踪这样的话deque块在头部和尾部都可以插入和删除,而不需要移动其他元素。插入元素时块的变化以push_back()在尾部插入为例deque 会先检查最后一块是否还有空闲位置最后一块未满直接把新元素写入最后一块的空闲位置无需新建块时间复杂度 O(1)最后一块已满deque 会新分配一个 deque 块约 512B把新元素放入新块的首个位置并在 map 中登记新块的首地址使其成为新的最后一块。此时 map 中记录的块数量 1但已有块中的元素不需要移动。push_front()在头部插入同理若最前面的块已满则新分配一个块作为新的首块元素放入其末尾位置并在 map 中登记。删除元素时块的变化以pop_back()在尾部删除为例删除后最后一块仍有元素直接删除该元素块保持不变删除后最后一块变空deque 会释放这块空块并从 map 中移除其记录让前一块成为新的最后一块。这样可及时回收内存避免空块长期占用。pop_front()在头部删除同理若首块被删空则释放该块并更新 map 中的首块记录。中间插入与删除使用insert()在中间erase()删除元素时deque 需要移动目标位置之后的元素来腾出或填补位置因此复杂度为 O(n)。若操作发生在靠近头部或尾部的块且该块有空位则只需在该块内部移动少量元素、用insert()在中间插入元素时deque 的目标是保持现有内存块的布局稳定而不是像两端插入那样通过增加新块来扩展容量。如果当前块已满‌deque 会将当前块中的部分元素‌移动‌到相邻的前一个或后一个块中从而在当前块腾出空间。‌连锁反应‌如果相邻的块也满了这种移动会像多米诺骨牌一样向最近的一端头部或尾部传递直到找到一个有空闲空间的块。2.双端队列基本用法2.1 dequeue的创建与vector类似dequeType d;2.2 dequeue常见用法操作含义a.push_back(e)在尾部插入元素e,会不断扩张队列a.push_front(e)在头部插入元素ea.pop_front()在头部删除数据a.pop_back()在尾部删除数据a.front()返回头部元素的引用a.back()返回尾部元素的引用a.at(i)返回下标i处元素的引用越界会抛出异常a[i]返回下标i处元素的引用越界行为未定义a.empty()判断队列是否为空空返回truea.size()返回容器中实际数据个数a.max_size()返回容器中最大数据的数量a.resize(num)重新指定队列的长度a.clear()清空所有元素a.insert(pos, e)在pos位置插入元素ea.erase(pos)删除pos位置的元素a.begin()返回指向首元素的迭代器a.end()返回指向尾元素后一位置的迭代器size() 与 max_size() 的区别a.size()返回容器中当前实际存储的元素个数。它反映的是队列此刻真正有多少个数据会随着push_back、pop_front等操作实时变化。a.max_size()返回容器理论上最多能容纳的元素数量。它由系统内存和容器类型共同决定是一个理论上限值与当前实际存了多少数据无关。