《内蒙古大学《算法与数据结构》讲义06队列》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义06队列（29页珍藏版）》请在金锄头文库上搜索。
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
2、方式而不是L I F O方式工作；第二个应用是关于寻找两个给定点之间最短路径的问题，这是一个经典的问题。可以把这个应用看成是5 . 5 . 6节迷宫问题的一种变化，即寻找从迷宫入口到迷宫出口的最短路径。 5 . 5 . 6节中的代码并不能保证得到一条最短的路径，它只能保证如果存在一条从入口到出口的路径，则一定能找到这样一条路径（没有限定长度） ；第三个应用选自计算机视觉领域，主要用于识别图像中的图元；最后一个应用是一个工厂仿真程序。工厂内有若干台机器，每台机器能够执行一道不同的工序。每一项任务都由一系列工序组成。我们给出了一个仿真程序，它能够仿真工厂中的任务流。该程序能够确定每项任务所花费的总
3、的等待时间以及每台机器所产生的总的等待时间，可以根据这些信息来改进工厂的设计。为了获得较高的执行效率，本章中每个应用都采用了队列数据结构。在后续章节中还会介绍其他几种队列应用。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 所示。图
4、6-1 队列举例所以，队列是一个先进先出（ F I F O）的线性表，而堆栈是一个先进后出（ L I F O）的线性表。队列的抽象数据类型描述见ADT 6-1。a)b)c)ADT6-1 队列的抽象数据类型描述抽象数据类型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 ( ) :返回队列的最后一
5、个元素；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）
6、 ，图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） ，就可以使队列的删除操作所需要的时
7、间减小至( 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 e a r =location (最后一个元素)，一个空队列1 9 0第二部分数 据 结 构下载a)b)c)具有性质r e a r f r o n t。如图6-3b 所示，每次删除操作将导致f r o
8、 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） ，则队列的添加和删除操作在最
9、坏情况下的时间复杂性均变成( 1 )。location (i) = (location (1) + i -1) % M a x S i z e（6 - 3）这时，用来描述队列的数组被视为一个环（如图 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)当且
10、仅当 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
11、 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 ) ;队列的成员函数与堆栈的对应函数相类似，因此这里不再
12、具体介绍这些函数。当 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 MaxQueueSize = 10);Queue() delete queue;bool IsEmpty() const return front = rear;bool IsFull() const retu
13、rn (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
14、e个元素的循环队列Queue:Queue(int MaxQueueSize)/ 创建一个容量为 M a x Q u e u e S i z e的空队列MaxSize = MaxQueueSize + 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:
15、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:
16、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
