队列--浙教版（2019）高中信息技术选修1.pptx

队列授授课课人人：*l队列：列：队列是列是一种先一种先进先出的先出的线性表性表，允，允许插插入的一端称入的一端称为队尾尾，允，允许删除的一端称除的一端称为队首。首。队 列 的 概 念出队入队队首元素队尾元素l队列元素列元素：队列中的数据元素列中的数据元素l入入队：在：在队列中插入一个元素的列中插入一个元素的过程程l出出队：从：从队列中列中删除一个元素的除一个元素的过程程有限序列性：线性表结构，元素个数有限的有限序列性：线性表结构，元素个数有限的先进先出、后进后出先进先出、后进后出（FIFOFIFO）只有一个后继点只有一个后继点只有一个前驱点只有一个前驱点一个前驱一个前驱&一个后继一个后继队 列 的 特 性先进先出、后进后出（先进先出、后进后出（FIFOFIFO）：）：由队列的定义可知，队列具备由队列的定义可知，队列具备“先进先出、后进后出先进先出、后进后出”的的特点。如图所示，出队时，对首元素特点。如图所示，出队时，对首元素a1a1优先出队，紧接着是优先出队，紧接着是a2,a3,an-1 a2,a3,an-1，队尾元素，队尾元素anan最后出队。最后出队。a1a1a a2 2a a3 3a4a4a a5 5入入队队首元素队尾元素先进先出、后进后出（先进先出、后进后出（FIFOFIFO）：）：由队列的定义可知，队列具备由队列的定义可知，队列具备“先进先出、后进后出先进先出、后进后出”的的特点。特点。如如图所示，出所示，出队时，对首元素首元素a1a1优先出先出队，紧接着是接着是a2,a3,an-1 a2,a3,an-1，队尾元素尾元素anan最后出最后出队。a a5 5a4a4a a3 3a a2 2a1a1出出队队首元素队尾元素队 列 的 特 性已知已知队列（列（4，21，55，66，48，24，35，12，78，5）第一个）第一个进入入队列的元素列的元素是是4，请问第第3个出个出队列的元素是（列的元素是（）A.35B.12 C.55 D.5练一练C C队 列 的 基 本 操 作a1a2a3a40123队列元素列元素数数组下下标u队列的存储结构：队列一般按顺序结构存储，可以用数组来实现。出入队时，队首和队尾元素的位置在不断改变，因此需设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。u队列的存储结构：队列一般按顺序结构存储，可以用数组来实现。出入队时，队首和队尾元素的位置在不断改变，因此需设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。Python中用列表模拟实现。队 列 的 基 本 操 作0123队列元素队列元素数组下标数组下标head=0tail=0建建队：head=0tail=0que=*4队 列 的 基 本 操 作0123队列元素队列元素数组下标数组下标head=0tail=0建建队：head=0tail=0que=*4初始状初始状态01230123A A A AA入入队：quetail=“A”tail+=1A入入队tail=1head=0A A A A B B B BB入入队：quetail=“B”tail+=1tail=2head=0B入入队0123C C C CB B B BA A A Aquetail=“A”tail+=1quetail=“B”tail+=1quetail=“C”tail+=1队 列 的 基 本 操 作for i in“A“,“B“,”C“：quetail=i tail+=1满队列列tail=3head=0为什么什么进入入3个元素，个元素，队列列就就满了？了？每个元素每个元素进队进队都都让让tailtail指指针针+1+1，当，当tailtail到达最大下到达最大下标时标时不能再增加不能再增加队列中最多存列中最多存储maxsize-1个元素个元素0123C C C CB B B BA A A A初始状初始状态tail=3head=00123headB B B BA A A AC C C Ctail排在排在队首的元素依次出首的元素依次出队，head指指针变量依次加量依次加1，直至，直至head值等于等于tail值时，队列列为空空while len(que)!=0:que.pop(head)队 列 的 基 本 操 作当当head=tail但不但不为0时，还可以有新的元素入可以有新的元素入队吗？假溢出拓 展：循 环 队 列循循环队列：列：将将队列的列的队首和首和队尾尾连接接起来，形成起来，形成逻辑上的上的环状状结构构。当。当对循循环队列中的元素列中的元素进行入行入队、出、出队操作操作时，队首指首指针变量和量和队尾指尾指针变量可以循量可以循环指向所有位置，从而有效解决指向所有位置，从而有效解决队列中列中“有空有空闲位置却不能入位置却不能入队”的的问题。为区分区分队空和空和满，会在，会在队尾留一个数据尾留一个数据单元，此元，此时队列最多可放列最多可放m-1个个数据元素数据元素.拓 展：循 环 队 列head=tailhead=tail(tail+1)%maxsize=headtail+1)%maxsize=headheadtail：n=maxsize+tail-head head=tail：n=tail-head课 堂 小 结队列列一、一、队列的概念（先列的概念（先进先出的先出的线性表性表）二、二、队列的特性（先列的特性（先进先出、有限序列性）先出、有限序列性）三、三、队列的基本操作（建列的基本操作（建队、入、入队、出、出队）同学们！下课啦！