《数据结构：思想与方法》第四章队列

1第四章队列队列的概念队列的实现队列类的实现STL中的队列队列的应用2队列队列是另外一种常用的线性结构，到达越早的结点，离开的时间越早。所以队列通常称之为先进先出(FIFO:FirstInFirstOut)队列。如：我们在银行储蓄柜前排队取款，计算机中打印管理器对打印队列的处理都采用了这种先来先服务的方式。可以将队列想象为一段管道，结点从一端流入，从另一端流出。流入端通常称之为队尾，而流出端称之为队首。3队列的基本概念出队入队队尾队头4队列的基本操作创建一个队列create()：创建一个空的队列；入队enQueue(x)：将x插入队尾，使之成为队尾元素；出队deQueue()：删除队头元素并返回队头元素值；读队头元素getHead()：返回队头元素的值；判队列空isEmpty()：若队列为空，返回true，否则返回false。5队列队列的概念队列的实现队列类的实现STL中的队列队列的应用6队列的具体实现队列的顺序实现队列的链接实现7队列的顺序存储使用数组存储队列中的元素队列中的结点个数最多为MaxSize个元素下标的范围从0到MaxSize-1。顺序队列的三种组织方式队头位置固定队头位置不固定循环队列8队头位置固定队头固定在下标0用一个变量指出队尾位置队列为空时，队尾位置为-19队头位置固定fedcba0Maxsize-1reara出队fedcb0Maxsize-1rear缺点：出队会引起大量的数据移动10队头位置不固定使用队首指针front和队尾指针rear，分别指示队首结点的前一位置和队尾结点存放的下标地址，用于删除队首结点和指示到何处去排队队列初始化时，设front=rear(都为-1)，即队空的标志：front=rear队满标志：rear=MaxSize-111fedcba0Maxsize-1reara出队frontfedcb0Maxsize-1rearfront特点：所有操作都是O（1）浪费空间12循环队列结点E进队后frontrearDCE从逻辑上认为单元0就是单元MaxSizeDCfrontrear13MaxSize-101……frontrear入队操作：rear=(rear

+1)%MaxSize；elem[rear]=x。出队操作：front=(front+1)%MaxSize。14问题如何确定队列为空和队列满？创建一个队列时，可以将front和rear都设为0来表示空队列。但经过了多次的入队和出队后，front和rear都不在0的位置。15出队后队列变空即队列中应该只有一个元素。此时rear和front相邻，rear在front后面。执行front=(front+1)%MaxSize后，front和rear相同。因此队列为空时，front=rearfrontrearMaxSize-1016入队后队列满此时数组中只剩下一个空单元，就是front指向的单元。执行入队操作后，rear按顺时针向后移一个单元，与front重叠。frontrear17解决方案“牺牲”一个单元，规定front指向的单元不能存储队列元素，只起到标志作用，表示后面一个是队头元素。当rear“绕一卷”赶上front时，队列就满了。因此队列满的条件是：(rear+1)%MaxSize==front队列为空的条件是front==rear，即队头追上了队尾。18队列基本运算的实现create()：申请一块空间，首地址存入elem。数组规模保存在MaxSize中，front和rear置成0。enQueue(x)：首先要判断数组是否已放满，这可以通过判别(rear+1)%MaxSize是否等于front来实现。如果数组已满。与顺序表的处理相同，可以有两种方案：终止入队操作或扩展数组空间。如果不等，表示元素可以入队。先通过语句rear=(rear+1)%MaxSize将rear往后移一个位置，然后执行elem[rear]=x。deQueue()：将front往后移一个位置，即执行front=(front+1)%MaxSize。然后返回elem[front]的内容。getHead()：返回elem[(front+1)%MaxSize]的内容isEmpty()：判断front是否等于rear。若相等，返回true，否则返回false。19队列的具体实现队列的顺序实现队列的链接实现20队列的链接实现由于队列的操作是在队列的两端进行的，不会对队列中的其他元素进行操作，用单链表就足够了。队列要对表的两端作操作，为方便两端操作，我们可以采用空间换时间的方法，同时记住头尾结点的位置。哪一端作为队头，哪一端作为队尾呢？队尾指出的是插入位置，对单链表来说，有了尾指针，在表头插入和表尾插入一样简单。但对于删除来说，删除表头元素很简单，但删除表尾元素必须知道它前一元素的存储地址，因此在表尾删除要花O（N）的时间。为此可以将单链表的表头作为队头，单链表的表尾作为队尾21队列的链接实现用无头结点的单链表表示队列，表头为队头，表尾为队尾frontrear22链接队列的特点链接队列不会出现队列满的情况，但队列为空的情况依然存在。队列为空时，单链表中没有结点存在，即头尾指针都为空指针。保存一个链接队列只需要两个指向单链表结点的指针front和rear，分别指向头尾结点。采用链接存储时，队列的基本运算的实现也非常简单，都是O（1）的时间复杂度。23队列操作的实例初始时：front=NULL;rear=NULL;A进队：frontrearAB进队：frontrearAB24C进队：frontrearABC出队：frontrearBC出队：frontrearC出队：front=NULL;rear=NULL;D进队：frontrearD25create()将front和rear设为空指针。26enQueue(x)首先申请一个结点存储x；将结点x作为单链表的表尾，即rear指向的结点的指针部分指向结点x，将结点x作为尾结点。注意，enQueue操作有个特殊情况，就是队列为空的情况。此时，我们只需要申请一个存放x的结点，让front和rear同时指向这个结点。27voidenQueue(x){p=new结点；

p指向结点的数据部分=x；

p指向结点的指针部分=NULL；

if(rear==NULL)front=rear=p;else{rear指向的结点的指针部分=p；

rear=p;}}28deQueue()返回front指向的结点的值并删除该结点。删除表头结点需要先将表头结点从链表中摘下，然后释放表头结点的空间。注意，deQueue操作有一个特殊情况，即如果执行deQueue操作时队列中只有一个元素，经过deQueue操作，队列为空，此时必须将front和rear同时置成NULL。29dataTypedeQueue(){p=front;x=p指向结点的数据部分；front=front指向的结点的指针部分；deletep；if(front==NULL)rear=NULL;

返回x的值;}30getHead()和isEmpty()getHead()：返回front指向的结点的值。isEmpty()：检查front或rear的值即可。若值为空指针，返回true，否则返回false。31队列队列的概念队列的实现队列类的实现STL中的队列队列的应用32队列类的抽象类template<classelemType>classqueue{public:virtualboolisEmpty()=0;//判队空

virtualvoidenQueue(constelemType&x)=0;//进队

virtualelemTypedeQueue()=0;//出队

virtualelemTypegetHead()=0;//读队头元素

virtual~queue(){}//虚析构函数

};33循环队列类的设计循环队列类由队列的抽象类派生循环队列存储：elem为存储队列元素的数组名，maxSize为数组的规模，front和rear为队头和队尾标记。公有成员函数：构造和析构，以及抽象类的所有函数私有的成员函数doubleSpace34循环队列类的定义template<classelemType>classseqQueue:publicqueue<elemType>{private:elemType*elem; intmaxSize; intfront,rear;

voiddoubleSpace();

35public:seqQueue(intsize=10){elem=newelemType[size];maxSize=size;front=rear=0;} ~seqQueue(){deleteelem;}boolisEmpty(){returnfront==rear;}voidenQueue(constelemType&x);elemTypedeQueue();elemTypegetHead(){returnelem[(front+1)%maxSize];}};36doubleSpacetemplate<classelemType>voidseqQueue<elemType>::doubleSpace(){elemType*tmp=elem;elem=newelemType[2*maxSize];for(inti=1;i<maxSize;++i) elem[i]=tmp[(front+i)%maxSize];

front=0;rear=maxSize-1;maxSize*=2;deletetmp;}注意和线性表的doubleSpace的不同之处37enQueuetemplate<classelemType>voidseqQueue<elemType>::enQueue(constelemType&x){if((rear+1)%maxSize==front)doubleSpace();rear=(rear+1)%maxSize;elem[rear]=x;}38deQueuetemplate<classelemType>elemTypeseqQueue<elemType>::deQueue(){front=(front+1)%maxSize;returnelem[front];}39链接队列类的设计数据成员：头尾指针头尾指针的类型：指向结点（数据，下一结点地址）成员函数：构造和析构函数抽象类规定的功能40链接队列类的定义template<classelemType>classlinkQueue:publicqueue<elemType>

