5-6 队列

没时间了,而且自己不知道用法,脑子又愚钝,所以就理解下代码就好了
http://acm.hust.edu.cn/vjudge/contest/128220#problem/F
以下源代码
——————————————————————————————————

#include <cstdio>  
#include <map>  
#include <queue>  
using namespace std;  
const int maxt=1000+10;  
int main()  
{  
    int t,kase=0; //kase时因为输出格式所以jia'de 
    while(scanf("%d",&t)==1&&t)  //判断种植条件
    {  
        printf("Scenario #%d\n",++kase);  //格式
        map<int,int> team;  //创建一个映射 相同队列的人对应同一个value值
        for(int i=0;i<t;i++)  //输入队列人数(一队一队输)
        {  
            int n,x;  
            scanf("%d",&n);  
            while(n--)  
            {  
                scanf("%d",&x);  //输入人
                team[x]=i;  //映射进i 同一队在同一for循环输入 i相同
            }  
        }  
        queue<int> q,q2[maxt];  //q为队列的队列 , q2[i]是x成员所在队列 每一个不同的i代表不同队列
        for(;;)  //一直循环 直到输入S break;
        {  
            int x;  
            char cmd[10];  原题里有这个:Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation
of the team queue should be efficient: both enqueing and dequeuing of an element should
only take constant time. 所以我不是很理解这里开到10是什么意思
            scanf("%s",cmd);  //输入指令 判断首字母 如果需要整体判断 之前有用过string
            if(cmd[0]=='S') break;  
            else if(cmd[0]=='D')   
            {  
                int t=q.front();  //令t = 总队列中的支队列(用唯一映射的int代表,并不是真正地包含)
                printf("%d\n",q2[t].front());  
                q2[t].pop();  //删除首队伍中的首元素
                if(q2[t].empty()) q.pop();  //支队列为空则删除
            }  
            else if(cmd[0]=='E')  
            {  
                scanf("%d",&x);  
                int t=team[x];  
                if(q2[t].empty()) q.push(t);  
                q2[t].push(x);  
            }  
        }  
        printf("\n");  
    }  
    return 0;       
}

题目明确告诉了我们使用队列。使用一个队列排列团队;再使用一个队列排列元素。题目中说了出队入队只能花费常数时间,所以要在元素和团队之间建立映射关系而不能简单地使用数组存下元素。

在这样队中有队的关系中,大的队中不是真的包含着队列,而是一个具有唯一性的数据

push()会将一个元素置入queue中。

front()会返回queue内的第一个元素(也就是第一个被置入的元素)。
back()会返回queue中最后一个元素(也就是最后被插入的元素)。
top()取队首元素(但不删除)。
pop()会从queue中移除一个元素。
注意:pop()虽然会移除下一个元素,但是并不返回它,front()和back()返回下一个元素但并不移除该元素。

另:

优先队列也定义在头文件中,用"priority_quene pq"来声明。(越小的整数优先级越低)

由于出队的元素并不是最先进队的元素,出队的方法由front()变为了top().

越小的整数优先级越大的定义方式 "priority_queue<int,vector,greater > pq"

自定义类型也可以组成优先级队列,但必须为每个元素定义一个优先级。

eg. 实现 “个位数的的整数优先级反而小” ,可以定义一个结构体cmp,重载“()” 运算符,然后用“priority_queue<int,vector,cmp> pq"的方式定义
下面是cmp的定义

struct cmp{

    bool operator() (const int a, const int b)const{                  //a的优先级比b小时返回true

            return a%10>b%10;

       }
}

另外 队与栈的区别 https://zhidao.baidu.com/question/223432364.html

question: 要多层嵌套队列要怎么做?

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,451评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,172评论 3 394
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,782评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,709评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,733评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,578评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,320评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,241评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,686评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,878评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,992评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,715评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,336评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,912评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,040评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,173评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,947评论 2 355

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,657评论 18 139
  • 容器的概念所谓STL容器,即是将最常运用的一些数据结构(data structures)实现出来。容器是指容纳特定...
    饭饭H阅读 383评论 0 0
  • GCD调度队列是执行任务的强大工具。调度队列允许您相对于调度者异步或者同步的执行任意代码块。您能够使用调度队列来执...
    坤坤同学阅读 6,673评论 1 3
  • 1.容器deque C++ STL容器deque和vector很类似,也是采用动态数组来管理元素。 使用deque...
    博览网小学员阅读 405评论 0 0
  • part 1 白小狗是一只美丽、可爱的小狗,并且拥有一颗善良的心。 黑小狗是一只正直、憨厚的小狗,并且拥有一颗真诚...
    用余生追赶时光阅读 1,639评论 0 4