1、知识回顾知识回顾有序排队上车的乘客有序排队接客的出租车 乘客排队时先到的总是从队伍的乘客排队时先到的总是从队伍的头部出去（出队）头部出去（出队）上车，而后到的乘客则必须在队伍上车，而后到的乘客则必须在队伍的的尾部加入（入队）尾部加入（入队）。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。3.2 队列高中信息技术 选择性必修一 数据与数据结构昌化中学 应彤鑫队列的概念与特性队列的概念与特性 概念 特性l 概 念：队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首l 队列元素：队列中的数据元素。l 入 队
2、：在队列中插入一个元素的过程。l 出 队：从队列中删除一个元素的过程。出队入队队首元素队尾元素队列的概念队列的概念d u i l i e d ed u i l i e d e g a i n i a n g a i n i a nl 先进先出、后进后出（FIFO）：由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图所示，出队时，对首元素a1优先出队，紧接着是a2,a3,an-1，队尾元素an最后出队。出队入队队首元素队尾元素队列的队列的特性特性d u i l i e d ed u i l i e d e t e x i n g t e x i n gl 有限序列性：队列也是一种线性表
3、结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。出队入队队首元素队尾元素队列的队列的特性特性d u i l i e d ed u i l i e d e t e x i n g t e x i n g1.幼儿园小朋友们排队玩华护体，轮流爬上去，再轮流滑下来，此过程用那种数据结构描述最合适（）A.链表 B.字典 C.栈 D.队列练一练练一练l i a n y i l i a nl i a n y i l i a nD2.下列事件执行过程与队列特征不相符的是（）A.在汽车加
4、油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象练一练练一练l i a n y i l i a nl i a n y i l i a nC队列队列的基本操作的基本操作 队列的存储结构 建队 入队 出队u 队列的存储结构：队列一般按顺序结构存储，可以用数组来实现。设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。队列的基本操作队列
5、的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z u o j i b e n c a o z u ou 队列的存储结构：队列一般按顺序结构存储，可以用数组来实现。设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位置。初始时，head指针和tail指针均记录下标为0的位置。队列的基本操作队列的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z u o j i b e n c a o z u o初始状态数据入队后状态tail=44数据出队后状态tail=44u 队列的链
6、式存储结构：队列的链式存储称为链队列，为了操作方便，可以设置队首指针head记录链表的头结点，队尾指针tail记录链表的队尾节点。队列的基本操作队列的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z u o j i b e n c a o z u o3.判断一个长度为n的队列q为空的条件是（）A.head=0 B.tail=0 C.tail=-1 D.head=tail4.用python列表模拟队列，并设置队头指针head指向队首元素，队尾指针tail指向队尾元素的下一个位置，则当head=3，tail=6时，队列中元素的个数为（）A.3
7、 B.4 C.5 D.6练一练练一练l i a n y i l i a nl i a n y i l i a nDAu建队由于队列以数组形式存储，因此python中用列表创建队列。例如：有4个字母“A”“B”“C”“D”按顺序入队、出队时，可以创建一个队列que，长度为5，python代码如下所示：队列的基本操作队列的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z u o j i b e n c a o z u ohead=0tail=0que=“”*5u入队字母“A”“B”“C”“D”按顺序入队时，在队列que中，用tail指针变量跟
8、踪各元素的入队队列的基本操作队列的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z u o j i b e n c a o z u o01234headtail初始状态（空队列）A01234headtail“A”入队head=0tail=0que=“”*5quetail=“A”tail+=1AB01234headtail“B”入队quetail=“B”tail+=1u入队字母“A”“B”“C”“D”按顺序入队时，在队列que中，用tail指针变量跟踪各元素的入队队列的基本操作队列的基本操作d u i l i e d ed u i l i
9、e d e j i b e n c a o z u o j i b e n c a o z u o01234headtail初始状态（空队列）head=0tail=0que=“”*5ABCD01234headtail全部入队quetail=“A”tail+=1quetail=“B”tail+=1quetail=“C”tail+=1quetail=“D”tail+=1u出队出队时，排在队首的元素依次出队，head指针变量依次加1，直至head值等于tail值时，队列为空。队列的基本操作队列的基本操作d u i l i e d ed u i l i e d e j i b e n c a o z
10、u o j i b e n c a o z u oABCD01234headtail全部出队while head!=tail:head+=1ABCD01234headtail初始状态（满队列）练一练练一练l i a n y i l i a nl i a n y i l i a n1.队列存储在数组que0.n中，用head表示队首指针，tail表示队尾指针，当元素“x”要进入队列时，入队操作为：_。2.当队列que（非循环队列）的头指针变量和尾指针变量为head、tail，如何判断队列是否为空？3.队列是限定在（）进行操作的线性表。A.队首B.队尾C.中间D.两端quetai=Xtail=ta
11、il+1对于线性队列，当headtail时，队列非空。Du 循环队列：将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“有空闲位置却不能入队”的问题。拓展拓展t u o z h a nt u o z h a n5.已知队列元素的个数为6，则队首指针head和队尾指针tail的值不可能的是（）A.head=0，tail=6 B.head=6，tail=0 C.head=3，tail=2 D.head=3，tail=8练一练练一练l i a n y i l i a nl i a n y i l i a nD
