數(shù)據(jù)結構PPT：棧和隊列

2023/6/141棧和隊列棧和隊列都是操作受限的線性表，應用十分廣泛。4.1棧（Stack）定義：棧是限制插入和刪除操作只能在某一端進行的線性表，并按先進后出（FILO)或后進先出（ＬIＦＯ）的原則進行操作入棧順序：

e0e1e2…en-2en-1

出棧順序：

en-1en-2…e2e1e0

?？梢詫π蛄袑崿F(xiàn)求逆en-1e0e1en-2…進棧（Push）出棧（Pop）棧頂top棧底數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第1頁。2023/6/142棧的基本操作：（參見P104）（1）棧初始化 Stack(int=10);//構造函數(shù)（2）進棧Push voidPush(constType&item);（3）出棧Pop TypePop();（4）判?？誌sEmpty intIsEmpty(){returntop==-1;}（5）讀取棧頂元素GetTop TypeGetTop();（6）置空棧MakeEmpty voidMakeEmpty(){top=-1;}（7）判棧滿IsFull intIsFull()const{returntop==maxSize;}棧的封閉性及其抽象數(shù)據(jù)類型：在一個棧中，出入口處稱為棧頂，棧內最深處稱為棧底。除了棧頂元素外，其他元素不會被改變，因而棧的封閉性非常好，使用起來非常安全。另外，在下面的棧的類定義中，體現(xiàn)了棧的抽象數(shù)據(jù)類型，在此定義中，所有棧的成員函數(shù)都是共有的，其他類的成員函數(shù)都可以使用這些函數(shù)，但是，棧的存儲表示和成員函數(shù)的實現(xiàn)對其他類的成員來說都是隱蔽的。數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第2頁。2023/6/1434.1.1順序棧－－在順序存儲結構上實現(xiàn)的棧#include<assert.h>//C＋＋斷言功能template<classType>classStack//順序棧的類定義{ public: Stack(int=10);//棧初始化，建立一個空棧，缺省大小為10 ~Stack(){delete[]elements;} voidPush(constType&item);//將數(shù)據(jù)元素item入棧

TypePop(); //將棧頂元素出棧

TypeGetTop(); //讀取棧頂元素

voidMakeEmpty(){top=-1;}//置空棧，top=-1表示棧為空

intIsEmpty()const{returntop==-1;}//判?？?/p>

intIsFull()const{returntop==maxSize-1;}//判棧滿

private://top=maxSize-1表示棧已滿

inttop;//棧頂指針（棧頂元素下標）

Type*elements;//存儲順序棧的數(shù)組

intmaxSize;//順序棧的最大容量}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第3頁。2023/6/144順序棧的基本操作（算法）（1）順序棧初始化算法（構造函數(shù)）template<classType>Stack<Type>::Stack(ints):top(-1),maxSize(s)//建立一個最大尺寸為s的空棧，若分配不成功則錯誤處理{ element=newType[maxSize];//創(chuàng)建順序?？臻g（數(shù)組）

assert(elements!=0);//斷言語句：若條件成立，則繼續(xù)；否則出錯處理并終止執(zhí)行}（2）順序棧入棧算法template<classType>voidStack<Type>::Push(constType&item)//若棧不滿，則將元素item插入到棧頂，否則出錯處理{ assert(!IsFull());//斷言：棧不滿則繼續(xù)執(zhí)行

elements[++top]=item;//棧頂指針先加1，然后按此地址進棧}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第4頁。2023/6/145（3）順序棧出棧算法template<classType>TypeStack<Type>::Pop()//若棧不空，則返回棧頂元素，并使棧頂指針退1；否則出錯處理

