資源描述：
《《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第3章棧和隊(duì)列棧和隊(duì)列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它們都來(lái)自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作受限”的線性表。棧在計(jì)算機(jī)的實(shí)現(xiàn)有多種方式：◆硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內(nèi)存的特殊區(qū)域來(lái)實(shí)現(xiàn)。這類堆棧容量有限，但速度很快；◆軟堆棧：這類堆棧主要在內(nèi)存中實(shí)現(xiàn)。堆棧容量可以達(dá)到很大。在實(shí)現(xiàn)方式上，又有動(dòng)態(tài)方式和靜態(tài)方式兩種。本章將討論棧和隊(duì)列的基本概念、存儲(chǔ)結(jié)構(gòu)、基本操作以及這些操作的具體實(shí)現(xiàn)。3.1棧3.1.1棧的基本概念1棧的概念棧(Stack)：是限制在表的一端進(jìn)行插入和刪除操作的線性表。又稱為后進(jìn)先出LIFO(LastInFirstOut)或先進(jìn)后出FILO(F
2、irstInLastOut)線性表。棧頂(Top)：允許進(jìn)行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來(lái)指示棧頂元素。棧底(Bottom)：是固定端，又稱為表頭。空棧：當(dāng)表中沒(méi)有元素時(shí)稱為空棧。設(shè)棧S=(a1，a2，…an)，則a1稱為棧底元素，an為棧頂元素，如圖3-1所示。棧中元素按a1，a2，…an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。即棧的修改是按后進(jìn)先出的原則進(jìn)行的。圖3-1順序棧示意圖a1a2aian????bottomtop進(jìn)棧（push）出棧(pop)2棧的抽象數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對(duì)象：D={ai
3、ai∈ElemSet,i=1,2,…,
4、n，n≥0}數(shù)據(jù)關(guān)系：R={
5、ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、進(jìn)棧、出棧、取棧頂元素等}ADTStack棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，和線性表相類似，用一維數(shù)組來(lái)存儲(chǔ)棧。根據(jù)數(shù)組是否可以根據(jù)需要增大，又可分為靜態(tài)順序棧和動(dòng)態(tài)順序棧。◆靜態(tài)順序棧實(shí)現(xiàn)簡(jiǎn)單，但不能根據(jù)需要增大棧的存儲(chǔ)空間；◆動(dòng)態(tài)順序?？梢愿鶕?jù)需要增大棧的存儲(chǔ)空間，但實(shí)現(xiàn)稍為復(fù)雜。3.1.2棧的順序存儲(chǔ)表示采用動(dòng)態(tài)一維數(shù)組來(lái)存儲(chǔ)棧。所謂動(dòng)態(tài)，指的是棧的大小可以根據(jù)需要增加?！粲胋ottom表示棧底指針，棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化。用top(稱為棧頂指針)指示
6、當(dāng)前棧頂位置。◆用top=bottom作為?？盏臉?biāo)記，每次top指向棧頂數(shù)組中的下一個(gè)存儲(chǔ)位置?！艚Y(jié)點(diǎn)進(jìn)棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€(gè)存儲(chǔ)位置;3.1.2.1棧的動(dòng)態(tài)順序存儲(chǔ)表示◆結(jié)點(diǎn)出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲(chǔ)位置，然后將棧頂元素取出。圖3-2是一個(gè)動(dòng)態(tài)棧的變化示意圖。圖3-2(動(dòng)態(tài))堆棧變化示意圖空棧bottomtop元素a進(jìn)棧bottomtopa元素b，c進(jìn)棧bottomtopabc元素c退棧bottomtopabbottomtopabdef元素d，e，f進(jìn)?；静僮鞯膶?shí)現(xiàn)1棧的類型定
7、義#defineSTACK_SIZE100/*棧初始向量大小*/#defineSTACKINCREMENT10/*存儲(chǔ)空間分配增量*/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*棧不存在時(shí)值為NULL*/ElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配空間，以元素為單位*/}SqStack;2棧的初始化StatusInit_Stack(void){SqStackS;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));
8、if(!S.bottom)returnERROR;S.top=S.bottom;/*?？諘r(shí)棧頂和棧底指針相同*/S.stacksize=STACK_SIZE;returnOK;}3壓棧(元素進(jìn)棧)Statuspush(SqStackS,ElemTypee){if(S.top-S.bottom>=S.stacksize-1){S.bottom=(ElemType*)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));/*棧滿，追加存儲(chǔ)空間*/if(!S.bottom)returnERROR;S.top=S.bottom+S.
9、stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;/*棧頂指針加1，e成為新的棧頂*/returnOK;}4彈棧(元素出棧)Statuspop(SqStackS,ElemType*e)/*彈出棧頂元素*/{if(S.top==S.bottom)returnERROR;/*?？眨祷厥?biāo)志*/S.top--;e=*S.top;returnOK;}采用靜態(tài)一維數(shù)組來(lái)存儲(chǔ)棧。棧底固定不變的，而棧頂則隨著進(jìn)棧和退
