棧 課件【考點(diǎn)打靶+定向訓(xùn)練】浙教版（2019）高中信息技術(shù)選修1

3.3棧棧：一種操作受限的線性表，僅允許在表的一端進(jìn)行插入或刪除。進(jìn)行插入或刪除操作的一端稱為棧頂，位于棧頂位置的元素稱為棧頂元素；相應(yīng)地，將表的另一端稱為棧底，位于棧底位置的元素為棧底元素。棧的特性1.先進(jìn)后出、后進(jìn)先出趙六王五李四張三棧頂棧底最后入棧的“趙六”最先出棧，最先入棧的“張三”最后出棧2.有限序列性?？梢允强盏?，也可以包含多個元素。棧中元素呈現(xiàn)線性關(guān)系，棧頂元素有一個前驅(qū)點(diǎn)，棧底元素有一個后繼點(diǎn)，其他元素既有一個前驅(qū)點(diǎn)，又有一個后繼點(diǎn)。棧與隊(duì)列有什么相同點(diǎn)和不同點(diǎn)？相同點(diǎn)：都是一種操作受限的線性表，都具有有限序列性的特點(diǎn)。不同點(diǎn)：隊(duì)列中的元素具有先進(jìn)先出、后進(jìn)后出的特點(diǎn)，棧中的元素則具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)。棧的基本操作棧，一般按順序結(jié)構(gòu)存儲，可以用數(shù)組實(shí)現(xiàn)。由于棧頂元素在數(shù)組中的位置會發(fā)生改變，因此使用top變量來記錄棧頂元素在數(shù)組中的位置。如下圖所示，①圖為棧結(jié)構(gòu)，②圖為用數(shù)組st存儲該棧。CBA棧頂：top=2棧底：ABC數(shù)組st012top棧的存儲①②棧的常用操作有建棧、入棧、出棧等。1.建棧在Python中，當(dāng)要存儲n個元素的棧時，可以用列表創(chuàng)建一個長度為n的棧。例如，要使4個字母“A”“B”“C”“D”按序入棧、出棧，可以建一個長度為4的棧st，元素初始值均為空串。為了操作方便，把指向棧頂元素的指針變量top值設(shè)置為-1。Python代碼實(shí)現(xiàn)如下：top=-1st=[“”]*42.入棧、出棧入棧又叫壓棧操作，把數(shù)據(jù)元素壓入棧頂。每次入棧時，棧頂指針變量top值加1，再給st[top]賦值。字母“A”“B”“C”“D”按序入棧的過程如下圖所示。0123空棧top=-1ABACBADCBAtop0123top1023top2013top3012滿棧④②③①⑤st棧的入棧過程Python代碼實(shí)現(xiàn)如下：top=top+1#top=0st[top]=“A”#字母A入棧top=top+1#top=1st[top]=“B”#字母B入棧top=top+1#top=2st[top]=“C”#字母C入棧top=top+1#top=3st[top]=“D”#字母D入棧出棧時把棧頂元素取出，同時top值減1。如果棧中沒有元素時，即top=-1，不能進(jìn)行出棧操作。Python代碼實(shí)現(xiàn)如下：whiletop>-1:print(st[top])top-=1編號為1、2、3、4的4列火車，按順序開進(jìn)一個棧式結(jié)構(gòu)的站點(diǎn)。問：開出火車站的順序有多少種？請寫出所有可能的出棧序列。進(jìn)入棧中的元素可停留、可出棧（1）出棧序列以火車“①”開頭為例，只能是“①”進(jìn)“①”出，剩下“②③④”，則有：出入棧方式出棧序列②進(jìn)②出，③進(jìn)③出，④進(jìn)④出①②③④②進(jìn)②出，③進(jìn)，④進(jìn)④出，③出①②④③②進(jìn)，③進(jìn)③出，②出，④進(jìn)④出①③②④②進(jìn)，③進(jìn)③出，④進(jìn)④出，②出①③④②②進(jìn)，③進(jìn)，④進(jìn)④出，③出，②出①④③②出棧序列以火車“②”開頭為例，只能是“①”進(jìn)，“②”進(jìn)，“②”出，剩下“③④”入棧，則有：出入棧方式出棧序列①出，③進(jìn)③出，④進(jìn)④出②①③④①出，③進(jìn)，④進(jìn)④出，③出②①④③③進(jìn)③出，①出，④進(jìn)④出②③①④③進(jìn)③出，④進(jìn)④出，①出②③④①③進(jìn)，④進(jìn)④出，③出，①出②④③①出棧序列以火車“③”開頭為例，只能是“①”進(jìn)，“②”進(jìn)，“③”進(jìn)，“③”出，剩下“④”，則有：出入棧方式出棧序列②出，①出，④進(jìn)④出③②①④②出，④進(jìn)④出，①出③②④①④進(jìn)④出，②出，①出③④②①出棧序列以火車“④”開頭為例，只能是“①”進(jìn)，“②”進(jìn)，“③”進(jìn)，“④”進(jìn)，“④”進(jìn)，“④”出，則有：④③②①。棧的應(yīng)用實(shí)例將一個十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，根據(jù)入棧、出棧的步驟，采用Python編寫的完整程序及測試結(jié)果如下所示：st=[-1]*100#列表中元素初始值為-1top=-1number=int(input(“請輸入十進(jìn)制整數(shù)：”))whilenumber>0:x=number%2top=top+1st[top]=x#入棧number=number//2whiletop>=0:print(st[top],end=“”)#出棧top=top-1請輸入十進(jìn)制整數(shù)：13輸出：1101拓展鏈接用列表自帶的函數(shù)和方法實(shí)現(xiàn)的棧Python中用列表自帶的函數(shù)和方法可以實(shí)現(xiàn)建棧、入棧、出棧、棧中元素個數(shù)的統(tǒng)計(jì)等操作。例如：stacklist=[]#建立一個空棧liststacklist.append(“A”)#字母A入棧stacklist.append(“B”)#字母B入棧print(stacklist[1])#輸出棧頂元素，為字母Bprint(len(stacklist))#輸出棧中元素的個數(shù)，為2stacklist.pop()#彈出棧頂元素print(len(stacklist))#輸出棧中元素的個數(shù)，為1，是字母A練一練1.有如下Python程序段：a=[0]*5b=[“A”,”B”,”C”,”D”,”E”]top=-1whiletop<4:top=top+1iftop%2==0:a[top]=b[top]else:a[top]=topforiinrange(2):a.pop()top=top-1print(a,top)程序運(yùn)行結(jié)束后，輸出的內(nèi)容是：A.[“A”,”B”,”C”]3B.[“A”,”B”,”C”]2C.[“A”,1,”C”]3D.[“A”,1,”C”]2D2.給定一個字符串，刪除相鄰重復(fù)項(xiàng)。例如，字符串“accdbbdca”刪除相鄰重復(fù)項(xiàng)的結(jié)果為“aca”。實(shí)現(xiàn)上述功能的python程序如下：S=input(“請輸入一個字符串：”)stack=[]#定義一個棧foriinS:if______①________:#如果當(dāng)前棧為空stack.append(i)elifi==stack[-1]:#如果當(dāng)前元素與棧頂元素相等_______②________#刪除else:_