資源簡介

3.2 隊列
【要點提示】
1.概念：隊列是一種 的線性表，允許插入的一端稱為隊首，允許刪除的一端稱為 。 ：在隊列中插入一個元素。 ：從隊列中刪除一個元素。
2.基本操作
1）以數組實現的隊列
①如上圖，可以設置一個頭指針head記錄隊首元素所在的位置，尾指針tail記錄隊尾元素的下一個位置（注意不是隊尾元素所在位置）。
【案例1】有4個字母“A”“B”“C”“D”按順序入隊、出隊時，可以創建一個隊列que，長度為5。
head=0
tail=0
que=[“”]*5
【案例2】出隊。排在隊首的元素依次出隊，head指針變量依次加1，直至head
值等于tail值時，隊列為空。
【思考】該隊列規模為4，隨著數據一個個出隊，tail已經到達索引4位置，head遞增，此時若想再入隊新數據，則超出隊列規模，但數組前幾個已出隊的位置數據已為空，這種稱為假溢現象。如何解決這個問題？
2）以鏈表實現的隊列
①隊列的鏈式存儲稱為 。
3.循環隊列
若一個普通隊列和一個循環隊列的最大容量都為n，head指向隊首元素，tail指向隊尾元素的下一位置。則關于這兩種隊列中數據元素的個數以及判斷隊列為空的條件如下：
項目 普通隊列 循環隊列
隊列中數據元素個數 tail-head (tail-head+n)%n（同樣適用于普通隊列）
隊列為空的條件 tail==head
4.常見隊列問題的Python實現
項目 普通方法 列表自帶方法 queue模塊（已導入模塊）
建隊 q=[0]*n head=0 tail=0 q=[] q=queue. Queue(n)
判斷隊列是否為空 head==tail len(q)=0 q.empty()
入隊 q[tail]=“A” tail=+=1 q.append(“A”) q.put(“A”)
出隊 head+=1 a.pop(0) q.get()
返回隊列元素個數 tail-head len(q) q.qsize()
隊列應用1：字符串加密
給定一個字符串S1,S2,…..Sn，按如下過程加密：取出第一個字符S1，將第二個字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接著把S3取出，S4放到字符串的末尾S2后面，直到最后一個字母Sn被取出。這些字母按取出的順序形成一個新的字符串，稱為密串，請編寫一個加密程序，輸入一個字符串（長度小于等于100），輸出該字符串的密串。
s=input(“請輸入字符串：”)
que=[“”]*100
head=0
tail=0
for i in range(len(s)):
_______________
________________
while headprint(__________,end="")
head+=1
if head______________
______________
______________
隊列應用2：銀行叫號排隊系統
que=[-1]*1000
head=0
tail=0
print("請輸入具體的操作編號（1.新到顧客（取號）2.下一個顧客（叫號）3.程序結束）：")
x=int(input(("請輸入操作\n")))
while x!=3:
if x==1:
___________________
print("您當前的號碼為：A%d,需要等待的人數為%d"%(________,______________))
tail=tail+1
if x==2:
if __________________:
print("對不起，沒有等待的客戶")
else:
print("請A%d號客戶準備，馬上將為您辦理業務。"%(____________))
head=head+1
x=int(input("請輸入操作\n")) #\n表示換行讀入
隊列應用3：報數游戲。已知班上有 n 名學生(用編號 1，2，3， ，n 分別表示)，學生按照編號由小到大
順時針圍成一個圓圈，從編號為 1 的學生開始順時針報數，報到 m 的同學出列；下一名同學 又從 1 開始報數，報數為 m 的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
（1）當 n=12，m=3 時，最后留下的同學的編號是________________
（2）下列代碼通過構造一個循環單向鏈表，模擬報數的過程， 逐一刪除報數為 m 的節點，直到剩下一個節點為止。請在劃線處填入合適的代碼。
n=int(input("n="))
m=int(input("m="))
lst=[]
for i in range(n-1):
lst.append([i+1,i+1])
lst.append( ①______________) #將尾節點的指針指向頭節點，構成循環單向鏈表
p=len(lst)-1
while n>1:
for i in range(1,m): #從 1~(m-1)依次報數
p=lst[p][1]
out=lst[p][1]
②______________________
n=n-1
print("最后留下的同學的編號是： ",lst[p][0])
（3）下列代碼通過構造一個循環隊列，模擬報數的過程，將報數為 m 的元素進行出隊操作(報數非 m 的元素重新入隊)，直到剩下一個元素為止。請在劃線處填入合適的代碼。
n=int(input("n="))
m=int(input("m="))
q=[0]*n
head=tail=0
for i in range(1,n+1): #構造循環隊列
q[tail]=i
③_____________________
c=0
while (head+1)%n!=tail:
c=c+1
if c==m:
head=(head+1)%n
c=0
else:
④_________________
tail=(tail+1)%n
head=(head+1)%n
print("最后留下的同學的編號是： ",q[head])
限時訓練
1.一個隊列的入隊序列是1,2,3,4，則出隊序列是（ ）
A.4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 1,3,2,4
2.下列對隊列的描述，正確的是（ ）
A.隊列的特點是先進后出
B.在隊列中，允許插入的一端稱為隊首，允許刪除的一端稱為隊尾
C.剛建立的隊列，隊首指針和隊尾指針均為0
D.出隊操作時，先將隊首指針加1，然后再將隊首元素出隊
3.下列事件執行過程與隊列特征不相符的是（ ）
A.在汽車加油站排隊加油時不允許插隊
B.當主機運行速度與打印機的打印速度不匹配時，為打印機設置一個打印數據緩沖區
C.把書疊放成一摞，最底下的書要最后才能拿出來
D.CPU分時系統可以根據用戶請求，按順序快速運行各程序段，實現多用戶同時工作的假象
4.在汽車站候車室，信息提示屏上顯示某個班車已做好準備，該車次的旅客可以檢票上車。旅客q1與q2依次排隊等待檢票，工作人員在檢票時，旅客q3,q4也排隊等待檢票。旅客q1檢完票后準備上車，這時應該接受工作人員檢票的旅客是（ ）
A.q1 B.q2 C.q3 D.q4
5.小王在使用隊列解決問題的過程中，初始時，隊列為空，隊列的首指針和尾指針分為為head、tail，接著小王開始進行了一系列的操作，操作序列為：入隊、入隊、入隊、出隊、入隊、入隊、出隊、出隊、出隊、入隊、入隊，則操作結束時head和tail的值分別為（ ）
A.4 7 B.4 8 C.5 7 D.5 8
6.某診所叫號系統中，利用隊列來存儲當前正在排隊病人的編號，head指向隊首元素，tail指向隊尾元素的下一個位置。若當前沒有病人，則head與tail的值分別為（ ）
A.head!=tail B.head>tail C.head==tail D.head7.某非循環隊列的實現方式是數組或鏈表，其指針條件為head=tail-3,則下列說法正確的是（ ）
A.該隊列中一定有3個元素
B.若該隊列以數組實現，則該隊列的長度為3
C.若該隊列以鏈表實現，則該隊列的長度為3
D.該隊列中最先出隊的元素一定是tail位置的元素
8.循環隊列指的是首尾相連的隊列，采用取余運算，可以有效解決隊列中“假溢出”的問題，有一循環隊列的示意圖如下，則該循環隊列的長度為（ ）
A.2
B.3
C.4
D.5
9.最大容量為n的循環隊列，設隊尾指針是tail，隊首指針是head，則隊列為空的條件是（ ）
A. (tail-1)%n=head B.(tail+1)%n=head C.tail=head-1 D.tail=head
10.若用能存放6個元素（索引用0-5表示）的數組來實現循環隊列，當前尾指針rear和頭指針front的值分別為1和5，當從隊列中出隊一個元素再入隊兩個元素后，rear和front的值分別為（ ）
A.3和4 B.3和0 C.5和0 D.5和1
11.使用有m+1個元素的列表data作為循環隊列SQ的存儲空間，front為隊列頭指針，rear為隊列尾指針，則執行出隊操作的語句為（ ）
A.front=front+1
B.front=(front+1)%m
C.rear=(rear+1)%(m+1)
D.front=(front+1)%(m+1)
9.編寫Python程序模擬一個循環隊列，具體代碼如下：
que=[""]*5
head=4;tail=4
que[tail]="X";tail=(tail+1)%5
que[tail]="Y";tail=(tail+1)%5
print(que[head])
head=(head+1)%5
print(tail)
執行程序后，tail指向的位置是( )
A.1 B.2 C.3 D.4
12.有如下程序：
qu=“thonepy”
h=5;t=4
s=“”
while h!=t:
s=s+qu[h]
h=(h+1)%len(qu)
print(s)
運行后，變量s的值為（ ）
A.pythone B.python C.epython D.epytho
13.循環隊列SQ（rear為隊尾指針，front為隊首指針，maxlen為循環隊列的長度）隊滿的條件是（ ）
A.rear==SQ B.(rear+1)%maxlen==front
C.rear==0 D.front==0
14.下列程序的功能是在一個循環隊列中進行入隊操作，輸入“+n”表示入隊操作，入隊元素為n，輸入“-”表示出隊操作，輸入“@”時表示操作結束，部分程序如下：
m=int(input(‘please input m:’)) #輸入隊列的規模m
que=[‘’]*m
head=tail=0
data=input(‘please input data:’)
while data!=’@’:
if data[0]==”+”:
que[tail]=data[1:]
____________
則程序中劃線處應填入的代碼為（ ）
A.head+=1 B.tail+=1 C.tail=(tail+1)%m D.tail=tail%m+1
15.小王在學習循環隊列后，發現循環隊列的本質就是將隊列空間的隊列尾指針連接首指針。小王想用循環單向鏈表表示一個循環隊列，小王知道該隊列的首指針head的位置，想嘗試向循環隊列的隊尾增加一個值為x的元素。小王寫了如下程序代碼，請完善代碼。
data=[34,21,64,23,76,54]
nextL=[5,3,4,0,1,2]
head=1
x=88
data.append(x);nextL.append(-1) #添加元素
wz=len(data)-1
_______①________
while nextL[t]!=head: #找隊尾
_______②______
nextL[t]=wz
______③___________
t=head
print(data[t],end=" ")
while nextL[t]!=head: #輸出添加后的隊列
t=nextL[t]
print(data[t],end=" ")

展開更多......

收起↑