NK数据结构06.pdfVIP

数据结构与程序设计 南开大学软件学院 2002-2003李耀国 1 Chapter 6 Queues ? 6.1 The Abstract Data Type ? 6.2 Formula-Based Representation ? 6.3 Linked Representation ? 6.4 Application 2 Chapter 6 Queues ? 我们已经学习过堆栈，是一种受限制的线性表，队 列也是一种特殊的线性表。队列的插入和删除操作 分别在线性表的两端进行，因此，队列是一个先进 先出（first-in-first-out,FIFO ）的线性表。尽管 可以很容易地从线性表类LinearList和链表类 Chain 中派生出队列类，但在本章中并没有这样 做。出于对执行效率的考虑，我们把队列设计成一 个基类，分别采用了公式化描述和链表描述。 3 Chapter 6 Queues ? 在应用部分，给出了四个使用队列的应用。 ? 1. 关于上节所介绍的火车车厢重排问题。在本章中对这 个问题做了修改，要求缓冲铁轨按FIFO方式而不是 LIFO方式工作； ? 2. 关于寻找两个给定点之间最短路径的问题，这是一个 经典的问题。可以把这个应用看成是迷宫老鼠问题的一 种变化，即寻找从迷宫入口到迷宫出口的最短路径。 ? 3. 计算机视觉领域，主要用于识别图像中的图元； ? 4. 一个工厂仿真程序。我们给出了一个仿真程序，它能 够仿真工厂中的任务流。该程序能够确定每项任务所花 费的总的等待时间以及每台机器所产生的总的等待时 间，可以根据这些信息来改进工厂的设计。 4 6.1The Abstract Data Type ? 定义[队列]：队列（queue）是一个线性表， 其插入和删除操作分别在表的不同端进行。 添加新元素的那一端被称为队尾(rear) ，而 删除元素的那一端被成为队首(front)。 front rear front rear front rear A B C B C B C D 5 6.1The Abstract Data Type 抽象数据类型Queue{ 实例 有序线性表，一端称为front ，另一端称为rear； 操作 Create(): 创建一个空的队列； IsEmpty(): 如果队列为空，则返回true ，否则返回 false ； IsFull(): 如果队列满，则返回true；否则返回false ； First(): 返回队列的第一个元素； Last(): 返回队列的最后一个元素； Add(x): 向队列中添加元素x； Delete(x): 删除队首元素，并送入x; }//ADT6-1队列的抽象数据类型描述