資源簡介

(共21張PPT)
選擇性必修1《數據與數據結構》
第三章 字符串、隊列和棧
3.2 隊列的概念、特性及基本操作
情境導入
知識講解
1.隊列的概念
隊首
隊尾
2.隊列的特性
先進先出、后進后出
有限序列性
隊首：一個后繼
隊尾：一個前驅
已出隊元素
既有前驅又有后繼
隊列-基本操作
隊列的概念
隊首：允許刪除的一端
隊尾：允許插入的一端
返回
3.2.2 隊列的基本操作
隊列一般按順序結構存儲，可以用數組來實現。
如圖3.2.2所示，數組que（4個元素）：隊首元素為，隊尾元素為。
由于需要入隊和出隊，隊首元素和隊尾元素在數組que中的位置在改變。因此設置頭指針變量head和尾指針變量tail，head指向隊首元素所在的位置，tail指向隊尾元素的下一個位置。
0 1 2 3
數組que的下標
圖3.2.2 隊列的存儲
3.2.2 隊列的基本操作
0 1 2 3
數組que的下標
圖3.2.3 隊列的head、tail指針的變化圖
初始時，head指針變量與tail指針變量均指向下標為0的位置。
隊列元素,均入隊后，tail指向下標為4的位置，head指向位置不變。
0 1 2 3 4
數組que的下標
head
tail
0 1 2 3 4
數組que的下標
head
tail
tail指向隊尾元素的下一個位置


圖3.2.2 隊列的存儲
3.2.2 隊列的基本操作
0 1 2 3 4
數組que的下標
head
tail
0 1 2 3 4
head
tail
圖3.2.3 隊列的head、tail指針的變化圖
數組que的下標
tail指向隊尾元素的下一個位置


當后，head記錄下標為2的位置，tail值不變。
當后，head與tail的值均為4，隊列為空。
head
隊列的基本操作
1.建隊
head=0
tail=0
que=[“ ”]*5
2.出隊、入隊
A
0 1
A B
0 1 2
A B C
0 1 2 3
A B C D
0 1 2 3 4
tail
tail
tail
tail


隊列的基本操作
A
0 1
A B
0 1 2
A B C
0 1 2 3
A B C D
0 1 2 3 4
2.出隊、入隊
tail
tail
tail
tail


