【信息技术 】队列 课件 浙教版（2019）高中信息技术选修1.pptx

《【信息技术 】队列 课件 浙教版（2019）高中信息技术选修1.pptx》由会员分享，可在线阅读，更多相关《【信息技术 】队列 课件 浙教版（2019）高中信息技术选修1.pptx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.2队列（队列（1）队列的概念与特性队列的概念与特性一、一、队列的概念队列的概念队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。入 队：在队列中插入一个元素的过程 出 队：从队列中删除一个元素的过程出队入队队首元素队尾元素队列的概念与特性队列的概念与特性二、二、队列的特性队列的特性1.先进先出、后进后出（FIFO）：由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图所示，出队时，对首元素a1优先出队，紧接着是a2,a3,an-1，队尾元素an最后出队。a1a1a2a2a3a3a4a4a5a5入 队队首元素队尾元素a5a5a4a4a3a3a2a2a1a1出

2、 队队首元素队尾元素队列的概念与特性队列的概念与特性二、二、队列的特性队列的特性出队入队队首元素队尾元素只有一个后继点只有一个后继点只有一个前驱点只有一个前驱点一个前驱一个前驱&一个后继一个后继2.有限序列性：队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。队列的基本操作队列的基本操作一、一、队列的存储结构队列的存储结构队列一般按顺序结构存储，可以用数组来实现。出入队时，队首和队尾元素的位置在不断改变，因此需设置头指针head记录队首元素位置，尾指针t

3、ail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。a1a2a3a40123队列元素数组下标队列的基本操作队列的基本操作1.建队建队由于队列以数组形式存储，因此Python中用列表创建队列。例如，有3个字母“A”“B”“C”按序入队、出队时，可以创建一个队列que，长度为4，Python代码如下所示。0123队列元素队列元素数组下标数组下标head=0tail=0初始时，head指针和tail指针均记录下标为0的位置。head=0#设置头指针tail=0#设置尾指针que=*4队列的基本操作队列的基本操作2.入队入队0123队列元素队列元素数组下标数组下标hea

4、d=0tail=0建队：head=0tail=0que=*4初始状态01230123AA入队：quetail=“A”tail+=1tail=1head=0ABB入队：quetail=“B”tail+=1tail=2head=00123ABC入队：quetail=“C”tail+=1tail=3head=0C队列的基本操作队列的基本操作2.入队入队head=0tail=0que=“”*4quetail=“A”tail+=1quetail=“B”tail+=1quetail=“C”tail+=1head=0tail=0que=“”*4a=A,B,C#元素依次入队for i in range(len

5、(a):_ tail+=1quetail=ai0123ABtail=3head=0C【思考】此时可否让字母D入队？若可以，请写出入队的代码；若不可以，请说明原因。满队列每个元素入队都让tail指针+1，当tail到达最大下标时不能再增加队列中最多存储maxsize-1个元素队列的基本操作队列的基本操作3.出队出队0123CBA初始状态tail=3head=00123headBACtail排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空head=0tail=3que=“A”,“B”,“C”print(quehead)head+=1print(quehea

6、d)head+=1print(quehead)head+=1队列的基本操作队列的基本操作3.出队出队0123headtail排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空head=0tail=3que=“A”,“B”,“C”print(quehead)head+=1print(quehead)head+=1print(quehead)head+=1head=0tail=3que=“A”,“B”,“C”#元素依次出队while _:print(quehead)head+=1head!=tail当队列元素全部出队，head=tail，此时还可以有新的元素

7、入队吗？队列的应用队列的应用信息的加密信息的加密 给定一个字符串S1,S2,.,Sn，按如下过程加密：取出一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3.SnS2;接着把S3取出，S4放到字符串的末尾S2后面.直到最后一个字母Sn被取出。这些字母按取出的顺序形成一个新的字符串，称为密串。请编写一个加密程序，输入一个字符串（长度小于等于30），输出该字符串的密串。队列的应用队列的应用信息的加密信息的加密队列que索引01234567891011headheadheadheadtailtailtailtail别别用用炮炮打打蚊蚊子子取出别别别别用用取出炮炮炮炮打打取出蚊蚊蚊

8、蚊子子取出用用用用打打取出子子子子打打取出打打打打head=tail队列清空【思考】加密字符只有6个，但实际需要的空间确是11个，为什么？队列的应用队列的应用信息的加密信息的加密算法步骤实现语句创建队列que将字符串各字符入队判断队列是否为空队首字符出队队首字符入队que=“”*11foriinrange(len(s):quetail=sitail+=1whileheadtail:print(quehead,end=)head+=1quetail=queheadtail+=1head+=1队列的应用队列的应用信息的加密信息的加密s=input(请输入字符串：)print(加密后的串为：)que

9、=*11#创建队列quehead,tail=0,0#初始化头指针和尾指针foriinrange(len(s):#元素依次入队_tail+=1whileheadtail:#直到队列为空，循环结束print(quehead,end=)#队首元素出队head+=1ifheadtail：n=maxsize+tail-head head=tail：n=tail-head练习练习1.下列事件执行过程与队列特征不相符的是（）A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象C练习练习1.队列存储在数组que0.n中，用head表示队首指针，tail表示队尾指针，当元素“x”要进入队列时，入队操作为：_。2.当队列que（非循环队列）的头指针变量和尾指针变量为head、tail，如何判断队列是否为空？3.队列是限定在（）进行操作的线性表。A.队首B.队尾C.中间D.两端quetai=Xtail=tail+1对于线性队列，当headtail时，队列非空。D好好学习好好学习天天向上天天向上