{private:structnode{elemTypedata;

node*next; node(constelemType&x,node*N=NULL){ data=x;next=N;} node():next(NULL){} ~node(){} }; node*front,*rear;41public:linkQueue(){front=rear=NULL;}

~linkQueue();boolisEmpty(){returnfront==NULL;}voidenQueue(constelemType&x);elemTypedeQueue();

elemTypegetHead(){returnfront->data;}

};

42析构函数template<classelemType>linkQueue<elemType>::~linkQueue(){ node*tmp; while(front!=NULL){ tmp=front; front=front->next; deletetmp; }}43enQueuetemplate<classelemType>voidlinkQueue<elemType>::enQueue(constelemType&x){if(rear==NULL) front=rear=newnode(x);else{ rear->next=newnode(x); rear=rear->next; }}44deQueuetemplate<classelemType>elemTypelinkQueue<elemType>::deQueue(){ node*tmp=front;

elemTypevalue=front->data; front=front->next; if(front==NULL)rear=NULL; deletetmp; returnvalue;}45队列类的应用intmain(){linkQueue<int>s;for(inti=0;i<10;++i)s.enQueue(2*i);while(!s.isEmpty())cout<<s.deQueue()<<'';cout<<endl;输出：02468101214161846for(i=0;i<15;++i)s.enQueue(i);while(!s.isEmpty()) cout<<s.deQueue()<<'';cout<<endl;

return0;}输出：0123456789101112131447顺序实现和链接实现的比较时间：两者都能在常量的时间内完成基本操作，但顺序队列由于采用回绕，使入队和出队的处理比较麻烦空间：链接队列中，每个结点多一个指针字段，但在顺序队列中有大量的尚未使用的空间。48队列队列的概念队列的实现队列类的实现STL中的队列队列的应用49STL中的队列STL中的队列类是一个容器适配器，队列可以借助的容器有vector,list和deque。定义一个队列对象要指明队列中元素的类型以及借助于哪一个容器，因此队列的类模板有两个模板参数：队列元素类型和所借助的容器类型。队列的类模板的第二个参数带有缺省值deque50STL中的队列STL中的队列提供六个运算：入队操作push：调用push_back出队操作pop：调用pop_front获得队头元素的操作front：调用front函数获得队尾元素的函数back：调用back函数判队列为空的函数empty：调用empty函数获得队列长度的函数size：调用size函数51STL队列的使用#include<iostream>#include<queue>usingnamespacestd;intmain(){queue<int,list<int>>q1;queue<int,deque<int>>q2;//也可以写成queue<int>q2;inti;

