3.2队列ppt课件-2023新浙教版（2019）《高中信息技术》选修1.pptx

1、去银行、医院办理业务时，取号机能按照到达时间的先后顺序，合理地安排办事次序。这些事件对数据的处理都具有排队的特性，可以使用队列来解决。队列的概念与特性一、队列的概念队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。n1 n2 n3 n4 nn 队尾元素队首元素入队出队图1二、队列的特性（1）先进先出、后进后出由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图1所示，出队时，队首元素n1优先出队，紧接着是n2,n3,nn，队尾元素nn最后出队。（2）有限序列性队列也是一种

2、线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。队列的基本操作队列一般按顺序结构存储，可以用数组来实现。如下图所示，数组que中存储了一个队列、共有4个元素，队首元素为a1，队尾元素为a4。由于在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。a1a1a2a2a3a3a4a40123队列的存储a1a1a2a2a3a3a4a401

3、23401234tailhead数组que的下标headtail队列的head、tail指针变化图对于下图所示的队列，初始时，head指针变量与tail指针变量均记录下标为0的位置。元素a1、a2、a3、a4依次入队后，tail值为4,head值为0。当a1、a2出队后，head记录下标为2的位置，tail值不变。当a3、a4出队后，head与tai的值均为4，队列为空。队列的常用操作有建队、入队、出队等。1.建队由于队列以数组形式存储，因此python中用列表创建队列。例如，有4个字母“A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5，python代码如下所示：hea

4、d=0tail=0que=“”*52.入队、出队字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素入队。如下图所示：A01tailAB01tailABC0123tailABCD01234tail（1）（2）（3）（4）入队的Python代码如下：quetail=“A”#字母A入队tail=tail+1#tail=1quetail=“B”#字母B入队tail=tail+1#tail=2quetail=“C”#字母C入队tail=tail+1#tail=3quetail=“D”#字母D入队tail=tail+1#tail=4出队时，排在队首的元素依次出队，head

5、指针变量依次加1，直至head值等于tail值时，队列为空。拓展链接：循环队列循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。E E01234下标headtailtail超出队列的边界如上图所示，某队列分配的最大空间为5，其最后一个位置上的元素为“E”，队首指针变量head的值为4，队尾指针变量tail的值为5（tail超出了队列的边界），此时，数组中存在空闲位置，但新的元素不能入队。将队列改为循环队列，则在元素“E”入队后，head的值为4

6、，队尾指针重新指向队首（tail的值为0），当新元素“F”入队时，就加入到队首，然后tail的值变为1。如下图所示。01234Eheadheadtailtail“E”入队01234headheadtailtailEF“F”入队循环队列队列模块queue在python中有自带的队列模块queue，方法如下。代码代码说明说明import queue导入队列模块q=queue.Queue(5)建立一个长度为5的队列qq.put(1)将数字1入队q.qsize()输出队列中元素的个数q.get()队首元素出队队列的应用例：信息的加密给定一个字符串S1，S2，Sn，按如下过程加密：取出第一个字符S1，将

7、第二个字符S2放到字符串的末尾Sn后面，得到字符串S3SnS2；接着把S3取出，S4放到字符串的末尾S2后面直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于100），输出该字符串的密串。加密的过程，类似队列的入队、出队操作。先把原字符串中各字符依次入队，得到一个队列，再执行加密的过程：取出队首元素，存到密串中，队列中第二个元素升级为队首元素；再取出队首元素，并把该元素插入队尾。反复操作，直至队列为空，得到密串。以字符串“STRING”为例，算法步骤如下：创建que队列，把字符串“STRING”按序压入队列，tail值

8、为6，head值为0。加密过程。先取出队首元素“S”，并输出，同时head值加1，记录新的队首元素“T”所在的位置。再取出队首元素“T”，并把该元素加入队尾，head值、tail值均加1。重复操作，直至队列为空。前两个字母的出队、入队过程如下图所示：队列队列quequeT TR RI IN NGG01234567headtail“S”出队队列队列quequeR RI IN NGG1234567“T”出队headtail队列队列quequeR RI IN NGGT T01234567headtail“T”入队用python 实现的完整程序及测试结果：s=input(“请输入字符串：”)print

9、(“加密后的串为：”)que=“”*100head=0tail=0for i in range(len(s):#把原串全部压入队列 quetail=si tail+=1While headtail:#队列非空时 print(quehead,end=“”)head+=1 if headtail:#队列非空时，出队的元素加入队尾 quetail=quehead tail+=1 head+=1请输入字符串：Python加密后的串为：Ptoynh练一练1.依次在初始为空的队列中将元素“h”，“e”，“l”，“l”，“o”入队以后，紧接着做了两次删除操作，此时的队首元素是：A.“h”B.“e”C.“l”

10、D.“o”C2.有如下python 程序段，使用长度为3的列表q模拟队列的出队入队活动：q=1,2,3 ys=for i in range(4,10):ys.append(q0)q0=q1 q1=q2 q2=i print(ys,q)程序运行结束后，列表ys中元素的数量为_。63.有如下python程序段：from queue import Queueq=Queue(5)print(“能存放的最多元素个数=”,q.maxsize)for i in range(q.maxsize):q.put(3*i)print(“是否满：”,q.full()for i in range(q.qsize():print(“当前实际长度=”,q.qsize()print(“取出元素：”,q.get()从队列中取出的元素依次是_。0,3,6,9,12谢 谢