《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第四章隊(duì)列

1第四章隊(duì)列隊(duì)列的概念隊(duì)列的實(shí)現(xiàn)隊(duì)列類的實(shí)現(xiàn)STL中的隊(duì)列隊(duì)列的應(yīng)用2隊(duì)列隊(duì)列是另外一種常用的線性結(jié)構(gòu)，到達(dá)越早的結(jié)點(diǎn)，離開的時(shí)間越早。所以隊(duì)列通常稱之為先進(jìn)先出(FIFO:FirstInFirstOut)隊(duì)列。如：我們?cè)阢y行儲(chǔ)蓄柜前排隊(duì)取款，計(jì)算機(jī)中打印管理器對(duì)打印隊(duì)列的處理都采用了這種先來先服務(wù)的方式。可以將隊(duì)列想象為一段管道，結(jié)點(diǎn)從一端流入，從另一端流出。流入端通常稱之為隊(duì)尾，而流出端稱之為隊(duì)首。3隊(duì)列的基本概念出隊(duì)入隊(duì)隊(duì)尾隊(duì)頭4隊(duì)列的基本操作創(chuàng)建一個(gè)隊(duì)列create()：創(chuàng)建一個(gè)空的隊(duì)列；入隊(duì)enQueue(x)：將x插入隊(duì)尾，使之成為隊(duì)尾元素；出隊(duì)deQueue()：刪除隊(duì)頭元素并返回隊(duì)頭元素值；讀隊(duì)頭元素getHead()：返回隊(duì)頭元素的值；判隊(duì)列空isEmpty()：若隊(duì)列為空，返回true，否則返回false。5隊(duì)列隊(duì)列的概念隊(duì)列的實(shí)現(xiàn)隊(duì)列類的實(shí)現(xiàn)STL中的隊(duì)列隊(duì)列的應(yīng)用6隊(duì)列的具體實(shí)現(xiàn)隊(duì)列的順序?qū)崿F(xiàn)隊(duì)列的鏈接實(shí)現(xiàn)7隊(duì)列的順序存儲(chǔ)使用數(shù)組存儲(chǔ)隊(duì)列中的元素隊(duì)列中的結(jié)點(diǎn)個(gè)數(shù)最多為MaxSize個(gè)元素下標(biāo)的范圍從0到MaxSize-1。順序隊(duì)列的三種組織方式隊(duì)頭位置固定隊(duì)頭位置不固定循環(huán)隊(duì)列8隊(duì)頭位置固定隊(duì)頭固定在下標(biāo)0用一個(gè)變量指出隊(duì)尾位置隊(duì)列為空時(shí)，隊(duì)尾位置為-19隊(duì)頭位置固定fedcba0Maxsize-1reara出隊(duì)fedcb0Maxsize-1rear缺點(diǎn)：出隊(duì)會(huì)引起大量的數(shù)據(jù)移動(dòng)10隊(duì)頭位置不固定使用隊(duì)首指針front和隊(duì)尾指針rear，分別指示隊(duì)首結(jié)點(diǎn)的前一位置和隊(duì)尾結(jié)點(diǎn)存放的下標(biāo)地址，用于刪除隊(duì)首結(jié)點(diǎn)和指示到何處去排隊(duì)隊(duì)列初始化時(shí)，設(shè)front=rear(都為-1)，即隊(duì)空的標(biāo)志：front=rear隊(duì)滿標(biāo)志：rear=MaxSize-111fedcba0Maxsize-1reara出隊(duì)frontfedcb0Maxsize-1rearfront特點(diǎn)：所有操作都是O（1）浪費(fèi)空間12循環(huán)隊(duì)列結(jié)點(diǎn)E進(jìn)隊(duì)后frontrearDCE從邏輯上認(rèn)為單元0就是單元MaxSizeDCfrontrear13MaxSize-101……frontrear入隊(duì)操作：rear=(rear

+1)%MaxSize；elem[rear]=x。出隊(duì)操作：front=(front+1)%MaxSize。14問題如何確定隊(duì)列為空和隊(duì)列滿？創(chuàng)建一個(gè)隊(duì)列時(shí)，可以將front和rear都設(shè)為0來表示空隊(duì)列。但經(jīng)過了多次的入隊(duì)和出隊(duì)后，front和rear都不在0的位置。15出隊(duì)后隊(duì)列變空即隊(duì)列中應(yīng)該只有一個(gè)元素。此時(shí)rear和front相鄰，rear在front后面。執(zhí)行front=(front+1)%MaxSize后，front和rear相同。因此隊(duì)列為空時(shí)，front=rearfrontrearMaxSize-1016入隊(duì)后隊(duì)列滿此時(shí)數(shù)組中只剩下一個(gè)空單元，就是front指向的單元。執(zhí)行入隊(duì)操作后，rear按順時(shí)針向后移一個(gè)單元，與front重疊。frontrear17解決方案“犧牲”一個(gè)單元，規(guī)定front指向的單元不能存儲(chǔ)隊(duì)列元素，只起到標(biāo)志作用，表示后面一個(gè)是隊(duì)頭元素。當(dāng)rear“繞一卷”趕上front時(shí)，隊(duì)列就滿了。因此隊(duì)列滿的條件是：(rear+1)%MaxSize==front隊(duì)列為空的條件是front==rear，即隊(duì)頭追上了隊(duì)尾。18隊(duì)列基本運(yùn)算的實(shí)現(xiàn)create()：申請(qǐng)一塊空間，首地址存入elem。數(shù)組規(guī)模保存在MaxSize中，front和rear置成0。enQueue(x)：首先要判斷數(shù)組是否已放滿，這可以通過判別(rear+1)%MaxSize是否等于front來實(shí)現(xiàn)。如果數(shù)組已滿。與順序表的處理相同，可以有兩種方案：終止入隊(duì)操作或擴(kuò)展數(shù)組空間。如果不等，表示元素可以入隊(duì)。先通過語句rear=(rear+1)%MaxSize將rear往后移一個(gè)位置，然后執(zhí)行elem[rear]=x。deQueue()：將front往后移一個(gè)位置，即執(zhí)行front=(front+1)%MaxSize。然后返回elem[front]的內(nèi)容。getHead()：返回elem[(front+1)%MaxSize]的內(nèi)容isEmpty()：判斷front是否等于rear。若相等，返回true，否則返回false。19隊(duì)列的具體實(shí)現(xiàn)隊(duì)列的順序?qū)崿F(xiàn)隊(duì)列的鏈接實(shí)現(xiàn)20隊(duì)列的鏈接實(shí)現(xiàn)由于隊(duì)列的操作是在隊(duì)列的兩端進(jìn)行的，不會(huì)對(duì)隊(duì)列中的其他元素進(jìn)行操作，用單鏈表就足夠了。隊(duì)列要對(duì)表的兩端作操作，為方便兩端操作，我們可以采用空間換時(shí)間的方法，同時(shí)記住頭尾結(jié)點(diǎn)的位置。哪一端作為隊(duì)頭，哪一端作為隊(duì)尾呢？隊(duì)尾指出的是插入位置，對(duì)單鏈表來說，有了尾指針，在表頭插入和表尾插入一樣簡(jiǎn)單。但對(duì)于刪除來說，刪除表頭元素很簡(jiǎn)單，但刪除表尾元素必須知道它前一元素的存儲(chǔ)地址，因此在表尾刪除要花O（N）的時(shí)間。為此可以將單鏈表的表頭作為隊(duì)頭，單鏈表的表尾作為隊(duì)尾21隊(duì)列的鏈接實(shí)現(xiàn)用無頭結(jié)點(diǎn)的單鏈表表示隊(duì)列，表頭為隊(duì)頭，表尾為隊(duì)尾frontrear22鏈接隊(duì)列的特點(diǎn)鏈接隊(duì)列不會(huì)出現(xiàn)隊(duì)列滿的情況，但隊(duì)列為空的情況依然存在。隊(duì)列為空時(shí)，單鏈表中沒有結(jié)點(diǎn)存在，即頭尾指針都為空指針。保存一個(gè)鏈接隊(duì)列只需要兩個(gè)指向單鏈表結(jié)點(diǎn)的指針front和rear，分別指向頭尾結(jié)點(diǎn)。采用鏈接存儲(chǔ)時(shí)，隊(duì)列的基本運(yùn)算的實(shí)現(xiàn)也非常簡(jiǎn)單，都是O（1）的時(shí)間復(fù)雜度。23隊(duì)列操作的實(shí)例初始時(shí)：front=NULL;rear=NULL;A進(jìn)隊(duì)：frontrearAB進(jìn)隊(duì)：frontrearAB24C進(jìn)隊(duì)：frontrearABC出隊(duì)：frontrearBC出隊(duì)：frontrearC出隊(duì)：front=NULL;rear=NULL;D進(jìn)隊(duì)：frontrearD25create()將front和rear設(shè)為空指針。26enQueue(x)首先申請(qǐng)一個(gè)結(jié)點(diǎn)存儲(chǔ)x；將結(jié)點(diǎn)x作為單鏈表的表尾，即rear指向的結(jié)點(diǎn)的指針部分指向結(jié)點(diǎn)x，將結(jié)點(diǎn)x作為尾結(jié)點(diǎn)。注意，enQueue操作有個(gè)特殊情況，就是隊(duì)列為空的情況。此時(shí)，我們只需要申請(qǐng)一個(gè)存放x的結(jié)點(diǎn)，讓front和rear同時(shí)指向這個(gè)結(jié)點(diǎn)。27voidenQueue(x){p=new結(jié)點(diǎn)；

p指向結(jié)點(diǎn)的數(shù)據(jù)部分=x；

p指向結(jié)點(diǎn)的指針部分=NULL；

if(rear==NULL)front=rear=p;else{rear指向的結(jié)點(diǎn)的指針部分=p；

rear=p;}}28deQueue()返回front指向的結(jié)點(diǎn)的值并刪除該結(jié)點(diǎn)。刪除表頭結(jié)點(diǎn)需要先將表頭結(jié)點(diǎn)從鏈表中摘下，然后釋放表頭結(jié)點(diǎn)的空間。注意，deQueue操作有一個(gè)特殊情況，即如果執(zhí)行deQueue操作時(shí)隊(duì)列中只有一個(gè)元素，經(jīng)過deQueue操作，隊(duì)列為空，此時(shí)必須將front和rear同時(shí)置成NULL。29dataTypedeQueue(){p=front;x=p指向結(jié)點(diǎn)的數(shù)據(jù)部分；front=front指向的結(jié)點(diǎn)的指針部分；deletep；if(front==NULL)rear=NULL;

返回x的值;}30getHead()和isEmpty()getHead()：返回front指向的結(jié)點(diǎn)的值。isEmpty()：檢查front或rear的值即可。若值為空指針，返回true，否則返回false。31隊(duì)列隊(duì)列的概念隊(duì)列的實(shí)現(xiàn)隊(duì)列類的實(shí)現(xiàn)STL中的隊(duì)列隊(duì)列的應(yīng)用32隊(duì)列類的抽象類template<classelemType>classqueue{public:virtualboolisEmpty()=0;//判隊(duì)空

virtualvoidenQueue(constelemType&x)=0;//進(jìn)隊(duì)

virtualelemTypedeQueue()=0;//出隊(duì)

virtualelemTypegetHead()=0;//讀隊(duì)頭元素

virtual~queue(){}//虛析構(gòu)函數(shù)

};33循環(huán)隊(duì)列類的設(shè)計(jì)循環(huán)隊(duì)列類由隊(duì)列的抽象類派生循環(huán)隊(duì)列存儲(chǔ)：elem為存儲(chǔ)隊(duì)列元素的數(shù)組名，maxSize為數(shù)組的規(guī)模，front和rear為隊(duì)頭和隊(duì)尾標(biāo)記。公有成員函數(shù)：構(gòu)造和析構(gòu)，以及抽象類的所有函數(shù)私有的成員函數(shù)doubleSpace34循環(huán)隊(duì)列類的定義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鏈接隊(duì)列類的設(shè)計(jì)數(shù)據(jù)成員：頭尾指針頭尾指針的類型：指向結(jié)點(diǎn)（數(shù)據(jù)，下一結(jié)點(diǎn)地址）成員函數(shù)：構(gòu)造和析構(gòu)函數(shù)抽象類規(guī)定的功能40鏈接隊(duì)列類的定義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析構(gòu)函數(shù)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隊(duì)列類的應(yīng)用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順序?qū)崿F(xiàn)和鏈接實(shí)現(xiàn)的比較時(shí)間：兩者都能在常量的時(shí)間內(nèi)完成基本操作，但順序隊(duì)列由于采用回繞，使入隊(duì)和出隊(duì)的處理比較麻煩空間：鏈接隊(duì)列中，每個(gè)結(jié)點(diǎn)多一個(gè)指針字段，但在順序隊(duì)列中有大量的尚未使用的空間。48隊(duì)列隊(duì)列的概念隊(duì)列的實(shí)現(xiàn)隊(duì)列類的實(shí)現(xiàn)STL中的隊(duì)列隊(duì)列的應(yīng)用49STL中的隊(duì)列STL中的隊(duì)列類是一個(gè)容器適配器，隊(duì)列可以借助的容器有vector,list和deque。定義一個(gè)隊(duì)列對(duì)象要指明隊(duì)列中元素的類型以及借助于哪一個(gè)容器，因此隊(duì)列的類模板有兩個(gè)模板參數(shù)：隊(duì)列元素類型和所借助的容器類型。隊(duì)列的類模板的第二個(gè)參數(shù)帶有缺省值deque50STL中的隊(duì)列STL中的隊(duì)列提供六個(gè)運(yùn)算：入隊(duì)操作push：調(diào)用push_back出隊(duì)操作pop：調(diào)用pop_front獲得隊(duì)頭元素的操作front：調(diào)用front函數(shù)獲得隊(duì)尾元素的函數(shù)back：調(diào)用back函數(shù)判隊(duì)列為空的函數(shù)empty：調(diào)用empty函數(shù)獲得隊(duì)列長度的函數(shù)size：調(diào)用size函數(shù)51STL隊(duì)列的使用#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隊(duì)列隊(duì)列的概念隊(duì)列的實(shí)現(xiàn)隊(duì)列類的實(shí)現(xiàn)STL中的隊(duì)列隊(duì)列的應(yīng)用53排隊(duì)系統(tǒng)的模擬模擬（simulation）是計(jì)算機(jī)的一個(gè)重要應(yīng)用，是指用計(jì)算機(jī)來仿真現(xiàn)實(shí)系統(tǒng)的操作并收集統(tǒng)計(jì)數(shù)據(jù)。例如，我們想模擬有K個(gè)出納員的銀行操作系統(tǒng)，以確定要提供合理的服務(wù)時(shí)間，最小的K值是多少。用計(jì)算機(jī)來模擬有很多優(yōu)點(diǎn)：首先，不需要真實(shí)的顧客就能夠得到統(tǒng)計(jì)信息；第二，由于計(jì)算機(jī)速度很快，使用計(jì)算機(jī)模擬比真實(shí)的實(shí)現(xiàn)要快很多；第三，模擬結(jié)果可以簡(jiǎn)單地重現(xiàn)。54離散事件模擬系統(tǒng)一個(gè)排隊(duì)系統(tǒng)主要由一些事件組合而成。在銀行的排隊(duì)系統(tǒng)中主要有兩類事件：顧客的到達(dá)和服務(wù)完畢后顧客的離去。整個(gè)系統(tǒng)就是不斷地有到達(dá)事件和離開事件發(fā)生，這些事件并不是連續(xù)發(fā)生的，因此這樣的系統(tǒng)被稱為離散事件模擬系統(tǒng)一個(gè)離散事件模擬器由事件處理組成；一般有兩類事件：客戶到達(dá)服務(wù)完畢，客戶離開我們可以在模擬過程中統(tǒng)計(jì)客戶的排隊(duì)長度、等待時(shí)間、服務(wù)員的連續(xù)工作時(shí)間、空閑時(shí)間等統(tǒng)計(jì)信息。55排隊(duì)系統(tǒng)的實(shí)現(xiàn)實(shí)現(xiàn)一個(gè)排隊(duì)系統(tǒng)就是模擬這兩類事件的生成和處理。事件處理過程當(dāng)遇到一個(gè)到達(dá)事件時(shí)，表示有一個(gè)新顧客到達(dá)。如果服務(wù)員沒空，顧客到隊(duì)列去排隊(duì)。否則為這個(gè)顧客生成服務(wù)所需的時(shí)間t。經(jīng)過了t時(shí)間以后會(huì)產(chǎn)生一個(gè)顧客離開事件。當(dāng)遇到一個(gè)離開事件時(shí)，就檢查有沒有顧客在排隊(duì)。如果有顧客在排隊(duì)，則讓隊(duì)頭顧客離隊(duì)，為他提供服務(wù)。如果沒顧客排隊(duì)，則服務(wù)員可以休息56如何產(chǎn)生顧客到達(dá)事件和服務(wù)時(shí)間顧客的到達(dá)時(shí)間間隔和為每個(gè)顧客的服務(wù)時(shí)間并不一定是固定的。盡管服務(wù)時(shí)間和顧客到達(dá)的間隔時(shí)間是可變的，但從統(tǒng)計(jì)上來看是服從一定的概率分布。要生成顧客的到達(dá)時(shí)間或生成服務(wù)時(shí)間必須掌握如何按照某個(gè)概率生成事件。57均勻分布的概率事件用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)如顧客到達(dá)的間隔時(shí)間服從[a，b]之間的均勻分布，則可以生成一個(gè)[a，b]之間的一個(gè)隨機(jī)數(shù)x，表示前一個(gè)顧客到達(dá)后，經(jīng)過了x的時(shí)間后又有一個(gè)顧客到達(dá)了。58[a，b]之間的隨機(jī)數(shù)的產(chǎn)生假如系統(tǒng)的隨機(jī)數(shù)生成器生成的隨機(jī)數(shù)是均勻分布在0到RAND_MAX之間，包括0和RAND_MAX；把數(shù)軸上0到RAND_MAX之間的區(qū)間等分成b-a+1份；當(dāng)生成的隨機(jī)數(shù)落在第一個(gè)區(qū)間中，則表示生成的是a；當(dāng)落在第二個(gè)區(qū)間中時(shí)，表示生成的是a+1;……，當(dāng)落在最后一個(gè)區(qū)間時(shí)，表示生成的是b。這個(gè)轉(zhuǎn)換可以用一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式rand()*(b–a+1)/(RAND_MAX+1)+a實(shí)現(xiàn)。59虛擬時(shí)間模擬系統(tǒng)是一個(gè)虛擬的系統(tǒng)。當(dāng)我們得到了在x秒后有一個(gè)事件生成的信息時(shí)，并不真正需要讓系統(tǒng)等待x秒，然后處理該事件。在模擬系統(tǒng)中，一般不需要使用真實(shí)的精確時(shí)間，只要用一個(gè)時(shí)間單位即可，我們把這個(gè)時(shí)間單位叫做一個(gè)嘀嗒。一個(gè)嘀嗒可以表示1秒，也可以表示1分鐘，也可以表示一小時(shí)，這根據(jù)應(yīng)用來決定。60離散的時(shí)間驅(qū)動(dòng)模擬沿著時(shí)間軸，模擬每一個(gè)嘀嗒中發(fā)生了什么事件并處理該事件。模擬開始時(shí)時(shí)鐘是0嘀嗒，隨后每一步都把時(shí)鐘加1嘀嗒，并檢查這個(gè)時(shí)間是否有事件發(fā)生；如果有事件發(fā)生，我們就處理該事件并生成統(tǒng)計(jì)信息；當(dāng)?shù)竭_(dá)規(guī)定時(shí)間時(shí)，模擬結(jié)束。61缺陷離散的時(shí)間驅(qū)動(dòng)模擬連續(xù)地處理每個(gè)時(shí)間單位；這種模擬對(duì)于時(shí)間間隔很大的事件很不適合。如果在很長的一段時(shí)間中沒有任何事情發(fā)生，程序還必須檢查每個(gè)嘀嗒中是否有事件發(fā)生。這將浪費(fèi)計(jì)算機(jī)的時(shí)間。運(yùn)行時(shí)間不依賴于顧客數(shù)或者事件數(shù)，而是取決于嘀嗒數(shù)。在一個(gè)銀行系統(tǒng)中，顧客到達(dá)的時(shí)間間隔和服務(wù)時(shí)間以分鐘作為單位是比較合適的，因此在模擬時(shí)可以用1嘀嗒表示1分鐘。但如果程序員選擇的時(shí)間單位不合適，用1嘀嗒表示1秒鐘，那么程序運(yùn)行的時(shí)間將增加60倍。62事件驅(qū)動(dòng)模擬將事件按照發(fā)生時(shí)間排隊(duì)，當(dāng)一個(gè)事件處理結(jié)束后，直接將時(shí)間撥到下一事件的發(fā)生時(shí)間，處理下一事件。63銀行排隊(duì)系統(tǒng)的模擬系統(tǒng)設(shè)計(jì)一個(gè)最簡(jiǎn)單的排隊(duì)系統(tǒng)模擬器，即只有一個(gè)服務(wù)臺(tái)的排隊(duì)系統(tǒng)，希望通過這個(gè)模擬器得到顧客的平均排隊(duì)時(shí)間。銀行中只有一個(gè)服務(wù)臺(tái)，顧客到達(dá)的時(shí)間間隔服從[arrivaLow,arrivalHigh]的均勻分布，服務(wù)時(shí)間長度服從[serviceTimeLow,serviceTimeHigh]間的均勻分布，一共模擬customNum個(gè)顧客。要求統(tǒng)計(jì)顧客的平均排隊(duì)時(shí)間。64單服務(wù)臺(tái)的排隊(duì)系統(tǒng)的實(shí)現(xiàn)只要使用一個(gè)隊(duì)列整個(gè)模擬由三個(gè)步驟組成：首先生成所有的顧客到達(dá)事件，按到達(dá)時(shí)間排成一個(gè)隊(duì)列；服務(wù)員一旦有空，就為隊(duì)頭元素服務(wù)，在提供服務(wù)前先檢查該顧客等待了多少時(shí)間，記入累計(jì)值；最后，在所有顧客都服務(wù)完以后，返回累計(jì)值除以顧客數(shù)的結(jié)果。65totalWaitTime=0;設(shè)置顧客開始到達(dá)的時(shí)間currentTime=0;for(i=0;i<customNum;++i){生成下一顧客到達(dá)的間隔時(shí)間；下一顧客的到達(dá)時(shí)間currentTime+=下一顧客到達(dá)的間隔時(shí)間；將下一顧客的到達(dá)時(shí)間入隊(duì)；

}從時(shí)刻0開始模擬;while（顧客隊(duì)列非空）

