2020-2021学年信息学奥赛资料 第十九课 队列（适用于高中）课件（18张PPT）

第十九课 队列

目 标
01、理解队列的概念及其基本操作。
02、 学会使用队列解决一些实际问题。
队列
队列是一种操作（或者说运算）受到限制的特殊线性表。其插入操作限定在表的一端进行，称为“入队”；其删除操作则限定在表的另一端进行，称为“出队”。插入一端称为队尾（rear）；删除一端称为队头（front）。
队列
队列也被称作“先进先出”线性表（FIFO，First In First Out）。类似于生活中排队购票，先来先买，后来后买。
在不断入队、出队的过程中，队列将会呈现出以下几种状态：
队空：队列中没有任何元素。
队满：队列空间已全被占用。
溢出：当队列已满，却还有元素要入队，就会出现“上溢（overflow）”；当队列已空，却还要做“出队”操作，就会出现“下溢（underflow）”。两种情况合在一起称为队列的“溢出”。
1. 队列的基本操作（具体参见教材245页-246页）
（1） 初始化
（2） 判空
（3） 求队列中实际元素的个数
（4） 入队，入队操作前，需要判断队列是否已满
（5） 出队，出队操作前，需要判断队列是否为空
（6） 取队首元素
2. 循环队列
随着入队与出队操作的不断进行，队头指针在数组中不断向队尾方向移动，而在队头前面产生了一片不能利用的“空闲区”，当队尾指针指向数组最后一个位置，即rear = maxn时，如果再有元素入队就会出现“溢出”，这种溢出称作“假溢出”。
如何解决这种情况呢？一种方法是每次出队操作时，都向“空闲区”整体移动一位，带来的后果是时间复杂度高了；另一种方法是让数组首尾相连，形成“环”状，即所谓的“循环队列”。
2. 循环队列
循环队列初始时，front = rear = 0，如果 maxn 个元素一个个依次入队，则 rear = maxn，此时再有元素入队，则它会被存放在 q[0] 这个单元，也会出现 front = rear = 0，与队空时的状态一样。解决方法是少用一个元素空间，约定数据入队前，测试“队尾指针在循环意义下加 1 后是否等于头指针”作为判断“队满”的条件。循环队列的实际长度为 (rear - front + maxn) % maxn。
循环队列的重要操作修改如下(使用 q[0] 这个单元)：
（1）判断队满：如果(rear + 1) % maxn = front，则队列已满。
（2）入队：如果队列未满，则执行：rear = (rear + 1) % maxn；q[rear] = x；
（3）出队：如果队列不为空，则执行：front = (front + 1) % maxn；
3. 队列的应用举例
例1、周末舞会
【问题描述】
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。
【输入格式】
第 1 行两个正整数，表示男士人数 m 和女士人数 n，1≤m，n≤1000；
第 2 行一个正整数，表示舞曲的数目 k，k≤1000。
【输出格式】
共 k 行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。
【输入样例】
2 4
6
【输出样例】
1 1
2 2
1 3
2 4
1 1
2 2
【问题分析】
显然，舞伴配对的顺序符合“先进先出”，所以用两个队列分别存放男士队伍和女士队伍。然后，模拟 k 次配对：每次取各队队头元素“配对”输出，并进行“出队”和重新“入队”操作。
参考程序参见教材247页-248页。
例2、取牌游戏
【问题描述】
小明正在使用一堆共 K 张纸牌与 N-1 个朋友玩取牌游戏。其中，N≤K≤100000，2≤N≤100，K 是 N 的倍数。纸牌中包含 M=K/N 张“good”牌和 K-M 张“bad”牌。小明负责发牌，他当然想自己获得所有“good”牌。
他的朋友怀疑他会欺骗，所以他们给出以下一些限制，以防小明耍诈：
1）游戏开始时，将最上面的牌发给小明右手边的人。
2）每发完一张牌，他必须将接下来的 P 张牌（1≤P≤10）一张一张地依次移到最后，放在牌堆的底部。
3）以逆时针方向，连续给每位玩家发牌。
小明迫切想赢，请你帮助他算出所有“good”牌放置的位置，以便他得到所有“good”牌。牌从上往下依次标注为 #1，#2，#3，…
【输入格式】
第 1 行，3 个用一个空格间隔的正整数 N、K 和 P。
【输出格式】
M 行，从顶部按升序依次输出“good”牌的位置。
【输入样例】
3 9 2
【输出样例】
3
7
8
【问题分析】
方法1、利用普通队列模拟。
结合题目中的条件 1 和 3，可以推出“小明是第 n 个拿到牌的”，根据数据范围大致推出队列存储容量上界为 K + 10 × N × (100000 / N) = 1100000。
参考程序参见教材248页-249页。
方法2、利用循环队列模拟实现。
参考程序参见教材249页-250页。
队列的应用
例1、Blah 数集
【问题描述】
数学家高斯小时候偶然间发现一种有趣的自然数集合 Blah。对于以 a 为基的集合 Blah 定义如下：
1）a 是集合 Blah 的基，且 a 是 Blah 的第一个元素；
2）如果 x 在集合 Blah 中，则 2x+1 和 3x+1 也都在集合 Blah 中；
3）没有其他元素在集合 Blah 中了。
现在小高斯想知道如果将集合 Blah 中元素按照升序排列，第 n 个元素会是多少？注意：集合中没有重复的元素。
【输入格式】
一行两个正整数，分别表示集合的基 a 以及所求元素序号 n，1≤a≤50，1≤n≤1000000。
【输出格式】
一行一个正整数，表示集合 Blah 的第 n 个元素值。
【输入样例1】
1 100
【输出样例1】
418
【输入样例2】
28 5437
【输出样例2】
900585
【问题分析】
根据条件，除了第一个数 a 以外，可以把数集 q[] 的所有数分成两个子集，一个是用 2x+1来表示的数的集合1，另一个是用 3x+1 来表示的数的集合2，两个集合要保持有序非常容易，只需用两个指针 two 和 three 来记录。其中 two 表示集合1 下一个要产生的数是由 q[two]*2+1 得到，three 表示集合2 下一个要产生的数是由 q［three］*3+1 得到。接下来比较 q[two]*2+1 和 q[three]*3+1 的大小关系：
1）如果 q[two]*2+1 < q[three]*3+1，则把 q[two]*2+1 加入数集中。
2）如果 q[two]*2+1 > q[three]*3+1，则把 q[three]*3+1 加入数集中。
3）如果 q[two]*2+1 = q[three]*3+1，则取任意其一加入数集中即可。
所以，本题就是利用队列先进先出的特点，模拟 n 个数依次产生的过程。
#include
using namespace std;
int q[1000011];
int main(){
int a,n,x,two,three,rear;
cin >> a >> n;
two = three = rear = 1;
q[1] = a;
while(rear != n){
if(2 * q[two] + 1 > 3 * q[three] + 1){
rear++;
q[rear] = 3 * q[three] + 1;
three++;
} else if(2 * q[two] + 1 < 3 * q[three] + 1){
rear++;
q[rear] = 2 * q[two] + 1;
two++;
} else{
rear++;
q[rear] = 3 * q[three] + 1;
two++; three++;
}
}
cout << q[n] << endl;
return 0;
}