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）每发完一 ... ...