for(i=0;i<10;++i)q1.push(i);

while(!q1.empty()){cout<<q1.front()<<'';q1.pop();}cout<<endl;for(i=0;i<10;++i)q2.push(i);

while(!q2.empty()){cout<<q2.front()<<'';q2.pop();}cout<<endl; return0;}52队列队列的概念队列的实现队列类的实现STL中的队列队列的应用53排队系统的模拟模拟（simulation）是计算机的一个重要应用，是指用计算机来仿真现实系统的操作并收集统计数据。例如，我们想模拟有K个出纳员的银行操作系统，以确定要提供合理的服务时间，最小的K值是多少。用计算机来模拟有很多优点：首先，不需要真实的顾客就能够得到统计信息；第二，由于计算机速度很快，使用计算机模拟比真实的实现要快很多；第三，模拟结果可以简单地重现。54离散事件模拟系统一个排队系统主要由一些事件组合而成。在银行的排队系统中主要有两类事件：顾客的到达和服务完毕后顾客的离去。整个系统就是不断地有到达事件和离开事件发生，这些事件并不是连续发生的，因此这样的系统被称为离散事件模拟系统一个离散事件模拟器由事件处理组成；一般有两类事件：客户到达服务完毕，客户离开我们可以在模拟过程中统计客户的排队长度、等待时间、服务员的连续工作时间、空闲时间等统计信息。55排队系统的实现实现一个排队系统就是模拟这两类事件的生成和处理。事件处理过程当遇到一个到达事件时，表示有一个新顾客到达。如果服务员没空，顾客到队列去排队。否则为这个顾客生成服务所需的时间t。经过了t时间以后会产生一个顾客离开事件。当遇到一个离开事件时，就检查有没有顾客在排队。如果有顾客在排队，则让队头顾客离队，为他提供服务。如果没顾客排队，则服务员可以休息56如何产生顾客到达事件和服务时间顾客的到达时间间隔和为每个顾客的服务时间并不一定是固定的。尽管服务时间和顾客到达的间隔时间是可变的，但从统计上来看是服从一定的概率分布。要生成顾客的到达时间或生成服务时间必须掌握如何按照某个概率生成事件。57均匀分布的概率事件用随机数产生器产生的随机数如顾客到达的间隔时间服从[a，b]之间的均匀分布，则可以生成一个[a，b]之间的一个随机数x，表示前一个顾客到达后，经过了x的时间后又有一个顾客到达了。58[a，b]之间的随机数的产生假如系统的随机数生成器生成的随机数是均匀分布在0到RAND_MAX之间，包括0和RAND_MAX；把数轴上0到RAND_MAX之间的区间等分成b-a+1份；当生成的随机数落在第一个区间中，则表示生成的是a；当落在第二个区间中时，表示生成的是a+1;……，当落在最后一个区间时，表示生成的是b。这个转换可以用一个简单的算术表达式rand()*(b–a+1)/(RAND_MAX+1)+a实现。59虚拟时间模拟系统是一个虚拟的系统。当我们得到了在x秒后有一个事件生成的信息时，并不真正需要让系统等待x秒，然后处理该事件。在模拟系统中，一般不需要使用真实的精确时间，只要用一个时间单位即可，我们把这个时间单位叫做一个嘀嗒。一个嘀嗒可以表示1秒，也可以表示1分钟，也可以表示一小时，这根据应用来决定。60离散的时间驱动模拟沿着时间轴，模拟每一个嘀嗒中发生了什么事件并处理该事件。模拟开始时时钟是0嘀嗒，随后每一步都把时钟加1嘀嗒，并检查这个时间是否有事件发生；如果有事件发生，我们就处理该事件并生成统计信息；当到达规定时间时，模拟结束。61缺陷离散的时间驱动模拟连续地处理每个时间单位；这种模拟对于时间间隔很大的事件很不适合。如果在很长的一段时间中没有任何事情发生，程序还必须检查每个嘀嗒中是否有事件发生。这将浪费计算机的时间。运行时间不依赖于顾客数或者事件数，而是取决于嘀嗒数。在一个银行系统中，顾客到达的时间间隔和服务时间以分钟作为单位是比较合适的，因此在模拟时可以用1嘀嗒表示1分钟。但如果程序员选择的时间单位不合适，用1嘀嗒表示1秒钟，那么程序运行的时间将增加60倍。62事件驱动模拟将事件按照发生时间排队，当一个事件处理结束后，直接将时间拨到下一事件的发生时间，处理下一事件。63银行排队系统的模拟系统设计一个最简单的排队系统模拟器，即只有一个服务台的排队系统，希望通过这个模拟器得到顾客的平均排队时间。银行中只有一个服务台，顾客到达的时间间隔服从[arrivaLow,arrivalHigh]的均匀分布，服务时间长度服从[serviceTimeLow,serviceTimeHigh]间的均匀分布，一共模拟customNum个顾客。要求统计顾客的平均排队时间。64单服务台的排队系统的实现只要使用一个队列整个模拟由三个步骤组成：首先生成所有的顾客到达事件，按到达时间排成一个队列；服务员一旦有空，就为队头元素服务，在提供服务前先检查该顾客等待了多少时间，记入累计值；最后，在所有顾客都服务完以后，返回累计值除以顾客数的结果。65totalWaitTime=0;设置顾客开始到达的时间currentTime=0;for(i=0;i<customNum;++i){生成下一顾客到达的间隔时间；下一顾客的到达时间currentTime+=下一顾客到达的间隔时间；将下一顾客的到达时间入队；

}从时刻0开始模拟;while（顾客队列非空）

{取队头顾客；

If（到达时间>当前时间）直接将时钟拨到事件发生的时间；

Else收集该顾客的等待时间；生成服务时间；将时钟拨到服务完成的时刻；}返回等待时间/顾客数；66模拟类的定义设计一个实现单服务台排队系统的工具。数据成员：到达时间间隔的分布，服务时间的分布，以及想要模拟多少个顾客。功能：获得本次服务中顾客的平均等待时间是多少。这个类应该有两个公有函数：构造函数接受用户输入的参数，另外一个就是执行模拟并最终给出平均等待时间的函数avgWaitTime。67classsimulator{ intarrivalLow; intarrivalHigh; intserviceTimeLow; intserviceTimeHigh; intcustomNum;public: simulator(); intavgWaitTime()const;};68

构造函数simulator::simulator(){ cout<<"请输入到达时间间隔的上下界："; cin>>arrivalLow>>arrivalHigh; cout<<"请输入服务时间的上下界："; cin>>service