内蒙古大学《算法与数据结构》讲义06队列

1、下载第6章队列像堆栈一样，队列也是一种特殊的线性表。队列的插入和删除操作分别在线性表的两端进行，因此，队列是一个先进先出（ first-in-first-out, FIFO）的线性表。尽管可以很容易地从线性表类L i n e a r L i s t（见程序3 - 1）和链表类C h a i n（见程序3 - 8）中派生出队列类，但在本章中并没有这样做。出于对执行效率的考虑，我们把队列设计成一个基类，分别采用了公式化描述和链表描述。在本章的应用部分，给出了四个使用队列的应用。第一个应用是关于 5 . 5 . 3节所介绍的火车车厢重排问题。在本章中对这个问题做了修改，要求缓冲铁轨按 F I F O方式而不是L I F O方式工作；第二个应用是关于寻找两个给定点之间最短路径的问题，这是一个经典的问题。可以把这个应用看成是5 . 5 . 6节迷宫问题的一种变化，即寻找从迷宫入口到迷宫出口的最短路径。 5 . 5 . 6节中的代码并不能保证得到一条最短的路径，它只能保证如果存在一条从入口到出口的路径，则一定能找到这样一条路径（没有限定长度） ；第三个应用选自计算机视觉领域，主要用于识别图像中的图

2、元；最后一个应用是一个工厂仿真程序。工厂内有若干台机器，每台机器能够执行一道不同的工序。每一项任务都由一系列工序组成。我们给出了一个仿真程序，它能够仿真工厂中的任务流。该程序能够确定每项任务所花费的总的等待时间以及每台机器所产生的总的等待时间，可以根据这些信息来改进工厂的设计。为了获得较高的执行效率，本章中每个应用都采用了队列数据结构。在后续章节中还会介绍其他几种队列应用。6.1 抽象数据类型定义队列 队列（q u e n e）是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾( r e a r )，而删除元素的那一端被成为队首( f r o n t )。一个三元素的队列如图6-1a 所示，从中删除第一个元素 A之后将得到图6-1b 所示的队列。如果要向图6-1b 的队列中添加一个元素 D，必须把它放在元素C的后面。添加D以后所得到的结果如图6-1c 所示。图6-1 队列举例所以，队列是一个先进先出（ F I F O）的线性表，而堆栈是一个先进后出（ L I F O）的线性表。队列的抽象数据类型描述见ADT 6-1。a)b)c)ADT6-1 队列的抽象数据

3、类型描述抽象数据类型Queue 实例有序线性表，一端称为f r o n t，另一端称为r e a r；操作C reate (): 创建一个空的队列；IsEmpty (): 如果队列为空，则返回t r u e，否则返回f a l s e；IsFull ( ) :如果队列满，则返回t r u e；否则返回f a l s e；First (): 返回队列的第一个元素；Last ( ) :返回队列的最后一个元素；Add (x): 向队列中添加元素 x；Delete (x): 删除队首元素，并送入x;6.2 公式化描述假定采用公式（6 - 1）来描述一个队列。location (i) = i- 1（6 - 1）这个公式在公式化描述的堆栈中工作得很好。如果使用公式（ 6 - 1）把数组q u e u e M a x S i z e 描述成一个队列，那么第一个元素为 q u e u e 0 ，第二个元素为q u e u e 1 ，。f r o n t总是为0，r e a r始终是最后一个元素的位置，队列的长度为 r e a r + 1。对于一个空队列，有 r e a r =1。使用公式（6 - 1）

4、 ，图6 - 1中的队列可以表示成图6 - 2的形式。图6-2 使用公式（6 - 1）描述图6 - 1中的队列向队列中添加一个元素时，需要把r e a r增1，并把新元素放入q u e u e r e a r 。这意味着一次添加操作所需要的时间为O ( 1 )。删除一个元素时，把位置1至位置n的元素分别左移一个位置，因此删除一个元素所花费的时间为( n )，其中n为删除完成之后队列中的元素数。如此看来，公式（6 - 1）应用于堆栈，可使堆栈的插入和删除操作均耗时( 1 )，而应用于队列，则使队列的删除操作所需要的时间达到( n )。如果采用公式（6 - 2） ，就可以使队列的删除操作所需要的时间减小至( 1 )。location (i) = location (1) + i- 1（6 - 2）从队列中删除一个元素时，公式（ 6 - 2）不要求把所有的元素都左移一个位置，只需简单地把location ( 1 )增加1即可。图6 - 3给出了在使用公式（6 - 2）时，图6 - 1中各队列的相应描述。注意，在使用公式（6 - 2）时，f r o n t =location ( 1 )，r

5、e a r =location (最后一个元素)，一个空队列1 9 0第二部分数 据 结 构下载a)b)c)具有性质r e a r f r o n t。如图6-3b 所示，每次删除操作将导致f r o n t右移一个位置。当r e a r 0时（表明队列未满） ，为了能够继续向队列尾部添加元素，必须将所有元素平移到队列的左端（如图 6 - 4所示） ，以便在队列的右端留出空间。对于使用公式（ 6 - 1）的队列来说，这种平移操作将使最坏情况下的时间复杂性增加( 1 )，而对于使用公式（6 - 2）的队列来说，最坏情况下的时间复杂性则增加了( n )。所以，使用公式（6 - 2）在提高删除操作执行效率的同时，却降低了添加操作的执行效率。图6-3 使用公式（6 - 2）描述图6 - 1中的队列图6-4 队列的平移a) 移位之前b) 移位之后若使用公式（6 - 3） ，则队列的添加和删除操作在最坏情况下的时间复杂性均变成( 1 )。location (i) = (location (1) + i -1) % M a x S i z e（6 - 3）这时，用来描述队列的数组被视为一个环（如图

