概述
规则: 先进先出!!!
1.queue 的基本操作有:
入队,如例:q.push(x); 将x 接到队列的末端。
出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
访问队首元素,如例:q.front(),即最早被压入队列的元素。
访问队尾元素,如例:q.back(),即最后被压入队列的元素。
判断队列空,如例:q.empty(),当队列空时,返回true。
访问队列中的元素个数,如例:q.size()
注: queue不支持下表操作和迭代器访问!
2.题目背景
队列和优先级队列是大多数计算机科学家都知道的数据结构
。但是团队队列却不被人熟知,尽管在生活中经常出现。比如,午餐时间的食堂门口的队列就是一个团队队列。在一个团队队列中,每个元素属于一个团队。如果一个元素进入一个队列,它首先从头到尾地搜寻这个队列——检查是否它的队友(在同一个团队称之为队友)也在这个队列里。如果有,它就排在它队友的后面(:-D就是插队咯~~)。如果没有,它就排在整个队列的最后,成为新的最后一名(/(ㄒoㄒ)/~真是不幸)。在普通队列中出队是这样的:元素从头到尾的被处理,按他们出现在团队队列里的顺序。你的任务是写一个程序模拟这样一个团队队列。
输入
输入文件会包含一个或多个测试样例。每一个测试样例由代表团队数量的t(1<=t<=1000)开始。然后t只团队描述如下,每一个团队由一个表示元素个数的数字,以及每个元素组成。元素属于整型,并且范围在0到999999(一百万减一)之间。一个团队可能有多达1000个元素。最后,指令列表如下。有三种不同的指令:ENQUEUE x——x进入团队队列。DEQUEUE x——处理第一个元素并将其移除STOP——结束一个测试样例。当t是0时,输入终止。警告:一个测试样例可能多达200000(/(ㄒoㄒ)/~~二十万)条指令,所以团队队列的实现应该是有效率的:入队和出队都应该花费常数时间。
输出
对应每个测试样例,首先输出一行“Scenario #k”,其中k表示第几次测试。然后,每一个“DEQUEUE”指令打印包含出队的元素(单独占一行)。打印一空行在每一个测试样例之后,即使是最后一个测试样例。
例如:Sample Input
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
Sample Output
Scenario
#1
101
102
103
201
202
203
Scenario
#2
259001
259002
259003
259004
259005
260001
————————————————————————————————————————————————————
思路:排两个队列,主队列排队伍编号,副队列有n个,是每一个队伍内的队列,通过主队列首元素和副队列对应队伍首元素来出人!!注意空队列的处理!!!
代码:
#include <iostream>
#include<map>
#include<queue>
const int maxn=1100;
using namespace std;
int main()
{
int n;
int k=0;
while(cin>>n&&n)
{
k++;
cout<<"Scenario #"<< k<<endl;
map<int,int> team;
int N;
for(int i=0;i<n;i++)
{
cin>>N;
for(int j=1;j<=N;j++)//队伍编号
{
int person;
cin>>person;//输入个人号码
team[person]=i;//在映射里将个人号码对应队伍编号保存(因为下面输入的是个人编号,方便直接找到队伍)
}
}
queue<int> q,q2[maxn];//q是主队列,q2是副队列对应每一队
string operate;
while(1)
{
cin>>operate;//指令
if(operate[0]=='S')break;
if(operate[0]=='E')//入队
{
int x;
cin>>x;
if(q2[team[x]].empty())q.push(team[x]);//寻找是否有队友,有就插队,没有创建队伍
q2[team[x]].push(x);
}
else if(operate[0]=='D')//出队
{
int t=q.front();
cout<<q2[t].front()<<endl;//出最前面队伍编号的第一个人
q2[t].pop();//弹出
if(q2[t].empty())//判断队伍是否为空
q.pop();
}
}
cout<<endl;
}
return 0;
}
思路
最后
以上就是闪闪柠檬为你收集整理的c++STL 数据结构之queue队列应用的全部内容,希望文章能够帮你解决c++STL 数据结构之queue队列应用所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复