棧　　課件　 【核心知識(shí)精講精析】 浙教版（2019）高中信息技術(shù)選修1

3.3棧新課導(dǎo)入裝置只有一端是開放的，所有的操作都只能在這開放的一端進(jìn)行。數(shù)據(jù)具有“先進(jìn)后出、后進(jìn)先出”的特征，可采用“?！边@種數(shù)據(jù)結(jié)構(gòu)。棧棧是一種后進(jìn)先出的線性表，僅允許在表的一端進(jìn)行插入或刪除操作。進(jìn)行插入或刪除操作的一端稱為棧頂，位于棧頂位置的元素稱為棧頂元素；另一端稱為棧底，位于棧底位置的元素稱為棧底元素。棧頂元素棧底元素棧的特性先進(jìn)后出、后進(jìn)先出有限序列性元素的個(gè)數(shù)是有限的，?？梢詾榭?，也可包含多個(gè)元素。棧中元素呈現(xiàn)線性特征，棧頂元素有一個(gè)前驅(qū)點(diǎn)，棧底元素有一個(gè)后繼點(diǎn)，其它元素既有一個(gè)前驅(qū)點(diǎn)又有一個(gè)后繼點(diǎn)。棧頂元素棧底元素牛刀小試1.有六個(gè)元素按照6,5,4,3,2,1的順序依次進(jìn)棧，則出棧順序不可能是（）5,4,3,6,1,24,5,3,1,2,63,4,6,5,2,12,3,4,1,5,62.一個(gè)棧的入棧序列是1,2,3,4,5，其出棧序列為s1,s2,s3,s4,s5，若s2是3，則s1不可能是（）A.1B.2C.4D.5CD棧的創(chuàng)建：數(shù)組創(chuàng)建棧一般按照順序結(jié)構(gòu)存儲(chǔ)，可以使用數(shù)組來實(shí)現(xiàn)。棧頂元素在數(shù)組中的位置會(huì)發(fā)生改變，因此使用top變量來記錄棧頂元素在數(shù)組中的位置。棧的創(chuàng)建：鏈表創(chuàng)建棧的鏈?zhǔn)酱鎯?chǔ)稱為鏈棧，設(shè)置棧頂指針top為鏈棧的頭指針。特點(diǎn)：克服了用數(shù)組實(shí)現(xiàn)的順序棧空間利用率不高的缺點(diǎn)，但要為每個(gè)棧元素分配額外的指針空間。棧操作（建棧\入棧IN\出棧OUT）例：有5個(gè)字母“a”“b”“c”“d”“e”按序入棧，可創(chuàng)建長(zhǎng)度為5的棧st：初始為空串，