{ assert(!IsEmpty());//斷言：若棧不空，則繼續(xù)執(zhí)行

returnelements[top--];//返回棧頂元素，并使棧頂指針退1}（4）讀取順序棧棧頂元素算法Template<classType>TypeStack<Type>::GetTop()//若棧不空，則返回棧頂元素；否則出錯處理{ assert(!IsEmpty());//斷言：若棧不空，則繼續(xù)執(zhí)行

returnelements[top];//返回棧頂元素，注意：棧頂指針不變} 數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第5頁。2023/6/1464.1.3鏈?！面準酱尜A結構實現(xiàn)的棧

與順序表一樣，順序棧的最大尺寸（maxSize）也難以確定，太小了容易溢出，太大了又浪費空間。因此在動態(tài)性較強的應用領域，宜采用鏈棧。 鏈棧的結構如下圖所示。與單鏈表相似，但不設頭結點，第一個結點即為棧頂。插入（入棧）與刪除（出棧）操作均只能在表頭進行。當top=NULL時，表示空?！璣top棧頂元素棧底元素數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第6頁。2023/6/147鏈棧的定義：鏈棧結點類的定義：template<classType>classStack;//鏈棧類的前視聲明template<classType>classStackNode{ friendclassStack<Type>; private: Typedata; StackNode<Type>*link; StackNode(Typed=0,StackNode<Type>*l=NULL): data(d),link(l){}//構造函數(shù)，初始化一鏈棧結點}datalink鏈棧結點結構數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第7頁。2023/6/148鏈棧類的定義：template<classType>classStack{ public: Stack():top(NULL){}//構造函數(shù)，初始化一個空鏈棧

~Stack();//析構函數(shù)，釋放鏈棧的所有結點，并使top=NULL。置棧空操作

voidPush(constType&item);//入棧操作

TypePop();//出棧操作

TypeGetTop();//讀取棧頂元素

voidMakeEmpty(){top=NULL;}//置?？詹僮?，應先刪除棧內所有結點

intIsEmpty()const{returntop==NULL;}//判?？詹僮?/p>

intIsFull()const{return0}//判棧滿，在鏈棧中該操作無意義

private: StackNode<Type>*top;//棧頂指針}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第8頁。2023/6/149鏈棧的入棧算法：Template<classType>voidStack<Type>::Push(constType&item)//將數(shù)據(jù)元素item入棧{ top=newStackNode<Type>(item,top);//創(chuàng)建一個新的鏈棧結點，并將該結點的data域置為item，

//link域置為top,最后將該結點的指針賦值給top.參見下圖}…^top原棧頂新棧頂item(1)(2)數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第9頁。2023/6/1410比較與思考：（1）比較順序棧與鏈棧的類定義 兩者的類名相同，均為Stack

兩者成員函數(shù)的名、參數(shù)、返回類型與規(guī)格說明均相同，但內部的實現(xiàn)有別假定某大型軟件系統(tǒng)原來使用順序棧，因經常上溢，欲改用鏈棧，請問哪些部分需要改動？數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第10頁。2023/6/1411棧應用舉例——迷宮問題迷宮問題：求迷宮中從入口點到出口點所有可能的簡單路徑迷宮模型：入口(i,j)出口

墻通道數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第11頁。2023/6/1412

所謂的簡單路徑是指：在求出的任何一條路徑上，不能重現(xiàn)某一通道塊，否則總有任意多條路徑迷宮問題是許多實際問題的抽象，求解這類問題時，沒有現(xiàn)成的數(shù)學公式可以套用，只能采用系統(tǒng)化的試探方法。下面規(guī)定： 通道用空格“”表示 墻壁用“#”表示 足跡用“0”表示 從入口點到當前立足點間，具有足跡標志的相連的通道塊構成的簡單路徑叫當前路徑將迷宮模型用二維字符型數(shù)組表示：

charmaze[n+1][n+1];

并假定入口為maze[0][0]，出口為maze[n][n]

考慮一般情況，設maze[i][j]為當前立足點，并納入當前路徑（即印上足跡標志“0”），則從當前立足點繼續(xù)試探的算法如下：數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第12頁。2023/6/1413ifmaze[i][j]是出口

then打印剛找到的一條簡單路徑，并回溯一步；

elseif東面的是通道塊

then前進一步

elseif南面的是通道塊

then前進一步

elseif西面的是通道塊

then前進一步

elseif北面的是通道塊

then前進一步

else回溯一步(i,j)東南西北數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第13頁。2023/6/1414前進一步：將下一通道塊印上“0”作為當前立足點（切換當前立足 點），并保存原立足點的信息以便回溯?；厮菀徊剑喝サ舢斍傲⒆泓c的足跡“0”;

把最近的原立足點重新切換為當前立足點； 試探尚未試探過的方向。上述的活動均需要在迷宮中移動，并且具有方向性，這種活動可以使用二維數(shù)組下標增量技術來實現(xiàn)：行下標增量di[k]列下標增量dj[k]方向及其序號k東0南1西2北3 intdi[4]={0,1,0,-1}; intdj[4]={1,0,-1,0};01100－1－10數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第14頁。2023/6/1415在上述的規(guī)定下：

k=0時，maze[i+di[k]][j+dj[k]]為立足點的東面下一塊；

k=1時，maze[i+di[k]][j+dj[k]]為立足點的南面下一塊；

k=2時，maze[i+di[k]][j+dj[k]]為立足點的西面下一塊；

k=3時，maze[i+di[k]][j+dj[k]]為立足點的北面下一塊；客體的表示方法設計：從上述的用試探法走迷宮的過程可知，其中 所管理的信息是立足點的信息?？梢杂萌M（i,j,k)來表 示立足點，其中(i,j)表示立足點的位置信息，k表示立足點 的下一個試探方向。可以將三元組定義成一個結構：

