欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL初步——队列Queue

程序员文章站 2022-06-08 08:10:42
...

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

1.定义 和 使用

queue<int> a;

STL初步——队列Queue

2.Queue的一些特性

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

¨STL初步——队列Queue

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;
}

 

『感悟』

请认真读题目

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

相关标签: STL queue