que[tail]=“A” #字母A入隊
tail=tail+1 #tail=1
que[tail]=“B” #字母B入隊
tail=tail+1 #tail=2
que[tail]=“C” #字母C入隊
tail=tail+1 #tail=3
que[tail]=“D” #字母D入隊
tail=tail+1 #tail=4
出隊時，排在隊首的元素依次出隊
head指針變量依次加1，直至head值等于tail值時，隊列為空。
為了解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區。計算機將所有的打印任務依次寫入緩沖區，以便打印機按序打印。數據緩沖區中的數據如何存儲及構造
問題與討論
按時間指令排隊打印——隊列
拓展鏈接
循環隊列是將隊列的隊首和隊尾連接起來，形成邏輯上的環狀結構。有效解決“有空閑位置不能入隊”的問題。
某隊列分配最大空間為5，其最后一個位置上的元素為”E“,隊首指針變量head的值為4，隊尾指針變量tail的值為5（tail超出隊列的邊界）。
此時，數組中存在空閑位置，但新的元素不能入隊。
改為循環隊列，則在元素“E”入隊后，head的值為4，隊尾指針重新指向隊首（tail=0）,當新元素“F”入隊后，就加入到隊首，然后tail 的值變為1,如圖所示。
循環隊列
E
0
1
2
3
4
E
0
1
2
3
4
F
tail
tail
head
head
例1 信息的加密（字符串：S1，S2，…，Sn）
按如下過程加密:
取出第一個字符S1，將第二個字符S2放到字符串的末尾Sn 后面，得到字符串S3…SnS2;
接著把S3取出，S4放到字符串的末尾Sn后面……直到最后一個字母Sn被取出。
這些字母按取出的順序形成一個新的字符串，稱為密串。
【此加密過程：取出隊首元素，存到秘串中，隊列中第二個元素升級為隊首元素；再取出隊首元素，并把該元素插入隊尾。】
以“STRING”為例：
T R I N G
0 1 2 3 4 5 6 7
R I N G
0 1 2 3 4 5 6 7
R I N G T
0 1 2 3 4 5 6 7
head
tail
head
head
tail
tail
例1 信息的加密（字符串：S1，S2，…，Sn）
程序 測試結果
s=input("請輸入字符串:") print("輸入后的字串為：") que=[""]*100 head=0 tail=0 for i in range(len(s)): #將原串全部壓入隊列 que[tail]=s[i] tail+=1 while head輸入后的字串為：Ptoynh
銀行叫號排隊系統
什么情況下適合采用“隊列”解決？？？
若問題中存在“先進先出，后進后出”的特性，即可用“隊列”解決問題。
①建立隊列que，隊列的初始長度設置為1000，初始值均為-1；設置head=tail=0。
②設計輸入提示界面，實現多次取號和叫號功能。
用X存儲輸入的數字，如果X等于1，實現取號功能; X等于2，實現叫號功能; X等于3時，程序退出。
③當x=1時，分配一個號碼，入隊指針tail+1，并顯示需要等待的人數。
④當x=2時，先判斷que隊列是否為空。若為空，則顯示無等待的人員;否則，que隊首元素出隊，head+1，并顯示可以辦理業務的客戶號碼。
銀行叫號系統
為了簡要實現“銀行叫號排隊系統”的功能，把取號、叫號流程集中到一個輸入界面上，用隊列que存儲用戶取的號
程序 測試結果
que=[-1]*1000 head=0 tail=0 print("請輸入具體的操作編號：") print("1.新到顧客（取號）") print("2.下一個顧客（取號）") print("3.程序結束") x=int(input()) while x!=3: if x==1: que[tail]=que[tail]+1 print("您當前的號碼為：A%d,需要等待的人數為%d"%(tail,tail-head)) tail=tail+1 if x==2: if head==tail: print("對不起，沒有等待的客戶") else: print("請A%d號客戶準備馬上將為您辦理業務。"%(head)) head=head+1 x=int(input("請輸入操作\n")) >> %Run 22222.py
請輸入具體的操作編號：
1.新到顧客（取號）
2.下一個顧客（取號）
3.程序結束
1
您當前的號碼為：A0,需要等待的人數為0
請輸入操作
1
您當前的號碼為：A1,需要等待的人數為1
請輸入操作
2
請A0號客戶準備馬上將為您辦理業務。
請輸入操作
3
拓展鏈接
Python自帶的隊列模塊
Python中自帶了隊列模塊，可以實現隊列的建隊、入隊、出隊等操作，代碼如下：
import queue #引入隊列模塊
q=queue.Queue(10) #建一個長度為10的隊列q
q.put(“A”) #字母“A”入隊
q.put(“B”) #字母“B”入隊
print(q.qsize( )) #輸出隊列中元素的個數，個數為2
print(q.get( )) #隊首元素出隊，出隊元素為“A”
print(q.qsize( )) #輸出隊列中的元素個數，個數為1
思考與練習
1.當需要統計隊列中元素的個數時,如何統計 請編程實現
2.給定一個能存儲100個元素的隊列,可用的下標為0到99,隊列中tail指針變量指向下標99，head指針變量指向下標51。再插入一個元素時,提示“隊列空間不夠,無法入隊”。由tail指針變量和head指針變量的值可知,隊列中的第1位置至第50位置是空的。由此說明提示信息為“假溢出”。請描述隊列出現“假溢出”現象的原因,并給出解決辦法。
隊列的概念
隊列的特性
隊列的基本操作
隊列的簡單應用
課堂小結
返回
實踐任務
要求：約瑟夫問題的隊列實現
n個人排成一圈，從某個人開始，按順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，……，1，2，3，……”報數，報到m(m>1)的人退出圈子。這樣不斷循環下去，圈子里的人數將不斷減少。請按序輸出出圈的編號。
學習評價
對自己和同伴的表現進行客觀的評價，并思考后續完善的方向。（5=優秀，4=超出一般水平，3=滿意，2=有待改進，1=不太理想）
評分項 自我評價 同學互評
能從新課導入中的對比圖中感知隊列的應用。 5 4 3 2 1 5 4 3 2 1
能理解隊列的概、特性。 5 4 3 2 1 5 4 3 2 1
能自主學習教材中“隊列的基本操作”，并遷移完成隊列的出隊操作。 5 4 3 2 1 5 4 3 2 1
能利用隊列的基本操作，解決一些簡單的含有入隊、出隊等思想的問題。 5 4 3 2 1 5 4 3 2 1
謝謝觀看

展開更多......

收起↑