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

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

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

3/92

先进先出，即先进队的元素先出队。 每次进队的元素作为新队尾元素，每次出队的元素只能是队头的 元素。 队列也称为先进先出表。 队列的主要特点： 4/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

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

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

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

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