【CSP-J系列】双端队列
2026-07-01 11:45:08
发布于：浙江
44阅读
0回复
0点赞
前言
蒟蒻的markdown用的不好，轻喷。
正题
双端队列就像是普通队列的加强版，使用时要引入头文件 <deque> ，大家都知道，普通的队列只支持从队头入队与从队尾出队。
qu.push(x);//将x入队
qu.pop();//将现在的队尾出队
而双端队列支持队头/尾的出/入队（长难句），也就是四个操作。
dq.push_front(x);//将x从队头入队
dq.push_back(x);//将x从队尾入队
dq.pop_front();//将队头元素出队
dq.pop_back();//将队尾元素出队
打个比方，队列就像是一个马路，普通的是单行道，只能从一边进一边出，而双端队列就是一个双向的路，可以从南到北也可以从北到南。当然，队列中的一些操作在双端队列里也可以使用。
dq.empty();//判断双端队列是否为空
dq.size();//双端队列的元素个数
dq.front();//双端队列的队头
dq.back();//双端队列的队尾
注意： 在调用 front() 与 back() 时要记得判读队列是否为空，不然会RE。
双端队列的遍历
//用迭代器遍历
for (auto it = dq.begin();it != dq.end();it++)
{
cout<<*it<<" ";
}
//用基于范围的for循环
for (const auto &val : dq)
{
cout<<val<<" ";
}
其中的 auto 可以自动切换数据的类型，不用写 deque<int>::iterator 这么长一段。
这里提一嘴，其实 dq[1] 这样的写法也是可以的，但是不推荐大家用。凑字数
例题
B3656 【模板】双端队列 1，这道题数据有点恶心，大家看看循环里的过程就行，这里的list其实就是一个可以储存大数据的deque，讲完了这些我们来看代码。
#include <iostream>
#include <list>
#include <unordered_map>
using namespace syh;
unordered_map<int,list<long long>> de;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int q;
cin>>q;
while(q--)
{
string op;
cin>>op;
if(op=="pop_back")
{
int a;
cin>>a;
if(de.count(a)&&!de[a].empty())//判断队列是否为空
{
de[a].pop_back();
if(de[a].empty()) de.erase(a);
}
}
else if(op=="pop_front")
{
int a;
cin>>a;
if(de.count(a)&&!de[a].empty()) //判断队列是否为空
{
de[a].pop_front();
if(de[a].empty()) de.erase(a);
}
}
else if(op=="push_back")
{
int a, x;
cin>>a>>x;
de[a].push_back(x);
}
else if(op=="push_front")
{
int a, x;
cin>>a>>x;
de[a].push_front(x);
}
else if(op=="size")
{
int a;
cin>>a;
if(de.count(a))
{
cout<<de[a].size()<<"\n";
}
else cout<<"0\n";
}
else if(op=="front")
{
int a;
cin>>a;
if(de.count(a)&&!de[a].empty()) //判断队列是否为空
{
cout<<de[a].front()<<'\n';
}
}
else if(op=="back")
{
int a;
cin>>a;
if(de.count(a)&&!de[a].empty()) //判断队列是否为空
{
cout<<de[a].back()<<"\n";
}
}
}
}
这道题就是考察同学们对双端队列的函数使用，对于每个操作按照题目上写就可以了。
后记
感谢@古希腊掌管AC和WA的神帮忙修正内容/bx
全部评论 7
我在把MST那个帖子搬到目录的时候发现这个例题就没写，然后补了一个还没过，一个点MLE气死了，后面看了下讨论发现
要开list2026-07-01 来自 浙江
0
有帮助，赞一个