數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列

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

e0e1e2…en-2en-1

出棧順序：

en-1en-2…e2e1e0

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

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

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

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

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

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

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

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

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

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

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

TypePop();//出棧操作

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

voidMakeEmpty(){top=NULL;}//置?？詹僮?，應(yīng)先刪除棧內(nèi)所有結(jié)點(diǎn)

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

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

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

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

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

墻通道數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第11頁(yè)。2023/6/1412

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

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

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

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

then打印剛找到的一條簡(jiǎn)單路徑，并回溯一步；

elseif東面的是通道塊

then前進(jìn)一步

elseif南面的是通道塊

then前進(jìn)一步

elseif西面的是通道塊

then前進(jìn)一步

elseif北面的是通道塊

then前進(jìn)一步

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

TypeDeQueue();//出列操作

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

voidMakeEmpty();//置隊(duì)空操作

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

intIsFull()const;//判隊(duì)滿操作}數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第19頁(yè)。2023/6/1420隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)——循環(huán)隊(duì)列（環(huán)型隊(duì)列）

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

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

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

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

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

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

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

Queue012maxSize-1maxSize-2front隊(duì)首指針rear隊(duì)尾指針front==(rear+1)%maxSize本圖滿足上述隊(duì)滿條件。由圖可知：隊(duì)滿時(shí)隊(duì)首指針?biāo)傅膯卧荒芾?，此時(shí)再入列會(huì)使隊(duì)列變成空隊(duì)列(front==rear)隊(duì)尾元素elements[rear]

隊(duì)首元素@@@@@@@@@@@@數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第22頁(yè)。2023/6/1423循環(huán)隊(duì)列的類(lèi)定義：#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ù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第23頁(yè)。2023/6/1424循環(huán)隊(duì)列入列操作算法：template<classType>voidQueue<Type>::EnQueue(constType&item)//若隊(duì)列不滿，則將元素item插入到隊(duì)尾，否則出錯(cuò)處理{ assert(!IsFull());//斷言：隊(duì)列不滿則繼續(xù)，否則出錯(cuò)處理

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

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

returnelements[front];//返回出列的隊(duì)首元素}數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第24頁(yè)。2023/6/14254.3.3鏈隊(duì)列——利用鏈?zhǔn)酱尜A結(jié)構(gòu)實(shí)現(xiàn)的隊(duì)列

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

隊(duì)首隊(duì)尾rear隊(duì)尾指針數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第25頁(yè)。2023/6/1426鏈隊(duì)列的類(lèi)定義template<classType>classQueue;template<classType>classQueueNode{//鏈隊(duì)列結(jié)點(diǎn)的類(lèi)定義

friendclassQueue<Type>;//將鏈隊(duì)列類(lèi)作為鏈隊(duì)列結(jié)點(diǎn)類(lèi)的友元

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

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

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

~Queue();//析構(gòu)函數(shù)，釋放鏈隊(duì)列的所有結(jié)點(diǎn)，參見(jiàn)下頁(yè)定義

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

TypeDeQueue();//出列操作

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

voidMakeEmpty();//置空隊(duì)列，與析構(gòu)函數(shù)類(lèi)似，參見(jiàn)下頁(yè)定義

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

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

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

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

p=front;//(1) front=front->link;//(2)出列隊(duì)首結(jié)點(diǎn)

deletep;//釋放出列的結(jié)點(diǎn)

}}

front^…rearpfront(1)(2)數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第28頁(yè)。2023/6/1429置空隊(duì)列操作：Template<classType>voidQueue<Type>::MakeEmpty(){//置空隊(duì)列操作，釋放鏈隊(duì)列中所有的結(jié)點(diǎn)

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

p=front;front=front->link;//出列隊(duì)首結(jié)點(diǎn)

deletep;//釋放出列的結(jié)點(diǎn)

}}鏈隊(duì)列入列操作：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)原隊(duì)尾新隊(duì)尾item數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第29頁(yè)。2023/6/1430鏈隊(duì)列出列操作：template<classType>TypeQueue<Type>::DeQueue()//若隊(duì)列不空，則刪除隊(duì)首結(jié)點(diǎn)并返回該結(jié)點(diǎn)的值，否則出錯(cuò)處理{ assert(!IsEmpty());//若隊(duì)列不空，則繼續(xù)，否則出錯(cuò)處理

QueueNode<Type>*p=front;//保留隊(duì)首結(jié)點(diǎn)指針（1）

Typeretvalue=p->data;//讀取隊(duì)首結(jié)點(diǎn)的值

front=front->link;//隊(duì)首指針指向下一結(jié)點(diǎn)，即刪除隊(duì)首結(jié)點(diǎn)（2）

if(rear==p)rear=NULL;//若原隊(duì)列只有一個(gè)結(jié)點(diǎn)，

//則出列后為空隊(duì)列：front=rear=NULL deletep;//釋放原隊(duì)首結(jié)點(diǎn)

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

（5）銀行上班時(shí)間到后顧客才能進(jìn)門(mén)，下班時(shí)間到時(shí)顧客 不能進(jìn)門(mén)數(shù)據(jù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第31頁(yè)。2023/6/1432仿真模型：

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

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

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

進(jìn)門(mén)時(shí)間（隨機(jī)數(shù)）ArrivalTime——事件 進(jìn)門(mén)序號(hào)（顧客號(hào)）CustomerID——用于統(tǒng)計(jì)顧客總數(shù) 要求服務(wù)的時(shí)間（隨機(jī)數(shù)）ServiceTime

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

本窗口完成當(dāng)前窗口隊(duì)列服務(wù)的時(shí)刻finishService

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

本窗口的累計(jì)顧客等待時(shí)間totalCustomerWait

本窗口的最大顧客等待時(shí)間maxCustomerWait

本窗口的最大隊(duì)列長(zhǎng)度maxQlength

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

Queue<Event>CustomerFlow;//定義顧客流隊(duì)列

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

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

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

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

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

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

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

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

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

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

//若長(zhǎng)度都一樣，則選擇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ù)結(jié)構(gòu)PPT：棧和隊(duì)列全文共41頁(yè)，當(dāng)前為第37頁(yè)。2023/6/1438 //改變窗口j的工作表

e.WaitTime=tstat[j].finishService-e.ArrivalTime;//計(jì)算等待時(shí)間

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

時(shí)間圖1

e.W