河池学院：《数据结构》课程电子教案（PPT教学课件）第3章 栈和队列 3.2 队列

队列的定义顺序队链队32队列Java中的队列容器Queue队列的综合应用双端队列优先队列1/92

3.2 队列 链 队 队列的综合应用 顺 序 队 队列的定义 Java中的队列容器Queue 双 端 队 列 优 先 队 列 1/92

队列的定义3.2.1队列（queue）是一种只能在不同端进行插入或删除操作的线性表。进行插入的一端称做队尾（rear），进行删除的一端称做队头或队首（front）。队列的插入操作通常称为进队或入队（push），队列的删除操作通常称为出队或离队（pop）。进队aia,出队个个队头队尾2/92

队列（queue）是一种只能在不同端进行插入或删除操作的线性表。 进行插入的一端称做队尾（rear），进行删除的一端称做队头或队 首（front）。 队列的插入操作通常称为进队或入队（push），队列的删除操作通 常称为出队或离队（pop）。 a1 a2 . an 队头 队尾 出队 进队 2/92

田front排队买早餐tail3/92

3/92

队列的主要特点：先进先出，即先进队的元素先出队。每次进队的元素作为新队尾元素，每次出队的元素只能是队头的元素。队列也称为先进先出表。4/92

先进先出，即先进队的元素先出队。 每次进队的元素作为新队尾元素，每次出队的元素只能是队头的 元素。 队列也称为先进先出表。 队列的主要特点： 4/92

ADTQueue(数据对象：D=[ai0≤i≤n-1,n≥0,a,为E类型]数据关系：R=(r}r=[ I ai, ai+iED, i=0, ."", n-2]基本运算：boolean empty()：判断队列是否为空，若队列为空，返回真，否则返回假。voidpush(Ee)：进队，将元素e进队作为队尾元素。E pop()：出队，从队头出队一个元素。Epeek()：取队头，返回队头元素而不出队。队列抽象数据类型=线性结构+队列的基本运算5/92

队列抽象数据类型 = 线性结构 + 队列的基本运算 ADT Queue { 数据对象： D={ai | 0≤i≤n-1，n≥0，ai为E类型} 数据关系： R={r} r={ | ai，ai+1∈D， i=0，.，n-2} 基本运算： boolean empty()：判断队列是否为空，若队列为空，返回真，否则返回假。 void push(E e)：进队，将元素e进队作为队尾元素。 E pop()：出队，从队头出队一个元素。 E peek()：取队头，返回队头元素而不出队。 } 5/92

【例3.10】若元素进队顺序为1234，能否得到3142的出队序列？解：进队顺序为1234，则出队的顺序也为1234（先进先出），所以不能得到3142的出队序列。6/92

【例3.10】若元素进队顺序为1234，能否得到3142的出队序列？ 解：进队顺序为1234，则出队的顺序也为1234（先进先出），所以 不能得到3142的出队序列。 6/92

队列的顺序存储结构及其基本运算算法实现3.2.2队列的实现方式逻辑结构U队列线性表映射链队链表顺序队顺序表存储结构7/92

队列的实现方式 线性表 顺序表 链表 队列 顺序队 链队 逻辑结构 存储结构 映射 ∩ 7/92

用data数组来存放队列中元素。约定：队头指针为front（实际上是队头元素的前一个位置），队尾指针为rear（正好是队尾元素的位置）。aean-1-frontrear8/92

. a0 a1 . an-1 . front rear 用data数组来存放队列中元素。 约定：队头指针为front（实际上是队头元素的前一个位置），队尾指针 为rear（正好是队尾元素的位置）。 8/92

1.非循环队列初始时置front和rear均为-1（front==rear）元素进队，rear增加1元素出队列，front增加1an-frontrear9/92

1. 非循环队列 初始时置front和rear均为-1（front==rear） 元素进队，rear增加1 元素出队列，front增加1 9/92 . a0 a1 . an-1 . front rear

rear40eerearrearfrontdd332C22bb1100front0a4-1-1-1-1front→front →rear（a）空队（b）5个元素进队（c）出队1次（c）出队4次18/92

4 3 2 1 0 （a）空队 front -1 rear e d c b （b）5个元素进队 4 3 2 1 0 -1 a rear front e d c b （c）出队1次 4 3 2 1 0 -1 rear front （c）出队4次 4 3 2 1 0 -1 rear front 10/92