队列 - 北冥有鱼 | Scarecrow = 2022

# 简介

队列 queue 是一种线性的序列结构，其存放的元素按照线性的逻辑次序排列，但与一般的线性序列结构如数组或向量相比，队列的操作只限于逻辑上的两端，即新元素只能从队列的一段插入（入队），并且只能从队列的另一端删除已有的元素（出队）。允许队列插入的一端称为队尾，允许队列删除的一端称为队头。

	// 常规操作
	#include <iostream>
	#include <queue>
	#include <cstdio>

	using namespace std;

	queue<int> myQueue;

	int main()
	{
	printf("the size of myQueue:%d\n", myQueue.size());
	for (int i = 0; i < 10; ++i)
	{
	myQueue.push(i);// 队列元素的添加
	}
	// 访问队列中的元素，front (),back ()
	printf("the front of myQueue:%d\n", myQueue.front());
	printf("the back of myQueue:%d\n", myQueue.back());
	// 队列的状态，size (),empty ()
	printf("the size of myQueue:%d\n", myQueue.size());
	int sum = 0;
	while (!myQueue.empty())
	{
	sum += myQueue.front();
	myQueue.pop();// 队列元素的删除
	}
	printf("sum:%d\n", sum);
	if (myQueue.empty())
	{
	printf("myQueue is empty\n");
	}
	printf("the size of myQueue:%d\n", myQueue.size());
	return 0;
	}

	the size of myQueue:0
	the front of myQueue:0
	the back of myQueue:9
	the size of myQueue:10
	sum:45
	myQueue is emptythe size of myQueue:0

# 队列的应用

# 约瑟夫问题（变体）

n 个小孩围成一圈，任意假定一个数 m , 从第 p 个小孩起按顺时针方向从 1 开始报数，当报到 m 时，该小孩离开
然后继续从 1 开始报数。这样，小孩不断离开，圈子不断缩小直到所有小孩都从圈中出去。请按出去的先后顺序输出小孩的编号。输入 n p m ，输出小孩的编号序列，用空隔隔开。（用 0 0 0 结束循环）

样例输入

	8 3 4
	0 0 0

样例输出

6,2,7,4,3,5,1,8

测试代码

	#include <iostream>
	#include <queue>
	#include <cstdio>

	using namespace std;

	queue<int> children;

	int main()
	{
	int n, p, m;
	while (scanf("%d%d%d", &n, &p, &m))
	{
	if (n == 0 && p == 0 && m == 0)
	{
	break;
	}
	for (int i = 1; i <= n; ++i)
	{
	children.push(i);
	}
	for (int i = 1; i < p; ++i)
	{
	children.push(children.front());
	children.pop();
	}
	while (!children.empty())
	{
	for (int i = 1; i < m; ++i)
	{
	children.push(children.front());
	children.pop();
	}
	printf("%d ", children.front());
	children.pop();
	}
	printf("\n");
	}
	return 0;
	}

# 猫狗收容所

有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式：
第一种为直接收养所有动物中最早进入收容所的。
第二种为选择收养的动物类型 (猫或狗)，并收养该种动物中最早进入收容所的。
给定一个操作序列代表所有事件。
若第一个元素为 1 ，则代表有动物进入收容所。第二个元素为动物的编号，正数代表狗，负数代表猫；
若第一个元素为 2 ，则代表有人收养动物，第二个元素若为 0 ，则采取第一种收养方式；若为 1 ，则指定收养狗；若为 -1 则指定收养猫。
请按顺序返回收养的序列。
若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

输入的第一行第一个数为操作次数 n ，接下来 n 行，每行有两个值 m 和 t ，分别代表题目中操作的两个元素。