文章目录

---

前言

我想以博客的方式记录并督促自己不断学习，从紫书的第五章开始，跟着佬们的线路慢慢走

本文介绍紫书P117团体队列问题，我们知道一般队列queue遵循“先进先出”的原则，对于队列的插入删除十分麻烦，通过本题了解如何实现队列的中间插入，模拟类似“急诊病人插队”的情况。

---

一、问题介绍

        （从洛谷扒的）

         有 t 个团队的人正在排长队。每有一个新来的人时，他会从队首开始向后搜寻，如果发现有队友正在排队，他就会插队到他队友的身后；如果没有发现任何一个队友排队，他就只好站在长队的队尾。

输入每个团队中所有队员的编号，要求支持如下 33 种指令：

ENQUEUE x：编号为 x 的人进入长队。

DEQUEUE：长队的队首出队。

STOP：停止模拟。

对于每个 DEQUEUE 指令，输出出队的人的编号。

二、问题分析

1.分析队列

很明显，题目需要两个队列，一个存储实时排队情况，一个存储不同的团体（比如101，102，103为一个团队）。

2.数据处理

对于每个人的编号（如101），可以归为不同的团队，比如规定1号团队包含101，102，103......

于是我们可以用map表示映射关系（key表示自己代表的号码，value表示所属团队）

map<int,int> number;

我们不妨模拟下排队的具体情况，以上面输入案例1为例：

1.1号团的大哥101来了！！！   

    此时队列为 101

2.2号团的大哥201也来了（可惜比1号大哥来得慢，只能站在1号大哥后面）   

    此时队列101，201

3.1号团的二把手102来了，有101大哥罩着就插在201前面   

    此时队列101，102，201

4.2号团的二把手来了，只能在队伍最后面站着   

     此时队列101，102，201，202

  .............................................................................

最后队伍为101，102，103，201，202，203

不难发现，一个团队的人都站在一块了，而团队在整个队伍的位置取决与该团队第一个排队人

按团队来看，整个队伍的排序为 1号团队，2号团队。

至此，我们已经对数据怎么存储有了一定思路了！

queue<int>  team[1000]; 
//把每个团队看作一个队列，所有团队在一起就看成数组形式，下面入队看成在team中出现

queue<int>  total;//按团队在队伍的位置记录排队情况


//从输入字符串开始判断
string in;
 while(cin>>in)
        {
            if(in[0]=='S')    //如果是STOP就跳出
                break;

            if(in[0]=='E')   //如果是ENQUEUE,那就把后面跟着的数字给安排了
            {
                int a1;    //需要入对的数字
                cin>>a1;
                int t=number[a1];   //t为a1对应的团队
                if(team[t].empty()) 
                   { 
                    total.push(t);
                   }
               //若团队没有成员入队，则a1为所在团队的成员第一次入队，在total里加上该团队的号码
              team[t].push(a1);   //入队
            }

            if(in[0]=='D')   //如果是DEQUEUE，那就出队
            {
                if(!total.empty())    
                {
                    int t=total.front();    
                    cout<<team[t].front()<<endl;   
                    team[t].pop();         //从头开始出队
                    if(team[t].empty())    
                        total.pop();
                    //当团队人都走了，则该团队在队伍中不存在，下一个团队继续
                }
            }
        }

三、完整代码

#include <iostream>
#include<queue>
#include<map>
using namespace std;
map<int,int> number;
int main()
{
    int n,i,j;
   int qwq=1;
    while(cin>>n&&n)
    {
        for(i=1; i<=n; i++)
        {
            int a;
            cin>>a;
            int k;
            for(j=0; j<a; j++)
            {
                cin>>k;
                number[k]=i;
            }
        }
        cout<<"Scenario #"<<qwq<<endl;
            qwq=qwq+1;
        string in;
        queue<int> team[1000];
        queue<int> total;
        while(cin>>in)
        {
            if(in[0]=='S')
                break;
            if(in[0]=='E')
            {
                int a1;
                cin>>a1;
                int t=number[a1];
                if(team[t].empty())
                    total.push(t);
                team[t].push(a1);
            }
            if(in[0]=='D')
            {
                if(!total.empty())
                {

                    int t=total.front();
                    cout<<team[t].front()<<endl;
                    team[t].pop();
                    if(team[t].empty())
                        total.pop();
                }
            }
        }
        cout<<endl;
    }
    return 0;
}

---

总结

       通过模拟插队的情况，初步了解和熟悉对于队列插入删除操作，通过map的对应关系找到插队的目标位置，然后以集合数组来表示实时队伍情况，从而方便操作。

        STL的强大不止如此，还需不断深入学习理解，与君共勉。