第三章字符串、隊列和棧

選修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》3.3棧

學(xué)習(xí)目標(biāo)

棧

棧的概念與特性棧的基本操作

棧的概念和特性棧是一種操作受限的線性表，僅允許在表的一端進行插入或刪除?！５母拍睢５奶匦裕?）先進后出、后進先出

（2）有限序列性

棧是一種線性表結(jié)構(gòu)，元素個數(shù)有限。?？梢詾榭铡?/p>

棧

棧底元素棧頂元素

·棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈棧）

棧的基本操作·棧一般按順序結(jié)構(gòu)存儲的，可以用數(shù)組來實現(xiàn)，而在Python語言中，可以用列表實現(xiàn)。a1a2a3a40123棧底：DCBA^

棧

topa4a3a2a1棧頂：top=3棧結(jié)構(gòu)數(shù)組st的下標(biāo)：數(shù)組存儲棧top=3

·建棧

棧的基本操作top=-1st=[“”]*4

棧

3210空棧下標(biāo)top=-1

·入棧（又稱壓棧操作）

棧的基本操作top=-1st=[“”]*4top+=1st[top]=“A”

棧

3210空棧下標(biāo)top=-13210A下標(biāo)top32C1B0A下標(biāo)top3D2C1B0A下標(biāo)top滿棧top+=1st[top]=“B”top+=1st[top]=“C”top+=1st[top]=“D”代碼：

·出棧

棧的基本操作

棧

3210空棧下標(biāo)top=-13210A下標(biāo)top32C1B0A下標(biāo)top3D2C1B0A下標(biāo)top滿棧

·棧的入棧和出棧

棧的基本操作st=[""]*6top=-1#元素依次入棧foriin"ABCDEF":top+=1st[top]=i#元素依次出棧，直至棧為空whiletop>-1:print(st[top],end="")top-=1

棧

輸出結(jié)果：FEDCBA

·列表自帶的方法實現(xiàn)棧

棧的基本操作·建立空棧：

stacklist=[]·入棧：

stacklist.append(“A”)·出棧：

stacklist.pop()·輸出棧頂元素：

print(stacklist[len(stacklist)-1])print(stacklist[-1])·輸出棧中元素個數(shù)：

print(len(stacklist))

棧

·列表自帶的方法實現(xiàn)棧的入棧和出棧

棧的基本操作st=[]foriin"ABCDEF":st.append(i)print(st)whilest:print(st.pop(),end="")

棧

輸出結(jié)果：['A','B','C','D','E','F']FEDCBA

·十進制轉(zhuǎn)二進制

棧的基本應(yīng)用st=[-1]*100top=-1number=int(input("請輸入十進制整數(shù)："))whilenumber>0:x=number%2top+=1st[top]=xnumber=number//2whiletop>=0:print(st[top],end="")top=top-1

棧

輸出結(jié)果：請輸入十進制整數(shù)：1001100100

·逆波蘭表達式的計算

棧的基本應(yīng)用str=input("請輸入逆波蘭表達式：")stack=[]foriinstr.split():ifiin"+-*/":s2=stack.pop()s1=stack.pop()#eval函數(shù)執(zhí)行一個字符串表達式，并返回表達式的值。該返回值為字符串stack.append(eval("%s%s%s"%(s1,i,s2)))else:stack.append(i)print("result：%s"%stack[0])

棧

輸出結(jié)果：請輸入逆波蘭表達式：682-2*3/+result：10.0

·思考

棧的基本應(yīng)用

棧

如何把計算表達式轉(zhuǎn)化成