structitems{inti,j,k;};數(shù)據(jù)的組織方法設計：考察上述用試探法走迷宮的過程：前進一步時，需要保存原立足點的信息；回溯一步時，需要取出最近的原立足點的信息，并且遵循 后保存的先取出的原則，即“后進先出”的原則，因此可以用棧 來記錄立足點的信息。迷宮問題的算法框架：

數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第15頁。2023/6/14161 Stack<items>s(sz);//棧初始化：創(chuàng)建一個大小為sz的棧，其數(shù)據(jù)元素類型為items2 itemse;intk;3 e.i=0;e.j=0;e.k=0;s.Push(e);maze[e.i][e.j]=‘0’; //將入口作為立足點并入棧4 while(!s.IsEmpty())//若棧不空則繼續(xù)循環(huán)試探

//若空表示已找到所有簡單路徑，可以結束程序5 {e=s.Pop();//出棧，準備試探下一方向或實現(xiàn)回溯一步操作6 if(e.k==4)maze[e.i][e.j]=‘‘;//四個方向均試探完畢

//消足跡,當再執(zhí)行到5時回溯一步

elseif(e.i==n&&e.j==n)printmaze();//當前立足點為出口

//成功找到一條簡單路徑并輸出，當再執(zhí)行到5時回溯一步

else{k=e.k;e.k=e.k+1;s.Push(e);//記住立足點的下一試探方向

e.i=e.i+di[k];e.j=e.j+dj[k];e.k=0;//沿k方向前進一步

if(maze[e.i][e.j]==‘‘)//若為通道則切換為新立足點并入棧

{s.Push(e);maze[e.i][e.j]=‘0’;} } } 數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第16頁。2023/6/1417作業(yè)：

