資源簡介

(共20張PPT)
第三章 字符串、隊列和棧
選修一《數據與數據結構》
3.2 隊列的概念、特性與基本操作
隊列是一種先進先出的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。
隊列是什么？
太抽象了，無法理解
隊列是什么？
隊尾
隊首
隊列是一種先進先出的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。
隊列中的數據被稱為隊列元素
隊列元素
先進先出
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
A
C
B
隊列
隊列的特性
一、先進先出，后進后出
元素入隊順序和元素出隊順序一致。
二、有限序列性：隊列元素個數有限
隊列可以為空，也可以包含多個元素，隊首元素只有一個后繼點，隊尾元素只有一個前驅點，其他元素既有一個前驅點，又有一個后繼點。
A
C
B
前驅點
后繼點
隊列
前驅節點
后繼節點
鏈表
A
C
B
隊列
隊列的基本操作
自主學習：閱讀課本P70-P71，思考如何使用Python完成隊列的建隊、入隊和出隊操作呢？
提示：隊列一般按順序結構存儲，可以通過數組實現
a1 a2 a3 a4
0
1
2
3
數組下標
隊列存儲
隊列的基本操作
提示：隊列一般按順序結構存儲，可以通過數組實現
a1 a2 a3 a4
0
1
2
3
數組下標
隊列存儲
head
記錄隊首元素所在的位置
tail
記錄隊尾元素所在位置的下一位置
0
1
2
3
4
tail
head
空隊列
0
1
2
3
4
tail
head
入隊
隊列的基本操作
提示：隊列一般按順序結構存儲，可以通過數組實現
a1 a2 a3 a4
0
1
2
3
數組下標
隊列存儲
0
1
2
3
4
tail
head
空隊列
a1
0
1
2
3
4
tail
head
入隊
head
記錄隊首元素所在的位置
tail
記錄隊尾元素所在位置的下一位置
隊列的基本操作
提示：隊列一般按順序結構存儲，可以通過數組實現
a1 a2 a3 a4
0
1
2
3
數組下標
隊列存儲
0
1
2
3
4
tail
head
空隊列
a1 a2
0
1
2
3
4
tail
head
入隊
a1 a2
0
1
2
3
4
tail
head
出隊
head
記錄隊首元素所在的位置
tail
記錄隊尾元素所在位置的下一位置
隊列的基本操作
提示：隊列一般按順序結構存儲，可以通過數組實現
0
1
2
3
4
tail
head
空隊列
a1 a2
0
1
2
3
4
tail
head
入隊
a2
0
1
2
3
4
tail
head
出隊
head
記錄隊首元素所在的位置
tail
記錄隊尾元素所在位置的下一位置
a1 a2 a3 a4
0
1
2
3
數組下標
隊列存儲
隊列的基本操作
0
1
2
3
4
tail
head
空隊列
a1 a2
0
1
2
3
4
tail
head
入隊
a2
0
1
2
3
4
tail
head
出隊
自主學習：閱讀課本P70-P71，思考如何使用Python完成隊列的建隊、入隊和出隊操作呢？
假設我們現在有“A”“B”“C”“D”4個字母，如何實現建隊、入隊、出隊呢？
隊列的基本操作-建隊
假設我們現在有“A”“B”“C”“D”4個字母，如何進行建隊呢？
思考2個問題：一、需要幾個變量？二、列表長度是多少？
0
1
2
3
4
tail
head
空隊列
Python源碼
head=0
tail=0
que=[“”]*
5
【課后思考】為什么列表長度是5，而不是4呢？
隊列的基本操作-入隊
A
0
1
2
3
4
tail
head
①
A B
0
1
2
3
4
tail
head
②
A B C
0
1
2
3
4
tail
head
③
入隊Python代碼如下
que[tail]=“A”
tail=tail+1
que[tail]=“B”
tail=tail+1
que[tail]=“C”
tail=tail+1
que[tail]=“D”
tail=tail+1
隊列的基本操作-出隊
A B C D
0
1
2
3
4
tail
head
①
B C D
0
1
2
3
4
tail
head
②
C D
0
1
2
3
4
tail
head
③
出隊Python代碼如下
print(que[head]) # 輸出A
que[head]=“”
head=head+1
print(que[head]) # 輸出B
que[head]=“”
head=head+1
print(que[head]) # 輸出C
que[head]=“”
head=head+1

展開更多......

收起↑