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

3.2 队列 去银行、医院办理业务时，取号机能 按照到达时间的先后顺序，合理地安 排办事次序。 这些事件对数据的处理都具有排队的 特性，可以使用队列来解决。 队列的概念与特性 一、队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个 元素称为出队。 n1 n2 n3 n4 nn … 队尾元素 队首元素 入队 出队 图1 二、队列的特性 （1）先进先出、后进后出 由队列的定义可知，队列具备“先进先出、后进后出”的特点。如图1所示， 出队时，队首元素n1优先出队，紧接着是n2,n3,…nn，队尾元素nn最后出队。 （2）有限序列性 队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含 多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素 只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 队列的基本操作 队列一般按顺序结构存储，可以用数组来实现。如下图所示，数组que中存储了一个 队列、共有4个元素，队首元素为a1，队尾元素为a4。由于在入队和出队的过程中， 队首元素和队尾元素在数组que中的位置在改变，因此需要设置头指针变量head和尾 指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。 a1 a2 a3 a4 0 1 2 3 队列的存储 a1 a2 a3 a4 0 1 2 3 4 0 1 2 3 4 tail head 数组que的下标 head tail 队列的head、tail指针变化图 对于下图所示的队列，初始时，head指针变量与tail指针变量均记录下标为 0的位置。元素a1、a2、a3、a4依次入队后，tail值为4,head值为0。 当a1、a2出队后，head记录下标为2的位置，tail值不变。当a3、a4出队后， head与tai的值均为4，队列为空。 队列的常用操作有建队、入队、出队等。 1.建队 由于队列以数组形式存储，因此python中用列表创建队列。例如，有4个字母 “A”“B”“C”“D”按序入队、出队时，可以创建一个队列que，长度为5， python代码如下所示： head=0 tail=0 que=[“”]*