資源描述：
《數(shù)據(jù)結(jié)構(gòu) 第3章 棧和隊(duì)列》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱為限定性數(shù)據(jù)結(jié)構(gòu)。3.1棧（stack）一、棧的定義和特點(diǎn)定義：棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。假設(shè)棧S=(a1，a2，a3，…,an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說(shuō)，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（LIFO）。特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）。在函數(shù)嵌套調(diào)用中，一個(gè)函數(shù)的
2、執(zhí)行沒(méi)有結(jié)束，又開(kāi)始另一個(gè)函數(shù)的執(zhí)行，因此必須用棧來(lái)保存函數(shù)中中斷的地址，以便調(diào)用返回時(shí)能從斷點(diǎn)繼續(xù)往下執(zhí)行。例設(shè)有一個(gè)主程序，它調(diào)用函數(shù)a，函數(shù)a又調(diào)用函數(shù)b，函數(shù)b又調(diào)用函數(shù)c，其中r，s，t分別表示中斷地址，我們可以用一個(gè)棧來(lái)描述調(diào)用情況。主程序調(diào)用函數(shù)a，留下一個(gè)斷點(diǎn)地址r進(jìn)棧，然后主函數(shù)處于掛起狀態(tài)，進(jìn)入函數(shù)a中執(zhí)行，函數(shù)a中再調(diào)用函數(shù)b，留下一個(gè)斷點(diǎn)地址s進(jìn)棧，然后函數(shù)a處于掛起狀態(tài)，進(jìn)入函數(shù)b中執(zhí)行，函數(shù)b中調(diào)用函數(shù)c，留下一個(gè)斷點(diǎn)地址t進(jìn)棧，然后函數(shù)b處于掛起狀態(tài)，進(jìn)入函數(shù)c中執(zhí)行，函數(shù)c執(zhí)行完后，要返回?cái)帱c(diǎn)處繼續(xù)執(zhí)行，但返回到那一個(gè)斷點(diǎn)呢?根據(jù)棧頂元素來(lái)決定。
3、返回時(shí)，執(zhí)行退棧操作，先退出t，故返回t斷點(diǎn)繼續(xù)執(zhí)行，接著退棧退出s，故返回s斷點(diǎn)繼續(xù)執(zhí)行，接著退棧退出r，返回r斷點(diǎn)繼續(xù)執(zhí)行，最后棧為空，算法結(jié)束。ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)棧的示意圖二、棧的運(yùn)算1.初始化棧：INISTACK(S)將棧S置為一個(gè)空棧(不含任何元素)。2.進(jìn)棧：PUSH(S,X)將元素X插入到棧S中，也稱為“入?！?、“插入”、“壓入”。3.出棧：POP(S)刪除棧S中的棧頂元素，也稱為”退?！?、“刪除”、“彈出”。4.取棧頂元素：GETTOP(S)取棧S中棧頂元素。5.判棧空：EMPTY(S)判斷棧S是否為空，
4、若為空，返回值為1，否則返回值為0。三、棧的存儲(chǔ)結(jié)構(gòu)1、順序棧①實(shí)現(xiàn)：一維數(shù)組s[M]top=-1123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,棧空，此時(shí)出棧，則下溢（underflow)top=Maxsize-1,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？闸陧樞驐５拇鎯?chǔ)結(jié)構(gòu)描述#defineMaxsize<允許存放的最大元素個(gè)數(shù)>typedefstruct{elementtypesk[Ma
5、xsize];inttop;}seqstack*s;S→sk[i]表示第i個(gè)進(jìn)棧的元素S→sk[S→top]表示棧頂元素當(dāng)S→top=-1表示空棧當(dāng)S→top=Maxsize-1表示棧滿③操作算法入棧（push）入棧的主要操作是先將棧頂指針加1；然后將入棧元素放到棧頂指針?biāo)甘鞠聵?biāo)值的位置上。設(shè)用下標(biāo)從0到maxsize-1的數(shù)組Sk表示堆棧，入棧的元素值為x，則可得到入棧函數(shù)如下：intpush_stack(seqstack*s;elementtypex){if(s→top==s→Maxsize-1){printf(“outofspace!”);return(0);}s→
6、top++;s→sk[s→top]=x;return(1);}出棧（Pop）出棧運(yùn)算時(shí)，先將棧頂?shù)脑刂蒂x給某個(gè)變量，以備后面的運(yùn)算應(yīng)用；然后棧頂指針減1，將棧頂位置下移。出棧的函數(shù)如下：intpop_stack(seqtstack*s){if(s→top==-1){printf(“noelement!”);return(0);}s→top--;return(1);}2、鏈棧①鏈棧的存儲(chǔ)結(jié)構(gòu)描述typedefstructnode{elementtypedata;structnode*next;}stacknode*linkstack;②實(shí)現(xiàn)^…...topdatalink棧
7、底^…...棧底toptopxptop^…...棧底topp入棧過(guò)程：出棧過(guò)程：棧頂1m棧1底棧1頂棧2底棧2頂3.在一個(gè)程序中同時(shí)使用兩個(gè)棧（共享?xiàng)＃┯袝r(shí)，一個(gè)程序設(shè)計(jì)中，需要使用多個(gè)同一類型的棧,這時(shí)候，可能會(huì)產(chǎn)生一個(gè)?？臻g過(guò)小，容量發(fā)生溢出，而另一個(gè)?？臻g過(guò)大，造成大量存儲(chǔ)單元浪費(fèi)的現(xiàn)象。為了充分利用各個(gè)棧的存儲(chǔ)空間，這時(shí)可以采用多個(gè)棧共享存儲(chǔ)單元，即給多個(gè)棧分配一個(gè)足夠大的存儲(chǔ)空間，讓多個(gè)棧實(shí)現(xiàn)存儲(chǔ)空間優(yōu)勢(shì)互補(bǔ)。常采用將兩個(gè)棧底設(shè)在可用空間的兩端。僅當(dāng)兩個(gè)棧頂相遇時(shí)，才產(chǎn)生上溢，即所