棧頂指針top設(shè)置為-1代碼示例：top=-1st=[“”]*5棧按順序結(jié)構(gòu)存儲(chǔ)，通過數(shù)組實(shí)現(xiàn)，所以Python可使用列表創(chuàng)建棧棧操作（建棧\入棧IN\出棧OUT）棧頂指針top記錄棧頂元素的位置，初始值為-1，進(jìn)棧一個(gè)元素，top指針加1，即st[top]=棧頂元素棧操作（建棧\入棧IN\出棧OUT）top=-1#初始值top=top+1 #top=0st[top]=”a”#a入棧，top指向a的位置top=top+1 #top=1st[top]=”b”#b入棧，top指向b的位置top=top+1 #top=2st[top]=”c”#c入棧，top指向c的位置top=top+1 #top=3st[top]=”d”#d入棧，top指向d的位置top=top+1 #top=4st[top]=”e”#e入棧，top指向e的位置棧操作（建棧\入棧IN總結(jié)\出棧OUT）停止入棧的條件是什么？st=[“”]*5top=-1while______________top+=1st[top]=“*”top<len(st):棧操作（建棧\入棧IN\出棧OUT）出棧，排在棧頂?shù)脑匾来纬鰲＃瑃op指針變量依次減1，直至top的值等于-1棧操作（建棧\入棧IN\出棧OUT）top=4#初始值st[top]=””#e出棧top=top-1 #top=3，top指向d的位置st[top]=””#d出棧top=top-1 #top=2，top指向c的位置st[top]=””#c出棧top=top-1 #top=1，top指向b的位置st[top]=””#b出棧top=top-1 #top=0，top指向a的位置st[top]=””#a出棧top=top-1 #top=-1，?？胀Ｖ钩鰲５臈l件是什么？top=len(st)-1while____________print(st[top])st[top]=“”top-=1top!=-1:棧應(yīng)用1：十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)算法思想：1）用棧結(jié)構(gòu)存放每次獲得的余數(shù)2）根據(jù)棧特征輸出每次獲得的余數(shù)st=[0]*100#初始值為0top=-1num=int(input(“輸入十進(jìn)制數(shù)”))whilenum!=0:___________________________#將余數(shù)放入棧num=num//2whiletop!=-1:print(st[top],end=“”)______________________________top+=1st[top]=num%2st[top]=“”top-=1括號(hào)匹配將表達(dá)式中數(shù)字和運(yùn)算符號(hào)忽略，直接判斷左右括號(hào)的數(shù)量和位置是否匹配，判斷過程用棧結(jié)構(gòu)來實(shí)現(xiàn)：若出現(xiàn)左括號(hào)則進(jìn)棧，右括號(hào)則把棧頂?shù)淖罄ㄌ?hào)出棧，判斷是否匹配，分下列3種情況：棧空，出現(xiàn)右括號(hào)，不匹配。掃描結(jié)束，棧中還有左括號(hào)，不匹配。掃描結(jié)束，?？眨ヅ?。數(shù)據(jù)合并問題程序備注st=[""]*100#初始化

top=-1#初始化為空棧

flag=True#標(biāo)記是否有不匹配的情況

s=input("請(qǐng)輸入數(shù)學(xué)表達(dá)式：")初始化各項(xiàng)數(shù)據(jù)foriinrange(len(s)):

ifs[i]=="(":#左括號(hào)入棧

top+=1

st[top]=s[i]

elifs[i]==")":#右括號(hào)與棧頂元素比較

iftop==-1:

flag=False

break

else:

top-=1從左往右逐步處理數(shù)學(xué)表達(dá)式：若為左括號(hào)則入棧；若為右括號(hào)則與棧頂指針進(jìn)行匹配。數(shù)據(jù)合并問題程序備注iftop>0:#棧中還有剩余元素

flag=False棧中還有剩余元素，即左括號(hào)數(shù)量大于右括號(hào)。ifflag:

print("括號(hào)匹配")

else:

print("括號(hào)不匹配")請(qǐng)輸入數(shù)學(xué)表達(dá)式：(((a+b)*(c-d)-e)/f)括號(hào)匹配請(qǐng)輸入數(shù)學(xué)表達(dá)式：((a+b)*c)-d)+(e括號(hào)不匹配字母A、B、C、D、E、F依次入棧，然后依次出棧并輸出foriin"ABCDEF":

top+=1

st[top]=i

whiletop>-1:

print(st[top],"出棧")

top-=1st=[]

foriin"ABCDEF":

st.append(i)

print(len(st))

foriinrange(len(st)):

print(st.pop(),"出?！?用列表自帶函數(shù)和方法實(shí)現(xiàn)棧逆波蘭表達(dá)式逆波蘭表達(dá)式（后綴表達(dá)式）：將運(yùn)算符置于其運(yùn)算對(duì)象之后，沒有括號(hào)，無需考慮運(yùn)算符號(hào)的優(yōu)先級(jí)。中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：表達(dá)式中加入括號(hào)；將所有運(yùn)算符移到對(duì)應(yīng)括號(hào)的右邊；刪除所有的括號(hào)。逆波蘭表達(dá)式計(jì)算：從左往右掃描逆表達(dá)式，遇到數(shù)字入棧；遇到運(yùn)算符號(hào)，將棧中最上方的兩個(gè)元素依次出棧并用運(yùn)算符計(jì)算，將計(jì)算結(jié)果壓入棧中。重復(fù)上述過程直至表達(dá)式掃描結(jié)束。表達(dá)式第一步第二步第三步a+b*c(a+(b*c))(a(bc)*)+abc*+6+(8-2)*2/3(6+(((8-2)*2)/3))(6(((82