【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 秒;
  • 每次只能过两个人。 过去后,对岸 要有一个人再把灯送回来。

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学