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

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

如何判空棧

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

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

#是表達(dá)式結(jié)束符表達(dá)式求值時，設(shè)立兩個棧運算符棧(OPTR)操作數(shù)棧(OPND)分別存放表達(dá)式中的運算符和操作數(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