資源簡介

(共29張PPT)
基礎教育精品課
棧
2 棧的基本操作
1 棧的概念與特性
3 棧的應用實例
學習內容
大學
論語
中庸
孟子
將4本書依次放入收納箱
中庸
大學
孟子
論語
將4本書依次從收納箱取出
彈匣中子彈裝彈過程（入棧）
文字處理軟件的“撤銷 ”操作
網頁瀏覽器的“ 后退 ”鍵
消毒桶中餐盤的取放
中庸
大學
孟子
論語
棧的概念
棧底：
棧頂：
中庸
大學
孟子
論語
ü 先進后出 、 后進先出
ü 有限序列性
棧的特性
棧底：
棧頂：
相同點
有限序列， 線性表結構， 元素個數是有限的， 可以 是空的， 也可以包含多個 元素。
棧是“ 先進后出 ”， 僅在 棧頂 一 端進行入棧或出棧操作；
隊列是“ 先進先出 ”， 可 以在兩端進行操作， 其中隊尾 一 端入隊， 隊首 一 端出隊。
問題與討論：棧與隊列有什么相同點與不同點？
不同點
A B C
D
數組 st 0 1 2
3
D
C
B
A
棧的存儲
top=3 top=2 top= 1 top=0
使用數組st來存儲棧
棧底：
棧頂：
D
C
D
C
B
A
棧的存儲
top=3 top=2 top= 1 top=0
B
A
^
棧的鏈式存儲結構
棧底：
棧頂：
top
top = - 1
st = ['']*4
棧的基本操作：建棧
3
2
1
0
下標
空棧
top = top + 1 st[top] = 'A' top = top + 1 st[top] = 'B' top = top + 1 st[top] = 'C' top = top + 1 st[top] = 'D'
下標
3 2 1
top→ 0
棧的基本操作：入棧
D
C
B
A
C
B
A
B
A
A
3
top→ 2
1 0
top→ 3
2 1 0
3
2
top→ 1 0
① ② ③ ④
a = ['A','B','C','D'] for i in a:
=
D
C
B
A
棧的基本操作：入棧
3
2
1
0
下標
思考：
若棧空則不能出棧， 判斷棧空的條件是什么？
下標
top→ 3
2
1
0
D
C
B
A
出棧時棧頂元素取出， 同時top值減1
棧的基本操作：出棧
出棧和取出棧頂元素有什么區別？
輸出棧頂元素代碼如何實現？
print(st[top])
top == - 1
while top > - 1:
print(st[top],end="") top = top - 1
下標
top→ 3
2
1
0
D
C
B
A
棧的基本操作：出棧
運行結果：
DCBA
問題與討論：
字母A,B,C按順序入棧， 請問出棧的順序可能有哪幾種？
A,B,C
A,C,B
B,A,C
B,C,A
C,B,A
C,A,B
A
B
C
問題與討論：
字母A,B,C按順序入棧， 請問出棧的順序可能有哪幾種？
B,C,A
C,B,A
C,A,B
A,B,C
A,C,B
B,A,C
A
B
C
第 一章項目挑戰中的“ 用戶角色特征值 ”， 把該值 （十進制） 轉換成二進制， 采用“ 除 二取余法 ”， 利用
棧來存儲每次計算得到的余數 。 (6)10 = (110)2
22
2
1
1
0
…
…
…
…
…
…
棧的實例：進制轉換
2 top→1 0 入棧過程 top→2 1 0
2 6 2 3 2 1
0
棧的實例：進制轉換
特征值的變化： 6→3→ 1→0
… …0
……1 ……1
2
1 top→ 0
0
1
0
1
1
0
n= 1 ②
n=0 ③
n=3 ①
2 2
1 1
top→ 0 0
top = - 1
② ③ ④
出棧過程
1 0
top→2
1
0
①
1
棧的實例：進制轉換
1
0
0
1
1
0
2
top→1
0
stack = [- 1]* 100
top = - 1
n = int(input("請輸入十進制整數：")) while :
x = n % 2
top = top + 1
n = n // 2
while top >= 0:
print(stack[top],end="")
=
棧的實例：進制轉換
(6×(3+2)-4)÷2
6×(3+2)-4)÷2 (6×(3+2-4)÷2 )6×)3+2(-4(÷2
判斷 一 個數學計算式中的括號（只有小括號） 是否匹配。
匹配
不匹配
不匹配
不匹配
棧的實例：括號匹配
括號的數量
括號的位置
從左往右遍歷， 遇到左括號， 入棧， 遇到右括號， 出棧。
① 棧空， 出現右括號， 不匹配
② 遍歷結束， 棧中還有左括號（棧不空）， 不匹配 ③ 遍歷結束， 棧空， 匹配
1.計算式中只關注括號， 忽略其他字符 ( ( ) ) 2.判斷左右括號的數量與位置時， 采用棧結構來設計
棧的實例：括號匹配
第 一 步： 抽象與建模
(6×(3+2)-4)÷2
top = - 1
① ② ③ ④
棧的實例：括號匹配
第 二 步： 設計算法
( ( )
)
(
(
(
(
1
top→ 0
1
top→ 0
top→1
0
1
0
該字符是
右括號？
從左往右遍歷
結束？
該字符是
左括號？
棧的實例：括號匹配
棧空？
棧空？
N Y
不匹配
不匹配
匹配
出棧
入棧
N
N
N
N
Y
Y
Y
Y
第三步： 編寫程序
st = [""]* 100; top = - 1 #建棧 flag= True #標記是否有不匹配的情況 s = input("輸入計算式：") for i in range(len(s)): #完善代碼 if top >= 0: #棧中還有左括號 flag = False if flag: print("括號匹配") else: print("括號不匹配")
棧的實例：括號匹配
stacklist[] #建立 一 個空棧
stacklist.append("A") #字母A入棧
stacklist.append("B") #字母B入棧
print(stacklist[1]) #輸出棧頂元素， 為字母B
print(len(stacklist)) #輸出棧中元素個數， 為2
stacklist.pop() #彈出棧頂元素
print(len(stacklist)) #輸出棧中元素個數， 為1， 是字母A
拓展：用列表自帶函數和方法實現棧
小結與練習
1. 編號為1 、 2 、 3 、 4的4列火車， 按順序開進 一 個棧式 結構的站點 。 開出火車站的順序有多少種？ 請寫出所
有可能的出棧序列。
2. 元素a,b,c,d,e按序入棧， 在所有的出棧序列中， 以d 開 頭的出棧序列有哪些？
3. 參照十進制轉二進制的方法， 編寫 一 個將十進制數N 轉換為r進制數的程序。
4. 如果括號匹配問題中， 既有小括號 、 又有中括號和大 括號， 請你設計算法并編寫程序判斷括號是否匹配。
小結與練習

展開更多......

收起↑