6、6 - 5所示） 。在这种情况下，对f r o n t的约定发生了变化，它指向队列首元素的下一个位置（逆时针方向） ，而r e a r的含义不变。向图 6 - 5 a中的队列添加一个元素将得到图 6-5b 所示的队列，而从图6-5b 的队列中删除一个元素则得到图6-5c 所示的队列。图6-5 循环队列a) 初始状态b) 添加c) 删除第6章队列1 9 1下载a) b) a)b)c)a)b)c)当且仅当 front=rear 时队列为空。初始条件f r o n t = r e a r = 0定义了一个初始为空的队列。现在需要确定队列为满的条件。如果不断地向图6-5b 的队列添加元素，直到队列满为止，那么将看到图 6 - 6所示的情形。这时有f r o n t = r e a r，竟然与队列为空的条件完全一样！因此，我们无法区分出队列是空还是满。为了避免这个问题，可以不允许队列被填满。为此，在向队列添加一个元素之前，先判断一下本次操作是否会导致队列被填满，如果是，则报错。因此，队列的最大容量实际上是M a x S i z e - 1。可用程序6 - 1所示的C + +类来实现抽象数据类型Q

7、 u e u e。在实现公式化描述的堆栈时（见程序5 - 1） ，为了简化代码的设计，重用了LinearList 类（见程序3 - 1）的定义。然而不能通过使用同样的方法来实现Queue 类，因为Queue 的实现基于公式（6 - 3） ，而L i n e a r L i s t的实现基于公式（6 - 1） 。程序6 - 2和程序6 - 3给出了Queue 成员函数的代码。注意观察Queue 的构造函数是怎样保证循环队列的容量比数组的容量少 1的。利用如下语句，可以创建一个能够容纳 1 2个整数的队列：Q u e u e Q ( 1 2 ) ;队列的成员函数与堆栈的对应函数相类似，因此这里不再具体介绍这些函数。当 T是一个内部数据类型时， 队列构造函数和析构函数的复杂性均为( 1 )；而当T是一个用户定义的类时，构造函数和析构函数的复杂性均为O ( M a x S t a c k S i z e )。其他队列操作的复杂性均为( 1 )。程序6-1 公式化类Q u e u etemplateclass Queue / FIFO 对象p u b l i c :Queue(int MaxQu

8、eueSize = 10);Queue() delete queue;bool IsEmpty() const return front = rear;bool IsFull() const return (rear + 1) % MaxSize = front) ? 1 : 0);T First() const; /返回队首元素T Last() const; / 返回队尾元素Queue& Add(const T& x);Queue& Delete(T& x);p r i v a t e :int front; /与第一个元素在反时针方向上相差一个位置int rear; / 指向最后一个元素int MaxSize; / 队列数组的大小T *queue; / 数组 ;程序6-2 Queue类的成员函数template1 9 2第二部分数 据 结 构下载图6-6 能容纳M a x S i z e个元素的循环队列Queue:Queue(int MaxQueueSize)/ 创建一个容量为 M a x Q u e u e S i z e的空队列MaxSize = MaxQueueSize +

9、1;queue = new TMaxSize;front = rear = 0;templateT Queue:First() const/ 返回队列的第一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();return queue(front + 1) % MaxSize;templateT Queue:Last() const/ 返回队列的最后一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();return queuerear;程序6-3 Queue类的成员函数templateQueue& Queue:Add(const T& x)/ 把 x 添加到队列的尾部/ 如果队列满，则引发异常NoMem if (IsFull() throw NoMem();rear = (rear + 1) % MaxSize;queuerear = x;return *this;templateQueue& Queue:

10、Delete(T& x)/ 删除第一个元素，并将其送入x/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();front = (front + 1) % MaxSize;x = queuefront;return *this;练习1. 扩充队列的A D T，增加以下函数：1) 确定队列中的元素数目。第6章队列1 9 3下载2) 输入一个队列。3) 输出一个队列。2. 扩充队列的A D T，增加以下函数：1) 把一个队列分解成两个队列，其中一个队列包含原队列中的第 1、3、5、 个元素，另一个队列包含了其余元素。2) 合并两个队列（称队列1和队列2） ，在新队列中，从队列1开始，两个队列的元素轮流排列，若某个队列中的元素先用完，则将另一个队列中的剩余元素依次添加在新队列的尾部。合并完成后，各元素之间的相对次序应与合并前的相对次序相同。请扩充公式化描述的队列类的定义，增加以上两个成员函数。编写并测试代码。3. 使用公式（6 - 2）设计一个相应的C + +队列类，编写并测试所有代码。4. 修改程序6 - 1

《内蒙古大学《算法与数据结构》讲义06队列》由会员东***分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义06队列》请在金锄头文库上搜索。