資源簡介

(共16張PPT)
隊列
n個人排成一圈，從某個人開始，按順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，…，m，1，2，3，…”報數，報到m（m＞1）的人退出圈子。按原始編號輸出最后一個出圈的編號。
1
2
3
4
5
……
n
6
7
8
約瑟夫游戲
1
2
3
4
5
……
n
6
7
8
約瑟夫游戲
任務一：當n=8,m=3時，用隊列數據結構，請每位同學按游戲規則模擬
一下，并按順序輸出出圈人員的編號。
1
2
3
4
5
6
7
8
約瑟夫游戲
1 2 3 4 5 6 7 8 …
4 5 6 7 8 1 2 …
輸出：3
tail
tail
head
head
約瑟夫游戲
4 5 6 7 8 1 2 …
head
tail
輸出：3 6 1
7 8 1 2 4 5 …
head
tail
2 4 5 7 8 …
head
tail
隊列
1.隊列的概念
隊列是一種先進先出的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。隊列中的數據元素稱為隊列元素。在隊列中插入一個元素稱為入隊，從隊列中刪除一個元素稱為出隊。
隊列
2.隊列的特性
① 先進先出、后進后出。隊首元素a1優先出隊，緊接著是a2，a3，…，an–1，隊尾元素an最后出隊。
② 有限序列性。隊列也是一種線性表結構，元素個數是有限的。隊列可以是空的，也可以包含多個元素。隊列中所有元素呈現線性特征，隊首元素只有一個后繼點，隊尾元素只有一個前驅點，其他元素既有一個前驅點，又有一個后繼點。
隊列
3.隊列的操作
①隊列的存儲
隊列一般按順序結構存儲，可以用數組來實現。如圖所示，數組que中存儲了一個隊列，共有4個元素，隊首元素為“A”，隊尾元素為“D” 。由于在入隊和出隊的過程中，隊首元素和隊尾元素的位置會改變，因此需要設置頭指針變量head和尾指針變量tail，head記錄隊首元素所在的位置，tail記錄隊尾元素的下一個位置。
隊列
3.隊列的操作
② 隊列的入隊、出隊
初始時，head指針變量與tail指針變量均記錄下標為0的位置。元素“A”，“B”，“C”，“D”依次入隊后，tail值為4，head值為0，如圖所示。
隊列
4.約瑟夫的隊列實現
que=[]
head=0
tail=0
n,m=map(int,input().split())
for i in range(n):
que.append(i+1)
tail+=1
tmp=0
cnt=0
while headtmp=que[head]
head+=1
cnt+=1
if cnt==3:
print(tmp,end=" ")
cnt=0
else:
tail+=1
que.append(tmp)
1 2 3 4 5 6 7 8 …
tail
head
0
1
2
3
4
5
6
7
隊列
5.思考
輸出：3 6
7 8 1 2 4 5 …
head
tail
輸出：3 6 1
2 4 5 7 8
head
tail
當第3個人出圈時，隊列中前面的9個位置是空的，造成空間上的浪費，請問可以用什么方法解決？
循環隊列
循環隊列是將隊列的隊首和隊尾連接起來，形成邏輯上的環狀結構。當對循環隊列中的元素進行入隊、出隊操作時，隊首指針變量和隊尾指針變量可以循環指向所有位置，從而有效地解決隊列中“有空閑位置卻不能入隊”的問題。如圖3.2.6所示，某隊列分配的最大空間為5，其最后一個位置上的元素為“E”，隊首指針變量head的值為4，隊尾指針變量tail的值為5（tail超出了隊列的邊界），此時，數組中存在空閑位置，但新的元素不能入隊。
循環隊列
將該隊列改為循環隊列，則在元素“E”入隊后， head的值為4，隊尾指針重新指向隊首（tail的值為0），當新元素“F”入隊時，就加入到隊首，然后
tail的值變為1，如圖3.2.7所示。
約瑟夫的循環隊列實現
當n=8,m=3時，循環隊列的入隊、出隊如圖所示：
1 2 3 4 5 6 7 8
tail
head
0
1
2
3
4
5
6
7
8
2 3 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
2 3 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
2 4 5 6 7 8 1
tail
0
1
2
3
4
5
6
7
8
head
輸出：3
約瑟夫的循環隊列實現
n,m=map(int,input().split())
que=[0]*(n+1)
head=0
tail=0
for i in range(n):
que[tail]=i+1
tail+=1
cnt=0
tmp=0
while head!=tail:
tmp=que[head]
head=(head+1)%(n+1)
cnt+=1
if cnt==m:
print(tmp,end=" ")
cnt=0
else:
que[tail]=tmp
tail=(tail+1)%(n+1)
1 2 3 4 5 6 7 8
tail
head
0
1
2
3
4
5
6
7
8
隊列
2.隊列的特性
3.隊列的基本操作
4.循環隊列
1.隊列的概念

展開更多......

收起↑