1、第三章 棧和隊(duì)列棧stackn若限定僅在線性表的一端進(jìn)行插入和刪除操作，這樣的線性表線性表稱為棧。n能夠進(jìn)行插入和刪除操作的一端稱為棧頂top。另一端則稱為棧底bottom。n位于棧頂?shù)脑胤Q為棧頂元素，位于棧底的元素稱為棧底元素。n不含任何元素的棧稱為空棧。n特點(diǎn)：后進(jìn)先出。(Last In First Out: LIFO)n和棧有關(guān)的操作：n構(gòu)造一個(gè)不含任何元素的空棧n判斷棧是否為空棧n判斷棧是否滿n返回棧中的元素個(gè)數(shù)n清空棧n向棧頂壓入push(添加)一個(gè)元素n從棧頂彈出pop(刪除)一個(gè)元素n讀取棧頂元素棧的實(shí)現(xiàn)n和線性表類似，棧也有兩種存儲(chǔ)結(jié)構(gòu)：n(1) 順序存儲(chǔ) n用一組連續(xù)的存儲(chǔ)

2、單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。 n(2) 鏈?zhǔn)酱鎯?chǔ)。n棧被組織成一個(gè)鏈表。順序棧SqStackn用一組地址連續(xù)的存儲(chǔ)單元存放typedef struct ElemType *base;ElemType *top;int stacksize; SqStack;n判空條件ntop = basen判滿條件？n靜態(tài)數(shù)組n動(dòng)態(tài)申請(qǐng)?jiān)黾涌臻g鏈棧LinkStackn鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充n插入與刪除僅在棧頂處執(zhí)行n鏈?zhǔn)綏５臈ｍ斣阪滎^n適合于多棧操作n鏈表的基本操作可直接用于鏈棧出棧順序問(wèn)題n對(duì)于一個(gè)棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列由ABC組成，試給出所有可能的輸出序列。nA進(jìn) A出 B進(jìn)

3、 B出 C進(jìn) C出 = ABCnA進(jìn) A出 B進(jìn) C進(jìn) C出 B出 = ACBnA進(jìn) B進(jìn) B出 A出 C進(jìn) C出 = BACnA進(jìn) B進(jìn) B出 C進(jìn) C出 A出 = BCAnA進(jìn) B進(jìn) C進(jìn) C出 B出 A出 = CBAn不可能產(chǎn)生輸出序列CABn對(duì)任一輸入項(xiàng)來(lái)說(shuō)，在它之前輸入的項(xiàng)若輸出排在它之后，則必須保證是逆序輸出的。棧的應(yīng)用舉例n棧具有LIFO的特點(diǎn)，應(yīng)用于n數(shù)制轉(zhuǎn)換n括號(hào)匹配的檢驗(yàn)n行編輯程序n迷宮求解n表達(dá)式求值 Alog3-6.cppn實(shí)現(xiàn)遞歸函數(shù)n用于不支持【函數(shù)遞歸調(diào)用】的高級(jí)語(yǔ)言棧的應(yīng)用：表達(dá)式轉(zhuǎn)換n中綴表達(dá)式：A + ( B C / D) En后綴表達(dá)式：ABCD/E+n

4、后綴表達(dá)式特點(diǎn)n1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同n2、沒(méi)有括號(hào)n后綴表達(dá)式的處理過(guò)程后綴表達(dá)式的處理過(guò)程操作順序后綴表達(dá)式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4ABCDEABCT1ABT2AT3n中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理規(guī)則n1、如為操作數(shù)，直接輸出到隊(duì)列；n2、如當(dāng)前運(yùn)算符高于棧頂運(yùn)算符，入棧；n3、如當(dāng)前運(yùn)算符低于棧頂運(yùn)算符,棧頂運(yùn)算符退棧，并輸出到隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較；n4、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，且棧頂運(yùn)算符為 “（”，當(dāng)前運(yùn)算符為“）”，則棧頂運(yùn)算符退棧，繼續(xù)讀下一符號(hào)；n5、如當(dāng)前

5、運(yùn)算符等于棧頂運(yùn)算符，且運(yùn)算符為“#”，則結(jié)束讀入。()#(#=當(dāng)前運(yùn)算符棧頂運(yùn)算符n棧頂運(yùn)算符 vs 當(dāng)前運(yùn)算符步驟步驟中綴表達(dá)式中綴表達(dá)式STACK輸出輸出(進(jìn)棧進(jìn)棧/隊(duì)列隊(duì)列)1A(BCD)E# #2(BCD)E# #A3(BCD)E# # A4BCD)E# # (A5CD)E# # (AB6CD)E# # +(AB7D)E# # (ABC8D)E# # (/ABC9)E# # (/ABCD步驟步驟中綴表達(dá)式中綴表達(dá)式STACK輸出輸出(進(jìn)棧進(jìn)棧/隊(duì)列隊(duì)列)10)E# # (ABCD/11)E# # (ABCD/ 12E# # ABCD/ 13E# # ABCD/ 14# # ABCD/

6、 E15# # +ABCD/ E 16# #ABCD/ E 隊(duì)列n若限定線性表僅能在一端進(jìn)行插入，另一端進(jìn)行刪除，這樣的線性表稱為隊(duì)列。n能夠進(jìn)行插入的一端稱為隊(duì)尾rear。能夠進(jìn)行刪除的一端稱為隊(duì)頭front。n位于隊(duì)尾的元素稱為隊(duì)尾元素，位于隊(duì)頭的元素稱為隊(duì)頭元素。n不含任何元素的隊(duì)列稱為空隊(duì)列。n隊(duì)列的特點(diǎn)是先進(jìn)先出。(First In First Out: FIFO)n和隊(duì)列有關(guān)的操作：n構(gòu)造一個(gè)不含任何元素的空隊(duì)列n判斷隊(duì)列是否空隊(duì)列n判斷隊(duì)列是否滿n返回隊(duì)列中的元素個(gè)數(shù)n清空隊(duì)列n在隊(duì)尾加入一個(gè)元素n刪除位于隊(duì)頭的元素n讀取隊(duì)頭元素隊(duì)列的實(shí)現(xiàn) 順序存儲(chǔ)n在隊(duì)列的順序?qū)崿F(xiàn)中，用一組連

7、續(xù)的存儲(chǔ)單元存儲(chǔ)隊(duì)列中的元素。n(1) 隊(duì)頭固定n(2) 隊(duì)頭、隊(duì)尾均不固定n(3) 循環(huán)隊(duì)列n防止“假溢出”已分配空間未分配空間n循環(huán)隊(duì)列n存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。n隊(duì)頭、隊(duì)尾指針加1時(shí)從max-1直接進(jìn)到0，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。n隊(duì)頭指針進(jìn)1: front = (front + 1) % max;n隊(duì)尾指針進(jìn)1: rear = (rear + 1) % max;n隊(duì)列初始化：front = rear = 0;n隊(duì)空條件：front = rear;n隊(duì)滿條件：(rear + 1) % max = frontn循環(huán)隊(duì)列在隊(duì)滿條件下，事實(shí)上還有一個(gè)空置的存儲(chǔ)空間。n思考：能否利用上這個(gè)空置的空間？隊(duì)