3.2 队列

队列 字符串、队列和栈 Educational courseware 主讲人：胡思杭 情景导入 食堂窗口打餐 火车站买票 银行叫号取号 计算机打印队列 ...... 队列的概念 已出队元素 队列元素 队首元素 队尾元素 队列的概念： 队列是一种先进先出的线性表 允许插入的一端称为队尾 允许删除的一段称为队首 队首 队尾 队列的特性 入队：在队列中插入一个元素的过程 出队：在队列中删除一个元素的过程 先进先出，后进后出 队首元素：只有一个后驱节点 队尾元素：只有一个前驱节点 既有前驱，又有后驱 出队 入队 有限序列性：队列是一种线性表结构，元素的个数也是有限的 队列的基本操作 队列一般按顺序结构储存，可以用数组来实现 如下图,数组que中储存了一个队列，共有3个元素，队首元素为a1，队尾元素为a3 由于在入队和出队的过程中，队首元素和队尾元素在数组que中的位置发生改变，因此需要头指针变量head和尾指针变量tail，head记录队首元素所在位置，tail记录队尾元素所在位置 a1 a2 a3 0 1 2 3 数组元素 数组下标 0 1 2 3 head tail head=0 tail=0 队列为空：tail=head 队列的基本操作 1.建队 head=0 tail=0 que=[“ ”]*5 2.入队 A 0 1 2 3 A B 0 1 2 3 A B C 0 1 2 3 tail tail tail head head head B入队： que[tail] =“B” tail+=1 C入队： que[tail] =“C” tail+=1 新元素入队： que[tail] =“新元素” tail+=1 队列的基本操作 3.出队 A B C 0 1 2 3 B C 0 1 2 3 C 0 1 2 3 tail tail tail head=head+1 0 1 2 3 tail head head head head 此时head=tail=3，还可以有新元素入队吗？ 假溢出 知识拓展 顺序队列的假溢出:随着队首元素出队会慢慢的空出一个个储存单元，但是队尾一直在进，最后导致前面的储存空间未满就队列就满了 解决办法：将顺序队列做成循环队列！ 队列的基本操作 A B C 0 1 2 3 tail head 0 1 2 3 tail head 队首元素： 队尾元素： 入队： 出队： 判断非空队： 求队列长度： que[head] que[tail] =“新元素”；tail+=1 head=head+1 if head != tail tail-head que[tail-1] 课后练习 1.已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( ) A.head=0, tail=6 B. head=6,tail=0 C. head=3,tail=2 D. head=3,tail=8 D 课后练习 2.用 python 列表模拟循环队列，并设置队首指针head指向队首元素，队尾指针指向队尾元素的下一个位置,则当列表长度 n=10，head=6，tail=3 时，队列中元素的个数为( ) A.5 B.6 C.7 D.8 C 感谢您的观看 Thank you for watching 主讲人：张小可 $$