我是靠谱客的博主 闪闪柠檬,最近开发中收集的这篇文章主要介绍c++STL 数据结构之queue队列应用,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

规则: 先进先出!!!


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队列应用所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(46)

评论列表共有 0 条评论

立即
投稿
返回
顶部