csp信奥赛C++标准模板库STL（2）：deque的使用详解
一、deque基本概念
1.1 什么是deque
- deque（double-ended queue，双端队列）是一种可以在两端进行高效插入和删除操作的序列容器
- 结合了vector和list的优点：支持随机访问（类似vector），同时在两端有高效的插入/删除（类似list）
1.2 内部实现原理
// deque的内部结构可以理解为：// 由多个固定大小的数组块（buffer）组成// 通过一个中央控制器（map）来管理这些数组块二、deque的声明和初始化
2.1 头文件和声明
#include<deque>usingnamespacestd;// 基本声明方式deque<int>dq1;// 空dequedeque<int>dq2(5);// 包含5个0deque<int>dq3(5,10);// 包含5个10deque<int>dq4={1,2,3,4,5};// 列表初始化// 从其他容器复制deque<int>dq5(dq4.begin(),dq4.end());deque<int>dq6(dq3);// 拷贝构造三、deque的核心操作
3.1 访问元素
deque<int>dq={1,2,3,4,5};// 随机访问（O(1)）cout<<dq[2]<<endl;// 访问索引2，输出3cout<<dq.at(2)<<endl;// 带边界检查，越界会抛出异常// 访问首尾元素cout<<dq.front()<<endl;// 1（首元素）cout<<dq.back()<<endl;// 5（尾元素）3.2 插入操作
deque<int>dq={1,2,3};// 头部插入（O(1)）dq.push_front(0);// dq: 0, 1, 2, 3// 尾部插入（O(1)）dq.push_back(4);// dq: 0, 1, 2, 3, 4// 指定位置插入（O(n)）autoit=dq.begin()+2;dq.insert(it,99);// dq: 0, 1, 99, 2, 3, 4// 批量插入dq.insert(dq.begin()+1,3,88);// 在位置1插入3个88// 从其他容器插入vector<int>vec={111,222};dq.insert(dq.end(),vec.begin(),vec.end());3.3 删除操作
deque<int>dq={1,2,3,4,5,6};// 头部删除（O(1)）dq.pop_front();// 删除1，剩余：2,3,4,5,6// 尾部删除（O(1)）dq.pop_back();// 删除6，剩余：2,3,4,5// 指定位置删除（O(n)）autoit=dq.begin()+1;dq.erase(it);// 删除3，剩余：2,4,5// 删除区间（O(n)）dq.erase(dq.begin(),dq.begin()+2);// 删除前2个，剩余：5// 清空所有元素dq.clear();3.4 大小和容量
deque<int>dq={1,2,3};cout<<dq.size()<<endl;// 元素个数：3cout<<dq.empty()<<endl;// 是否为空：false// deque没有capacity()函数，因为它是动态分块的// 但可以调整大小dq.resize(5);// 调整为5个元素，新增元素为0dq.resize(2);// 调整为2个元素，删除多余元素四、迭代器使用
4.1 正向和反向迭代器
deque<int>dq={1,2,3,4,5};// 正向迭代for(deque<int>::iterator it=dq.begin();it!=dq.end();it++){cout<<*it<<" ";}// 反向迭代for(deque<int>::reverse_iterator rit=dq.rbegin();rit!=dq.rend();rit++){cout<<*rit<<" ";}// C++11范围for循环for(intnum:dq){cout<<num<<" ";}五、deque在信奥赛中的典型应用
5.1 滑动窗口最大值（单调队列）
// 题目：求每个长度为k的滑动窗口中的最大值vector<int>maxSlidingWindow(vector<int>&nums,intk){vector<int>result;deque<int>dq;// 存储下标for(inti=0;i<nums.size();i++){// 移除不在窗口内的元素if(!dq.empty()&&dq.front()<=i-k){dq.pop_front();}// 维护单调递减队列while(!dq.empty()&&nums[dq.back()]<nums[i]){dq.pop_back();}dq.push_back(i);// 当窗口形成时记录结果if(i>=k-1){result.push_back(nums[dq.front()]);}}returnresult;}5.2 队列优化BFS（双端队列BFS）
// 0-1 BFS：边权只有0和1时的最短路径vector<int>bfs01(intstart,vector<vector<pair<int,int>>>&graph){intn=graph.size();vector<int>dist(n,INT_MAX);deque<int>dq;dist[start]=0;dq.push_front(start);while(!dq.empty()){intu=dq.front();dq.pop_front();for(auto&[v,w]:graph[u]){if(dist[u]+w<dist[v]){dist[v]=dist[u]+w;if(w==0){dq.push_front(v);// 边权为0，加入队首}else{dq.push_back(v);// 边权为1，加入队尾}}}}returndist;}六、deque与其他容器的比较
| 特性 | deque | vector | list |
|---|---|---|---|
| 随机访问 | O(1) | O(1) | O(n) |
| 头部插入/删除 | O(1) | O(n) | O(1) |
| 尾部插入/删除 | O(1) | O(1)* | O(1) |
| 中间插入/删除 | O(n) | O(n) | O(1) |
| 内存连续性 | 部分连续 | 完全连续 | 不连续 |
| 迭代器失效 | 插入可能使所有迭代器失效 | 插入可能使所有迭代器失效 | 不影响其他迭代器 |
注：vector尾部插入均摊O(1)，但可能需要重新分配内存
七、性能特点和注意事项
7.1 性能特点
- 两端操作高效：
push_front()、pop_front()、push_back()、pop_back()都是O(1) - 随机访问高效：通过下标访问元素是O(1)
- 中间操作较慢：在中间插入删除是O(n)
7.2 注意事项
// 1. 迭代器失效问题deque<int>dq={1,2,3,4,5};autoit=dq.begin()+2;dq.push_front(0);// 可能导致所有迭代器失效！// 此时使用it是危险的// 2. 与算法库结合使用#include<algorithm>sort(dq.begin(),dq.end());// 可以排序reverse(dq.begin(),dq.end());// 可以反转// 3. 获取最大/最小值automax_it=max_element(dq.begin(),dq.end());automin_it=min_element(dq.begin(),dq.end());八、实战练习题
8.1 基础练习
- 实现一个支持前插入、后插入、随机访问的序列
- 使用deque实现栈和队列
8.2 中级练习
- 滑动窗口最大值/最小值
- 最大子数组和的滑动窗口版本
- 单调队列优化DP问题
8.3 高级应用
- 0-1 BFS解决最短路径问题
- 使用deque维护动态区间的最大值
- 实现一个支持在两端高效操作的缓存结构
总结
deque是信奥赛中非常实用的数据结构，特别适合需要同时从两端操作的问题。它的主要优势在于：
- 两端插入删除高效
- 支持随机访问
- 不需要预分配大量内存
在解决滑动窗口、单调队列、BFS优化等问题时，deque往往是最高效的选择。熟练掌握deque的使用，能让你在竞赛中写出更优雅、更高效的代码。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
