Team Queue（双端队列：deque）

题意

有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。
ENQUEUE：编号为X的人进入长队。
DEQUEUE：长队队首出队。
STOP：停止模拟。
对于每个DEQUEUE指令，输出出队的人的编号。

输入

输入文件中有一组或多组测试数据。
每组测试数据开始有t个团队。下面t行，每行的第一个数字代表这个团队人数，后面是这几个人的编号。编号为0到999999之间的一个整数。
每组测试数据以“STOP”结束。
输入以t==0时结束。
警告：一个测试用例可能包含最多200000（二十万）个命令，所以实现
团队的队列应该是有效的。

输出

对于每组测试数据，先打印一句"Scenario #k"，k是第几组数据。对于每一个"DEQUEUE"指令，输出一个出队的人的编号。每组测试数据后要换行，即使是最后一组测试数据。

样例输入

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

样例输出

Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001

这个题题意是有t个队伍要排成一队，排队的规则是：如果当前正在排的总的队伍中有该人的队友则插入到队友后面的那个位置，否则站到队尾，根据这个特点，最终要出队时的每个状态（也就是当前排成的）总的队伍中原队伍的人一定是在一起的（每队组成一段连续的区间），这样只要根据原来每队中第一个人进入总队伍的顺序一队一队地输出就行了，其中每队的成员输出时按进入总队伍的顺序输出(先进先出)，这样正好可以用双端队列实现。

双端队列：

#include<deque>
deque<int>dq;//定义一个int型的双端队列
双端队列的特点：队列的两端都可进行入队和出队操作

完整代码：

#include <bits/stdc++.h>
#define int long long
const int maxn=1e6+6;
using namespace std;
int t,n,vis[maxn];//vis[i]用来表示原队伍编号为i的队伍是否在总队伍中有人
deque<int>que[maxn];//que表示原来那t个队伍每次进队的人，que[i]根据进入总队伍的顺序依次保存第i个队伍中进入总队伍的人的编号
deque<int>teamque;//teamque表示那一个要排成的总的队伍（teamque中根据原来每队中第一个人进入总队伍的顺序依次保存原队编号）
map<int,int>id;//id[i]表示编号为i的人所处的队伍编号
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int c=0;
while(cin>>t&&t)
{
cout<<"Scenario #"<<++c<<endl;
memset(vis,0,sizeof(vis));
for(int i=0;i<maxn;i++)
que[i].clear();
teamque.clear();
id.clear();
for(int i=0;i<t;i++)
{
cin>>n;
for(int j=0;j<n;j++)
{
int x;
cin>>x;
id[x]=i;
}
}
string s;
while(cin>>s&&s!="STOP")
{
if(s=="ENQUEUE"){
int x;
cin>>x;
if(!vis[id[x]]){
teamque.push_back(id[x]);//如果总队伍中没有该人的队友，就把这个人先放到teamque再放到que；否则直接放到que
vis[id[x]]=1;
}
que[id[x]].push_back(x);
}
else{
int num=teamque.front();//出队时，从teamque中依次保存的编号为num的队伍开始输出
cout<<que[num].front()<<endl;
que[num].pop_front();
if(que[num].empty()){
teamque.pop_front();//当当前队伍全都从总队伍出队后，让当前队伍编号从teamque中移除，然后继续让下一个队伍出队
vis[num]=0;
}
}
}
cout<<endl;
}
}

最后

以上就是悲凉舞蹈为你收集整理的Team Queue（双端队列：deque）的全部内容，希望文章能够帮你解决Team Queue（双端队列：deque）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。