3.2 队列　课件　2021—2022学年浙教版（2019）信息技术选修1

知识回顾 有序排队上车的乘客 有序排队接客的出租车 乘客排队时先到的总是从队伍的头部出去（出队）上车，而后到的乘客则必须在队伍的尾部加入（入队）。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。 1 CHZX 3.2 队列 浙江省高中信息技术 选择性必修一 《数据与数据结构》 昌化中学 应彤鑫 2 队列的概念与特性 概念 特性 01 3 概 念：队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首 队列元素：队列中的数据元素。 入 队：在队列中插入一个元素的过程。 出 队：从队列中删除一个元素的过程。 出队 入队 队首元素 队尾元素 队列的概念 duilie de gainian 4 先进先出、后进后出（FIFO）：由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图所示，出队时，对首元素a1优先出队，紧接着是a2,a3,……,an-1 ，队尾元素an最后出队。 出队 入队 队首元素 队尾元素 队列的特性 duilie de texing 5 有限序列性：队列也是一种线性表结构，元素个数是有限的。 队列可以是空的，也可以包含多个元素。 队列中所有元素呈线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 出队 入队 队首元素 队尾元素 队列的特性 duilie de texing 6 1.幼儿园小朋友们排队玩华护体，轮流爬上去，再轮流滑下来，此过程用那种数据结构描述最合适（ ） A.链表 B.字典 C.栈 D.队列 练一练 lianyilian D 7 2.下列事件执行过程与队列特征不相符的是（ ） A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 练一练 lianyilian C 8 队列的基本操作 队列的存储结构 建队 入队 出队 02 9 队列的存储结构：队列一般按顺序结构存储，可以用数组来实现。设置头指针head记录队首元素位置，尾指针tail队尾元素的下一个位