數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 3.1 棧

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)3.1棧棧的定義與基本操作棧的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序棧和鏈棧的比較棧的應(yīng)用案例棧的定義與基本操作棧的定義棧：限定僅在一端進(jìn)行插入和刪除操作的線(xiàn)性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱(chēng)為棧頂棧底（bottom）：另一端稱(chēng)為棧底插入位置：1~n+1刪除位置：1~n線(xiàn)性表插入位置：n+1刪除位置：n棧棧底棧頂棧的定義與基本操作棧的操作插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧a插入刪除bc此時(shí)執(zhí)行出棧操作，哪個(gè)元素可以出棧呢？棧的操作特性：后進(jìn)先出（LastInFirstOut，LIFO）空棧：不含任何數(shù)據(jù)元素的棧

如何判空棧

initStack()：初始化操作。設(shè)置一個(gè)空棧isEmpty()：判棧空函數(shù)。若為空，則返回true，否則返回false。getTop()：讀棧頂元函數(shù)。若棧不空，函數(shù)值為棧頂元素，否則為空元素NULLpush(x)：進(jìn)棧操作。將元素x插入棧中，使x成為棧的棧頂元素pop()：出棧函數(shù)。若棧不空，函數(shù)值為棧頂元素，且從棧中刪除當(dāng)前棧頂元素，否則函數(shù)值為空元素NULLclearStack()：棧置空操作。不論棧是否為空棧，置為空棧棧的定義與基本操作棧的基本操作棧的定義與基本操作棧的抽象數(shù)據(jù)類(lèi)型定義ADTStackDataModelOperationendADT棧中元素具有相同類(lèi)型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系initStack：棧的初始化clearStack：清空棧內(nèi)元素push：入棧pop：出棧getTop：取棧頂元素isEmpty：判空利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素a1a2……an順序棧Sai……0n棧底棧頂top棧的順序存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)順序棧用數(shù)組的一端作為棧底設(shè)變量top存儲(chǔ)棧頂元素所在的下標(biāo)組織形式與單鏈表類(lèi)似，鏈表的尾部是棧底，鏈表的頭部是棧頂FtopdatanextEDANULL棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)鏈棧順序棧和鏈棧的比較順序棧和鏈棧的基本算法的時(shí)間復(fù)雜度均為O(1)空間復(fù)雜度比較Java中，初始時(shí)順序棧需要確定棧的長(zhǎng)度，所以存在存儲(chǔ)元素個(gè)數(shù)的限制和浪費(fèi)存儲(chǔ)空間的問(wèn)題。鏈棧沒(méi)有棧滿(mǎn)的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用存儲(chǔ)空間時(shí)才會(huì)出現(xiàn)棧滿(mǎn)，但是每個(gè)元素都需要指針域，從而存在結(jié)構(gòu)性開(kāi)銷(xiāo)。把所有的余數(shù)按出現(xiàn)的逆序排列起來(lái)（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)棧的應(yīng)用351784210110001余數(shù)結(jié)果：100011表達(dá)式求值棧的應(yīng)用對(duì)算術(shù)表達(dá)式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號(hào)內(nèi)，后括號(hào)外的四則運(yùn)算法則，其計(jì)算順序應(yīng)為：1+2*4-9/3└─┘└─┘①②└──┘③└───┘④采用“運(yùn)算符優(yōu)先數(shù)法”對(duì)每種運(yùn)算符賦于一個(gè)優(yōu)先數(shù)，如：運(yùn)算符：*/+-#優(yōu)先數(shù)：22110其中

#是表達(dá)式結(jié)束符表達(dá)式求值時(shí)，設(shè)立兩個(gè)棧運(yùn)算符棧(OPTR)操作數(shù)棧(OPND)分別存放表達(dá)式中的運(yùn)算符和操作數(shù)

步驟OPTR棧OPND棧輸入字符主要操作──────────────────────────────────────────

1 # 1+2*4-9/3# PUSH(OPND,'1')2 # 1+2*4-9/3#PUSH(OPTR,'+')3 #+ 12*4-9/3# PUSH(OPND,'2')4 #+ 12*4-9/3# PUSH(OPTR,'*')5 #+* 124-9/3# PUSH(OPND,'4')6 #+* 124-9/3# OPERATE('2','*','4')7 #+ 18-9/3# OPERATE('1','+','8')8 # 9-9/3# PUSH(OPTR,'-')9 #- 99/3# PUSH(OPND,'9')10 #- 99/3# PUSH(OPTR,'/')11 #-/ 993# PUSH(OPND,'3')12 #-/ 993# OPERATE('9','/','3')13 #- 93# OPERATE('9','-','3')14