STL初步——队列Queue

『写在前面的一些基础语法』

1.定义 和 使用

queue<int> a;

2.Queue的一些特性

•  操作原则：先进先出（First In First Out），简称为FIFO表。
• ¨只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
• ¨允许删除的一端称为队头（Front）。
• ¨允许插入的一端称为队尾（Rear）。
• ¨当队列中没有元素时称为空队列。

¨

3.一些基本的操作

• ¨q.pop() ;//     删除queue的队头元素
• ¨q.front() ;//   返回队列的队头元素，但不删除该元素
• ¨q.back() ;//   返回队列的队尾元素，但不删除该元素
• ¨q.push(arg);//      将元素arg插入到队列的队尾
• ¨q.emplace(arg);//  将元素arg放置到队列的尾部，作用和push一样
• ¨q.size();//   返回队列中元素的个数
• ¨q.empty();//    当队列为空时返回true，否则返回false
• ¨q.swap(q1);//     交换q和q1中的元素，方法和stack中一样，并不会真正使用拷贝形式进行交换，只是交换底层的数据结构
• ¨swap(q,q1);//     非成员函数，和成员函数swap一样

『上题上题』

【团体队列】（Team Queue UVa 540）

先给出T个团体，并给出每个团体有多少人和每个人的编号，然后所有团体一起排队，排成一条大队列，排队的原则是，一个成员加入，如果这个成员所在的团体已经有人在排队了，那么他就加到他所在团体的最后面，而不是整个大队列的最后。如果整个大队列中没有他的团体，也就是他是他的那个团体第一个来的人，那么他就要排在整个大队列的最后（当然，他成为了他这个团体的第一人，以后他的队友来了就可以排他后面）

【输入】

输入文件将包含一个或多个测试案例。每个测试案例第一个是团队T的数量。然后，接下来的T行为团队每个人的编号，编号是整数，范围在0 - 999999。一个团队可以由多达1000个元素组成。

最后，如下命令指令。有三种不同的指令：

ENQUEUE x - 输入元素x入队队列

DEQUEUE -长队队首出队，并输出出队的人的编号

STOP - 结束

【输出】

对于每一个测试案例，首先打印一句"Scenario #k”，其中K是测试案例数。然后，为每个队列的命令，输出出队一行元素。每个测试案例后输出一个空行（包括最后一个）

【样例输入】

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

『代码代码』

#include <bits/stdc++.h>
using namespace std;
const int maxt = 1010;
int main() {
	int t,kase = 0;
	while(scanf("%d", &t) == 1 && t) {
		printf("Scenario #%d\n",++kase);

		map<int, int> team;
		for(int i = 0; i < t; i++) {
			int n,x;
			scanf("%d",&n);//每个队伍的成员个数
			while(n--) {
				scanf("%d",&x);
				team[x]=i;
			}
		}

		//模拟
		queue<int> q, q2[maxt]; //q是大队列 q2[i]是团队i成员的队列 是本题关键
		while(1) {
			int x;
			char cmd[10];
			scanf("%s", cmd);
			if(cmd[0] == 'S') break;//如果是STOP 就直接跳出
			else if(cmd[0] == 'D') {
				int t = q.front();// 找出大队列的队首
				printf("%d\n", q2[t].front());//找到大队列队首元素所在的小队列的队首  并输出
				q2[t].pop();//将小队列队首出队
				if(q2[t].empty())//如果该队伍在整个队列中只有一个人，则q的队首出队，即该队伍出队
					q.pop();
			} else if(cmd[0] == 'E') {
				scanf("%d",&x);
				int t = team[x];//通过map找出x的队列序号
				if(q2[t].empty())
					q.push(t);//如果该队还没有人排在队中，则该队列插入队尾
				q2[t].push(x);//把该队伍的人插入到q2的该队中
			}
		}
		printf("\n");
	}
	return 0;
}

 

『感悟』

请认真读题目

最近无心学习,更新太慢 ,明天一定改正...一定改正