资源简介

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

展开更多......

收起↑