(
课件网) 队列 授课人：**** 队列：队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。 队列的概念 出队 入队 队首元素 队尾元素 队列元素：队列中的数据元素 入 队：在队列中插入一个元素的过程 出 队：从队列中删除一个元素的过程 有限序列性：线性表结构，元素个数有限的 先进先出、后进后出（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 课堂小结 队列 一、队列的概念（先进先出的线性表……） 二、队列的特性（先进先出、有限序列性） 三、队列的基本操作（建队、入队、出队） 同学们！下课啦！ ... ...