{取隊(duì)頭顧客；

If（到達(dá)時(shí)間>當(dāng)前時(shí)間）直接將時(shí)鐘撥到事件發(fā)生的時(shí)間；

Else收集該顧客的等待時(shí)間；生成服務(wù)時(shí)間；將時(shí)鐘撥到服務(wù)完成的時(shí)刻；}返回等待時(shí)間/顧客數(shù)；66模擬類的定義設(shè)計(jì)一個(gè)實(shí)現(xiàn)單服務(wù)臺(tái)排隊(duì)系統(tǒng)的工具。數(shù)據(jù)成員：到達(dá)時(shí)間間隔的分布，服務(wù)時(shí)間的分布，以及想要模擬多少個(gè)顧客。功能：獲得本次服務(wù)中顧客的平均等待時(shí)間是多少。這個(gè)類應(yīng)該有兩個(gè)公有函數(shù)：構(gòu)造函數(shù)接受用戶輸入的參數(shù)，另外一個(gè)就是執(zhí)行模擬并最終給出平均等待時(shí)間的函數(shù)avgWaitTime。67classsimulator{ intarrivalLow; intarrivalHigh; intserviceTimeLow; intserviceTimeHigh; intcustomNum;public: simulator(); intavgWaitTime()const;};68

構(gòu)造函數(shù)simulator::simulator(){ cout<<"請(qǐng)輸入到達(dá)時(shí)間間隔的上下界："; cin>>arrivalLow>>arrivalHigh; cout<<"請(qǐng)輸入服務(wù)時(shí)間的上下界："; cin>>service