浙教版 (2019)3.2 隊列優(yōu)質(zhì)課件ppt

這是一份浙教版 (2019)3.2 隊列優(yōu)質(zhì)課件ppt，共16頁。PPT課件主要包含了約瑟夫游戲，輸出3，tail，head，輸出361，隊列的特性，隊列的操作，①隊列的存儲，約瑟夫的隊列實現(xiàn)，輸出36等內(nèi)容，歡迎下載使用。
n個人排成一圈，從某個人開始，按順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，…，m，1，2，3，…”報數(shù)，報到m（m＞1）的人退出圈子。按原始編號輸出最后一個出圈的編號。
任務(wù)一：當(dāng)n=8,m=3時，用隊列數(shù)據(jù)結(jié)構(gòu)，請每位同學(xué)按游戲規(guī)則模擬一下，并按順序輸出出圈人員的編號。
1.隊列的概念 隊列是一種先進(jìn)先出的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。隊列中的數(shù)據(jù)元素稱為隊列元素。在隊列中插入一個元素稱為入隊，從隊列中刪除一個元素稱為出隊。
① 先進(jìn)先出、后進(jìn)后出。隊首元素a1優(yōu)先出隊，緊接著是a2，a3，…，an–1，隊尾元素an最后出隊。
② 有限序列性。隊列也是一種線性表結(jié)構(gòu)，元素個數(shù)是有限的。隊列可以是空的，也可以包含多個元素。隊列中所有元素呈現(xiàn)線性特征，隊首元素只有一個后繼點，隊尾元素只有一個前驅(qū)點，其他元素既有一個前驅(qū)點，又有一個后繼點。
隊列一般按順序結(jié)構(gòu)存儲，可以用數(shù)組來實現(xiàn)。如圖所示，數(shù)組que中存儲了一個隊列，共有4個元素，隊首元素為“A”，隊尾元素為“D” 。由于在入隊和出隊的過程中，隊首元素和隊尾元素的位置會改變，因此需要設(shè)置頭指針變量head和尾指針變量tail，head記錄隊首元素所在的位置，tail記錄隊尾元素的下一個位置。
② 隊列的入隊、出隊
初始時，head指針變量與tail指針變量均記錄下標(biāo)為0的位置。元素“A”，“B”，“C”，“D”依次入隊后，tail值為4，head值為0，如圖所示。
que=[]head=0tail=0n,m=map(int,input().split())fr i in range(n): que.append(i+1) tail+=1tmp=0cnt=0
while head