《數(shù)據(jù)結構：思想與方法》第四章隊列

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

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

p指向結點的指針部分=NULL；

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

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

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

virtualvoidenQueue(constelemType&x)=0;//進隊

virtualelemTypedeQueue()=0;//出隊

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

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

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

}從時刻0開始模擬;while（顧客隊列非空）

{取隊頭顧客；

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

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

構造函數(shù)simulator::simulator(){ cout<<"請輸入到達時間間隔的上下界："; cin>>arrivalLow>>arrivalHigh; cout<<"請輸入服務時間的上下界："; cin>>service