资源简介

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=" ")

展开更多......

收起↑