高中：03图像模块.pptx

队列及基本操作 常见的数据结构——队列有序排队上车的乘客有序排队接客的出租车 乘客排队时先到的总是从队伍的头部出去（出队）上车，而后到的乘客则必须在队伍的尾部加入（入队）。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。 常见的数据结构——队列 用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出” FIFO（First In First Out）且中间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。 队列定义（一种线性表）队列：数据具有“先进先出（First in First out）”且中间不能“插队”的组织和操作的性质。队列元素：队列中的元素。在数据序列的头部（称队首）进行数据的读取（即出队），在数据序列的尾部（称队尾）进行数据的插入（即入队）。 队列的特性1.先进先出、后进后出（FIFO）：由队列的定义可知，队列具备“先进先出、后进后出”的特点。如下图所示，出队时，对首元素a1优先出队，紧接着是a2,a3,……,an-1 ，队尾元素an最后出队。2.有限序列性：队列也是一种线性表结构，元素个数是有限的。队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 队列存储结构队列一般按顺序结构存储，可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。(1)元素a1，a2，a3，a4依次入队后，tail的值为4，head的值为0。(2)当a1，a2，出队后，head记录下标为2的位置，tail值保持不变。 队列的相关操作：1.创建队列方法：直接使用Python列表创建队列。需要设置头指针变量head和尾指针变量tail，其中head指向队首元素所在位置，tail 指向队尾元素的下一个位置，当head值与tail值相等时，表示队列为空。例如，当有4个字母“A”“B”“C”“D”按序入队及出队时，可以创建一个长度为5，初始值均为0的空队列que，代码如下：head=0tail=0que=[“”]*5 队列的相关操作: 元素入队、出队元素从队尾入队，每插入一个新元素，tail后移一位。例如，字母“A”“B”“C”“D”按序入队时，在队列que中，用tail指针变量跟踪各元素的入队。代码见教材71页元素从队首出队，每删除一个元素，head后移一位。当head值与tail值相等时，表示队列为空。 元素入队和出队程序实现例如，将数字 1，2，3，4 依次入队，然后依次出队并输出的代码如下：a=[]print(入队：)for i in range(1,5): a.append(i) print(a)print(-----------)print(出队：)while len(a)!=0: print(a.pop(0)) 循环队列P72图D①在顺序队列中，当队尾指针已经到达数组的上界时，不能再有入队操作，否则 tail 前移会导致下标越界，但其实数组中可能还有空位置，这就叫做“假溢出”。解决假溢出的方法是采用循环队列。D②消除假溢出：当队尾指针 tail 指向 len(q)时，让其自动指向起始下标 0。循环队列可以采用取模运算解决队列中“假溢出”的问题，但同时会带来一个新问题：在循环队列中，队空和队满的特征都是 head==tail，判断条件将出现二义性。满？空？ 循环队列P72图③解决循环队列二义性：最常见的是空闲单元法，即人为浪费一个单元，将队满特征改为 head==(tail+1)%len(q)。tail队满 循环队列例：创建一个长度为 6，初始值均为 0 的空循环队列 q；然后随机生成整数入队，直至队满；再让元素依次出队并输出，直至队列为空的代码如下：运行程序可以发现循环队列 q 有一个空闲单元，即虽然队列总长度为 6，但实际被使用的长度为 5，在本例中 q[-1]没有被使用。 队列练习1.队列是限定在（ ）进行操作的线性表。A.队首 B.队尾 C.中间 D.两端2.队列存储在数组que[0..n]中，用head表示队首指针，tail表示队尾指针，当元素“x”要进入队列时，入队操作为：___________________________。D直接入队，队尾指针tail再加1que[tai]=Xtail=tail+1对于线性队列，当headtail时，队列非空3.当队列que（非循环队列）的头指针变量和尾指针变量为head、tail，如何判断队列是否为空？ 队列练习2C s=input(请输入字符串)q=[]*100head,tail=0,0#入队for i in range(len(s)):