完善迷宮問題解決算法（迷宮數(shù)組的輸入inputmaze()算法、 簡單路徑的輸出printmaze()算法等） 編寫軟件并上機實習要求11月6日前完成數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第17頁。2023/6/14184.3隊列定義：隊列是限制插入操作只能在一端進行，而刪除操作只能在另 一端進行的線性表，并按先進向出（FIFO）的原則進行操作。 在一個隊列中，能進行刪除的一端稱為隊首（front），能進行 插入操作的一端稱為隊尾（rear）。出列入列隊首（front）隊尾（rear） 與棧類似，隊列的封閉性也非常好 棧能對輸入序列部分或全局起求逆作用 隊列對輸入序列起緩沖作用，隊列的應用非常廣泛e0e1…en-2en-1數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第18頁。2023/6/1419隊列的基本操作Template<classType>classQueue{ public: Queue(int=10);//構造函數(shù)，隊列初始化操作

voidEnQueue(constType&item);//入列操作

TypeDeQueue();//出列操作

TypeGetFront();//讀取隊首元素操作

voidMakeEmpty();//置隊空操作

intIsEmpty()const;//判隊空操作

intIsFull()const;//判隊滿操作}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第19頁。2023/6/1420隊列的順序存儲結構——循環(huán)隊列（環(huán)型隊列）

由于在隊列的入列和出列操作中，其對應的隊尾和隊首指 針（下標）都是進1操作（否則出列操作需要移動所有的數(shù)據(jù)元素），隨著入列和出列操作的進行，隊尾和隊首指針都在逐步增大，因此隊列若用普通的順序存儲結構來實現(xiàn)，則很容易上溢，基本不能使用，因此實際中一般使用循環(huán)隊列。 通過求余運算（%），可以實現(xiàn)下標的循環(huán)累進：

index=(index+1)%m 012…m-1

因此，對隊首和隊尾進行如下操作就可以實現(xiàn)循環(huán)隊列：

front=(front+1)%maxSize隊首指針循環(huán)進1 rear=(rear+1)%maxSize隊尾指針循環(huán)進1 maxSize表示數(shù)組的最大尺寸

front和rear的最大取值為maxSize-1數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第20頁。2023/6/1421循環(huán)隊列：逆時針運行示意圖

Queue012maxSize-1maxSize-2front隊首指針rear隊尾指針規(guī)定：隊空：front==rear隊滿：front==(rear+1)%maxSize隊尾元素：elements[rear]

隊首元素：elements[(front+1)%maxSize]@@@@數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第21頁。2023/6/1422循環(huán)隊列：滿隊列示意圖

Queue012maxSize-1maxSize-2front隊首指針rear隊尾指針front==(rear+1)%maxSize本圖滿足上述隊滿條件。由圖可知：隊滿時隊首指針所指的單元不能利用，此時再入列會使隊列變成空隊列(front==rear)隊尾元素elements[rear]

隊首元素@@@@@@@@@@@@數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第22頁。2023/6/1423循環(huán)隊列的類定義：#include<assert.h>template<classType>classQueue{ public: Queue(int=10); ~Queue(){delete[]elements;} voidEnQueue(constType&item); TypeDeQueue(); TypeGetFront(); voidMakeEmpty(){front=rear=0;} intIsEmpty()const{returnfront==rear;} intIsFull()const{returnfront==(rear+1)%maxSize;} intLength()const{return(rear-front+maxSize)%maxSize;} private: intrear,front,maxSize; Type*elements;}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第23頁。2023/6/1424循環(huán)隊列入列操作算法：template<classType>voidQueue<Type>::EnQueue(constType&item)//若隊列不滿，則將元素item插入到隊尾，否則出錯處理{ assert(!IsFull());//斷言：隊列不滿則繼續(xù)，否則出錯處理

rear=(rear+1)%maxSize;//隊尾指針循環(huán)加1 elements[rear]=item;//在隊尾插入item}循環(huán)隊列出列操作算法：template<classType>TypeQueue<Type>::DeQueue()//若隊列不空，則刪除并返回隊首元素，否則出錯處理{ assert(!IsEmpty());//斷言：隊列不空則繼續(xù)，否則出錯處理

front=(front+1)%maxSize;//隊首指針循環(huán)加1，隊首元素出列

returnelements[front];//返回出列的隊首元素}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第24頁。2023/6/14254.3.3鏈隊列——利用鏈式存貯結構實現(xiàn)的隊列

與順序表一樣，循環(huán)隊列的最大尺寸（maxSize）也難以確定，太小了容易溢出，太大了又浪費空間。因此在動態(tài)性較強的應用領域，宜采用鏈隊列。 鏈隊列的結構如下圖所示。與單鏈表相似，但不設頭結點，第一個結點即為隊首。最后一個結點為隊尾。插入（入列）操作只能在隊尾進行，刪除（出列）操作只能在隊首進行。當front=rear=NULL時，表示空隊列…^front隊首指針

隊首隊尾rear隊尾指針數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第25頁。2023/6/1426鏈隊列的類定義template<classType>classQueue;template<classType>classQueueNode{//鏈隊列結點的類定義

friendclassQueue<Type>;//將鏈隊列類作為鏈隊列結點類的友元

private: Typedata; QueueNode<Type>*link; QueueNode(Typed=0,QueueNode*l=NULL): data(d),link(l){}};template<classType>classQueue//鏈隊列的類定義{ public: //鏈隊列類的成員函數(shù)

private: QueueNode<Type>*front,*rear;//隊首與隊尾指針}; 數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第26頁。2023/6/1427鏈隊列類的成員函數(shù)： Queue(int=10):rear(NULL),front(NULL){}//構造函數(shù)，建立一個

//空鏈隊列，int型參數(shù)是為了與循環(huán)隊列一致而設，此處無意義

~Queue();//析構函數(shù)，釋放鏈隊列的所有結點，參見下頁定義

voidEnQueue(constType&item);//入列操作

TypeDeQueue();//出列操作

TypeGetFront();//讀取隊首元素

voidMakeEmpty();//置空隊列，與析構函數(shù)類似，參見下頁定義

intIsEmpty()const{returnfront==NULL;}//判隊空操作

intIsFull()const;//為了與循環(huán)隊列一致而設，對鏈隊列無意義

intLength()const;//為了與循環(huán)隊列一致而設，對鏈隊列意義不大比較循環(huán)隊列的類定義可知：鏈隊列的成員函數(shù)的名、返回類型和參數(shù)表與循環(huán)隊列的完全一樣，這樣安排的好處是，當一個大型軟件原來使用循環(huán)隊列時經常發(fā)生溢出，此時改用鏈隊列的話只需將原來循環(huán)隊列的類定義及其成員函數(shù)定義改為鏈隊列的類定義和成員函數(shù)定義即可，無需更改軟件的其他地方。數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第27頁。2023/6/1428鏈隊列成員函數(shù)定義：Template<classType>voidQueue<Type>::~Queue(){//析構函數(shù)，釋放鏈隊列中所有的結點

QueueNode<Type>*p; while(front!=NULL) {//隊列不空，繼續(xù)循環(huán)

p=front;//(1) front=front->link;//(2)出列隊首結點

deletep;//釋放出列的結點

}}

