双端队列(deque)和双端栈(double ended stack)
组别：提高组
难度：5
双端队列(deque)和双端栈（Double-ended Stack）是一种特殊的数据结构，它允许在两端进行操作。双端栈结合了栈和队列的特性，使得在头部和尾部都可以进行插入和删除的操作，适用于需要双向访问的场景。
常用函数：
| 成员函数 | 功能 |
| dq.front() | 返回双端队列中的第一个元素的引用 |
| dq.back() | 返回双端队列中的最后一个元素的引用 |
| dq.push_front(value) | 头部添加元素 |
| deq.push_back(value) | 末尾添加元素 |
| deq.insert(pos, value) | 在pos迭代器之前插入一个值为value的元素 |
| deq.insert(pos, other.begin(), other.end()) | // pos之前插入一段范围 |
| deq.pop_front() | 头部删除元素 |
| deq.pop_back() | 末尾删除元素 |
| dq.assign(n, x); | 用n个x替换当前内容 |
| dq.assign(begin, end); | 用范围内容替换当前内容 |
| dq.assign({initializer list}); | 初始赋值initializer list |
| dq.erase(pos); | 删除pos位置元素 |
| dq.erase(start, end); | 删除[start, end)区间元素 |
| dq.clear(); | 清空所有元素 |
| emplace(pos, args…) | 在迭代器 pos 位置前构造元素 |
| emplace_front(args…) | 在前端构造元素 |
| emplace_back(args…) | 在后端构造元素 |
deque的C++实现示例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /**************************************************************** * 代码作者: Alex Li * 创建时间: 2025-07-06 18:10:04 * 最后修改: 2025-07-09 16:50:34 * 文件描述: 双端队列 ****************************************************************/ #include <iostream> #include <deque> #include <iterator> using namespace std; int main(){ deque<int> a,b; // a.resize(10); for(int i=0;i<=5;i++){ // a[i]=i; a.push_back(i); } cout<<a[0]<<' '; a.push_front(2); cout<<a[0]<<'\n'; if(!a.empty())cout<<"no empty"<<'\n'; for(auto &it:a){ cout<<it<<' '; } cout<<'\n'; a.erase(a.begin()+1); //a.erase(first,last); a.insert(a.begin()+3,9); a.insert(a.begin()+4,2,10); //a.insert(pos,first,last); //a.inser(pos,init_list); for(auto it=a.begin();it!=a.end();it++){ cout<<*it<<' '; } cout<<'\n'; //b.assign(4,6); b.assign({1,2,3}); // b.assign(a.begin(),a.end()); for(int i=0;i<b.size();i++){ cout<<b[i]<<' '; //cout<<b.at(i)<<' '; } a.pop_front(),a.pop_back(); cout<<'\n'; cout<<a.front()<<' '<<a.back(); } |