3.2队列 课件-2022-2023学年浙教版（2019）高中信息技术选修1

3.2队列（1） 队列的概念与特性 一、队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 入 队：在队列中插入一个元素的过程 出 队：从队列中删除一个元素的过程 出队 入队 队首元素 队尾元素 队列的概念与特性 二、队列的特性 1.先进先出、后进后出（FIFO）：由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图所示，出队时，对首元素a1优先出队，紧接着是a2,a3,……,an-1 ，队尾元素an最后出队。 a1 a2 a3 a4 a5 入队 队首元素 队尾元素 a5 a4 a3 a2 a1 出队 队首元素 队尾元素 队列的概念与特性 二、队列的特性 出队 入队 队首元素 队尾元素 只有一个后继点 只有一个前驱点 一个前驱&一个后继 2.有限序列性：队列也是一种线性表结构，元素个数是有限的。 队列可以是空的，也可以包含多个元素。 队列中所有元素呈线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 队列的基本操作 一、队列的存储结构 队列一般按顺序结构存储，可以用数组来实现。出入队时，队首和队尾元素的位置在不断改变，因此需设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。 a1 a2 a3 a4 0 1 2 3 队列元素 数组下标 队列的基本操作 1.建队 由于队列以数组形式存储，因此Python中用列表创建队列。 例如，有3个字母“A”“B”“C”按序入队、出队时，可以创建一个队列que，长度为4，Python代码如下所示。 0 1 2 3 队列元素 数组下标 head=0 tail=0 初始时，head指针和tail指针均记录下标为0的位置。 head=0#设置头指针 tail=0#设置尾指针 que=[""]*4 队列的基本操作 2.入队 0 1 2 3 队列元素 数组下标 head=0 tail=0 建队： head=0 tail=0 que=[""]*4 初始状态 0 1 2 3 0 1 2 3 A A入队： que[tail] =“A” tail+=1 tail=1 head=0 A B B入队： que[tail] =“B” tail+=1 tail=2 head=0 0 1 2 3 A B C入队： que[tail] =“C” tail+=1 tail=3 head=0 C 队列的基本操作 2.入队 head = 0 tail = 0 que = [“”] * 4 que[tail] =“A” tail +=1 que[tail] =“B” tail +=1 que[tail] =“C” tail +=1 head = 0 tail = 0 que = [“”] * 4 a=["A", "B", "C"] # 元素依次入队 for i in range(len(a)): ________________ tail += 1 que[tail] = a[i] 0 1 2 3 A B tail=3 head=0 C 【思考】此时可否让字母"D"入队？若可以，请写出入队的代码； 若不可以，请说明原因。 满队列 每个元素入队都让tail指针+1，当tail到达最大下标时不能再增加 队列中最多存储maxsize-1个元素 队列的基本操作 3.出队 0 1 2 3 C B A 初始状态 tail=3 head=0 0 1 2 3 head B A C tail 排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空 head = 0 tail = 3 que = [“A”,“B”,“C”] print(que[head]) head +=1 print(que[head]) head +=1 print(que[head]) head +=1 队列的基本操作 3.出队 0 1 2 3 head tail 排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空 head = 0 tail = 3 que = [“A”,“B”,“C”] print(que[head]) head +=1 print(que[head]) head +=1 print(que[head]) head +=1 head = 0 tail = 3 que = [“A”,“B”,“C”] # 元素依次出队 while ________________: print(que[head])