【3.2】队列

一、队列的定义

先进先出 (First In First Out)

• 限制访问点的线性表
• 按照到达的顺序来释放元素
• 所有的插入在表的一端进行，所有的删除都在表 的另一端进行

主要元素：

• 队头 (front)
• 队尾 (rear)

队列的主要操作：

• 入队列 (enQueue)
• 出队列 (deQueue)
• 取队首元素 (getFront)
• 判断队列是否为空 (isEmpty)

队列的抽象数据类型

二、队列的实现方式

• 顺序队列 – 关键是如何防止假溢出
• 链式队列– 用单链表方式存储，队列中每个元素对于链 表中的一个结点

队列示意:环形(实指)

2.1 顺序队列

顺序队列的类定义

顺序队列的维护

顺序队列代码实现

思考：

1. 只是用front,rear两个变量，长度为 mSize = n 的队列，可以容纳的最大元素个 数为多少? 请给出详细的推导过程。
2. 如果不愿意浪费队列的存储单元，还 可以采用什么方法?

2.2 链式队列

链式队列的表示：

• 单链表队列
• 链接指针的方向是从队列的前端向尾端链接

链式队列的类定义

链式队列代码实现

2.3 顺序队列与链式队列的比较

• 顺序队列 – 固定的存储空间
• 链式队列– 可以满足大小无法估计的情况

都不允许访问队列内部元素

三、队列的应用

• 只要满足先来先服务特性的应用均可采用队列 作为其数据组织方式或中间数据结构
• 调度或缓冲
• 消息缓冲器
• 邮件缓冲器
• 计算机硬设备之间的通信也需要队列作为数据缓冲
• 操作系统的资源管理
• 宽度优先搜索

思考：

• 链式队列往往用单链表。 为什么不用双链表来实现?
• 若采用虚指方法实现队尾指针(rear指向 队尾元素后一个元素，和实指相比后移一 位)，在具体实现上有何异同?哪一种更 好?

3.1 农夫过河问题

数据抽象：

每个角色的位置进行描述

• 农夫、狼、菜和羊，四个目标各用一位(假定 按照农夫、狼、白菜、羊次序)，目标在起始 岸位置:0，目标岸:1
• 如 0101 表示农夫、白菜在起始岸，而狼、羊 在目标岸(此状态为不安全状态)

数据的表示：

确定每个角色位置的函数：

算法抽象：

问题变为：

从状态0000(整数0)出发，寻找全部 由安全状态构成的状态序列，以状态1111 (整数15)为最终目标。

• 状态序列中 每个 状态都可以从前一状 态通过农夫(可以带一样东西)划船过 河的动作到达。
• 序列中不能出现 重复 状态

算法设计：

• 定义一个整数队列 moveTo，它的每个元素表示一 个可以安全到达的中间状态
• 还需要定义一个数据结构 记录已被访问过的各个状 态，以及已被发现的能够到达当前这个状态的路径
• 用顺序表 route 的第 i 个元素记录状态i是否已被访问过
• 若 route[i] 已被访问过，则在这个顺序表元素中记入前驱状态值; -1表示未被访问
• route 的大小(长度)为 16

算法实现：

3.2 另一个小游戏

五人提灯过独木桥:

• 有一盏灯能使用30秒，要在灯熄灭 前过这座桥;
• 一家五口人每个人过桥的速度不同: 哥哥 1 秒，弟弟 3 秒，爸爸 6 秒， 妈妈 8 秒，奶奶 12 秒;
• 每次只能过两个人。 过去后，对岸 要有一个人再把灯送回来。

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