STL专项：deque 双端队列

deque

deque是queue的升级版，全称为double-ended queue，队头和队尾都支持入队和出队，同时还支持遍历，所有操作时间复杂度均为O(1)。

声明

deque<int> dq;

常用操作

dq.push_front(x);//在队头插入元素

dq.push_back(x);//在队尾插入元素

dq.front();//获取队头元素

dq.back();//获取队尾元素

//获取队列大小

dq.size();

//判断队列是否为空

dq.empty();

//以下两个操作注意判断队列非空

dq.pop_front();//弹出队头

dq.pop_back();//弹出队尾

遍历deque

//用迭代器遍历

for(auto it = dq.begin(); it != dq.end(); it ++){

cout << *it << ' ';

}

//用基于范围的for循环

for(const auto &val : dq) cout << val << ' ';

一起写论文

一起写论文 | 星码StarryCoding 算法竞赛新手村

代码

删除前一定要记得判空！！！

#include<bits/stdc++.h> using namespace std; void solve(){ int N;cin>>N; deque<string> dq; for(int i=1;i<=N;i++){ char a,b;cin>>a>>b; if(b=='w'){ string s;cin>>s; if(a=='f'){ dq.push_front(s); }else{ dq.push_back(s); } }else if(b=='d'){ if(!dq.size()) continue; if(a=='f') dq.pop_front(); else dq.pop_back(); } } if(dq.empty()) cout<<'#'; else{ while(dq.size()){ cout<<dq.front(); dq.pop_front(); } } } int main(){ int _;cin>>_; while(_--) solve(); return 0; }