(
课件网) 3.2队列 生活中的队列 按照到达时间的先后顺序，合理地安排办事次序。这些事件对数据的处理具有排队的特性，可以使用队列来解决。 出队：从队首中_____一个元素称为出队。 队列是一种_____的线性表，允许插入的一端称为_____，允许删除的一端称为_____。队列中的数据元素称为_____。 入队：在队尾中_____一个元素称为入队； 先进先出 队尾 队首 队列元素 插入 删除 出队 入队 队首元素 队尾元素 先进先出、后进后出 一、队列的概念 二.队列的特性 出队 入队 队首元素 队尾元素 只有一个后继点 只有一个前驱点 一个前驱&一个后继 特性一： 特性二： 有限序列性 队列也是一种线性表结构，元素个数是有限的。 先进先出、后进后出 图1 图2 下列事件执行过程与队列特征不相符的是 ( ) A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓 冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时” 工作的假象 练习1 C 解析：C选项中最底下的书是最先放入，但要最后才能拿出来，是先进后出，不符合队列先进先出的特性。 队列一般按顺序结构存储的，可以用数组来实现。 如图所示：数组que中存储了一个队列、共有4个元素，队首元素为a1，队尾元素为a4。 a1 a2 a3 a4 0 1 2 3 数组que的下标 在入队和出队的过程中，队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的_____位置。 三、队列的基本操作 队首元素 队尾元素 head tail 下一个 问题1：在Python语言中如何表示队列？ 问题2：如何描述队列入队和出队过程？ 活动1.建队：如：有4个字母“A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5, head=0tail=0que=[""]*5 0 1 2 3 4 数组que的下标 head tail 程序实现： 队列为空？ head==tail 初始时，head=tail=0 活动2.入队： que[tail]=”A” # A入队 tail=tail+1 #tail=1 que[tail]=”B” # B入队 tail=tail+1 #tail=2 que[tail]=”C” # C入队 tail=tail+1 #tail=3 que[tail]=”D” # D入队 tail=tail+1 #tail=4 0 1 2 3 4 数组que的下标 head 程序实现： 队非空判断条件： (head!=tail) A B C D tail 头指针head记录队首位置 尾指针tail记录队尾元素的下一个位置 队内元素个数= tail-head head