front^…rearpfront(1)(2)數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第28頁。2023/6/1429置空隊列操作：Template<classType>voidQueue<Type>::MakeEmpty(){//置空隊列操作，釋放鏈隊列中所有的結點

QueueNode<Type>*p; while(front!=NULL) {//隊列不空，繼續(xù)循環(huán)

p=front;front=front->link;//出列隊首結點

deletep;//釋放出列的結點

}}鏈隊列入列操作：Template<classType>voidQueue<Type>::EnQueue(constType&item){ QueueNode<Type>*p=newQueueNode<Type>(item,NULL); if(front==NULL) front=rear=p; else{rear->link=p;//(1) rear=p;//(2) }}

^…rearrearp(1)(2)原隊尾新隊尾item數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第29頁。2023/6/1430鏈隊列出列操作：template<classType>TypeQueue<Type>::DeQueue()//若隊列不空，則刪除隊首結點并返回該結點的值，否則出錯處理{ assert(!IsEmpty());//若隊列不空，則繼續(xù)，否則出錯處理

QueueNode<Type>*p=front;//保留隊首結點指針（1）

Typeretvalue=p->data;//讀取隊首結點的值

front=front->link;//隊首指針指向下一結點，即刪除隊首結點（2）

if(rear==p)rear=NULL;//若原隊列只有一個結點，

//則出列后為空隊列：front=rear=NULL deletep;//釋放原隊首結點

returnretvalue;//返回原隊首結點的值}原隊首新隊首…frontpfront(1)(2)數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第30頁。2023/6/14314.5事件驅動模擬（Event-DrivenSimulation）模擬目的： （1）計算銀行顧客的平均（最大）等待時間 （2）計算銀行出納員的工作繁忙程度 （3）計算銀行顧客隊列的最大長度出納員服務原則： （1）某一時刻只能接待一位顧客 （2）若本窗口還有顧客則應立刻服務顧客活動原則： （1）顧客達到時間為ArrivalTime（隨機數(shù)） （2）顧客需要服務的時間為ServiceTime（隨機數(shù)） （3）顧客選擇最短的隊列排隊 （4）顧客的等待時間（從進門到輪到服務）為WaitTime

（5）銀行上班時間到后顧客才能進門，下班時間到時顧客 不能進門數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第31頁。2023/6/1432仿真模型：

窗口隊列服務窗口顧客選擇排隊顧客流（隊列）…………數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第32頁。2023/6/1433事件分析：顧客進門事件觸發(fā)下列操作： （1）從顧客流隊列中出列進門事件 （2）從各窗口隊列中選擇一最短隊列 （3）計算顧客需要等待的時間 （4）將該顧客入列到所選的最短窗口隊列中

出納員對當前顧客服務完畢事件觸發(fā)下列操作： （1）累計本窗口的服務時間 （2）累計本窗口顧客的等待時間 （3）記錄本窗口顧客的最大等待時間 （4）記錄本窗口的最大隊列長度 （5）累計本窗口服務的顧客總數(shù) （6）將當前顧客出列

數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第33頁。2023/6/1434數(shù)據(jù)結構設計：（1）顧客信息的表示——可將其定義為一結構Event

進門時間（隨機數(shù)）ArrivalTime——事件 進門序號（顧客號）CustomerID——用于統(tǒng)計顧客總數(shù) 要求服務的時間（隨機數(shù)）ServiceTime

需要等待的時間（計算數(shù)）WaitTime（2）窗口信息的表示——將其定義為一結構TellerStatus

本窗口完成當前窗口隊列服務的時刻finishService

本窗口已經服務的顧客總數(shù)CustomerCount

本窗口的累計顧客等待時間totalCustomerWait

本窗口的最大顧客等待時間maxCustomerWait

本窗口的最大隊列長度maxQlength

本窗口的累計服務時間totalService（3）數(shù)據(jù)的組織方法——采用隊列 將未進門的顧客按將要進門的先后順序入列到顧客流隊列中 將已進門的顧客（進門事件）入列到最短窗口隊列中 數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第34頁。2023/6/1435仿真算法思路：（1）利用隨機數(shù)發(fā)生器預先計算一天中達到銀行的所有顧客，并將他們入列到顧客流隊列CustomerFlow中。該功能由下述的CreateCustomerFlow()函數(shù)實現(xiàn)：

Queue<Event>CustomerFlow;//定義顧客流隊列

voidCreateCustomerFlow()//創(chuàng)建顧客流隊列

{ Evente=GetAEvent();//獲取一事件（使用隨機數(shù)發(fā)生器）

CustomerFlow.EnQueue(e);//將事件入列到顧客流隊列中

}//上述的每一事件代表一個顧客（2）用一虛擬時鐘VirtualTimer來模擬前述進門事件和服務完畢事件的發(fā)生。此處的虛擬時鐘是一查詢循環(huán)，每循環(huán)一次代表走過一個時間單位，用查詢模擬隨機的中斷請求，從而實現(xiàn)用順序執(zhí)行模擬并發(fā)執(zhí)行過程。該功能由下頁的RunSimulation()函數(shù)實現(xiàn)。數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第35頁。2023/6/1436仿真運行函數(shù)設計：若規(guī)定上班時間為StartTime,下班時間為EndTime，則查詢循環(huán)結構如下：VoidRunSimulation()//{ for(intt=StartTime;t<EndTime;t++)//虛擬時鐘

{ Evente=CustomerFlow.GetFront();//讀取顧客流隊列的隊首

if(e.ArrivalTime==t)ArrivalEvent(); //發(fā)現(xiàn)一進門事件并作相應處理。

for(i=0;i<tellernum;i++)//查詢各窗口有無服務完畢事件

{ e=Windowq[i].GetFront(); inttime=e.ArrivalTime+e.waitTime+e.serviceTime; if(t>=time)ServicedEvent(i); //發(fā)現(xiàn)窗口i有一服務完畢事件并作相應處理

} }}數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第36頁。2023/6/1437進門事件處理函數(shù)Queue<Event>Windowq[tellernum];//共定義了tellernum個窗口隊列VoidArrivalEvent()//進門事件處理{ Evente=CustomerFlow.DeQueue(); //將進門事件從顧客流隊列中出列到事件變量e中

//下面程序段實現(xiàn)從所有窗口隊列中選擇一最短隊列

//若長度都一樣，則選擇Windowq[0] intj=0; intminLength=Windowq[0].Length(); for(inti=1;i<tellernum;i++) { intL=Windowq[i].Length(); if(L<minLength) { j=i; minLength=L; } } 數(shù)據(jù)結構PPT：棧和隊列全文共41頁，當前為第37頁。2023/6/1438 //改變窗口j的工作表

e.WaitTime=tstat[j].finishService-e.ArrivalTime;//計算等待時間

if(e.WaitTime<0){e.WaitTime=0;//窗口隊列j為空隊列 tstat[j].finishService=e.ArrivalTime+e.serviceTime;}//圖2 elsetstat[j].finishService+=e.serviceTime;//圖1 Windowq[j].EnQueue(e);//將進門事件入列到最短窗口隊列中}e.ArrivalTime原tstat[j].finishService新tstat[j].finishService

時間圖1

e.W