第9课 队列1——初识队列-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第9课　队列1——初识队列(见学生用书P69) ——3.2　队列，教材P74～81 1.理解队列的概念和特性。　2.掌握队列的基本操作，并能编程实现。 1．队列的概念与特性 (1)队列的概念 ①队列是一种　先进先出　的线性表，允许插入的一端称为　队尾　，允许删除的一端称为　队首　。 ②队列中的数据元素称为　队列元素　。在队列中插入一个元素称为　入队　，从队列中删除一个元素称为　出队　。 (2)队列的特性 ①队列具备“先进先出、后进后出”的特点。 ②队列是一种线性表结构，元素个数是　有限　的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现　线性特征　，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 2．队列的基本操作 队列一般按顺序结构存储，可以用数组来实现。设置头指针变量head和尾指针变量tail记录队首元素所在的位置和队尾元素的下一个位置。 (1)建队 由于队列以数组形式存储，利用列表创建队列。例如，创建一个队列q，长度为5，初始值为0，Python代码如下： head＝0 tail＝0 q＝[0]*5 (2)入队与出队 ①元素从队尾入队，先将元素存储到tail指针指向的位置，然后tail指针加1，向队尾方向移动。例如，数字5入队： q[tail]＝5 tail＋＝1 ②元素出队时，当队列非空时(head！＝tail)，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到head＝＝tail时，队列为空。例如，将队首位置出队： a＝q[head] head＋＝1 (3)循环队列 在顺序队列中，当队尾指针已经到达数组的上界时，不能再有入队操作，否则tail前移会导致下标越界；但数组的前部可能还有空位置，此时可以采用循环队列解决。 判断队满的语句为： head＝＝(tail＋1)%len(q) 判断队空的语句为： tail＝＝head 入队语句为： q[tail]＝5 tail＝(tail＋1)%len(q) 出队语句为： a＝q[head] head＝(head＋1)%len(q) (4)Python的queue模块 内建模块queue可以实现队列的建队、入队、出队等操作，queue中定义的方法如下。 【注意】：需要先导入模块，import queue 方法 功能 举例说明 Queue() 创建队列 q＝queue.Queue(10) #建立一个长度为10的队列q qsize() 返回队列长度，即队列中的元素个数 print(q.qsize()) put() 在队尾插入数据 q.put(10)　　　#数字10入队 get() 在队首取出数据 a＝q.get()　　#队首元素出队 empty() 判读队列是否为空，返回值True或Flase，True表示队空 full() 判读队列是否为满，返回值True或Flase，True表示队满 1．队列基本操作举例 q＝[””]*6 head，tail＝0，0 for i in range(0，6)： q[tail]＝chr(i＋65) tail＋＝1 while head！＝tail： print(q[head]，end＝” ”) head＋＝1 2．循环队列基本操作举例 q＝[””]*10 head，tail＝0，0 for i in range(0，12)： if head＝＝(tail＋1)%len(q)： head＝(head＋1)%len(q) tail＝(tail＋1)%len(q) q[tail]＝chr(i＋65) print(q，head，tail) while tail！＝head： print(q[head]) head＝(head＋1)%len(q) 　　下列关于队列的说法中，不正确的是(　C　) A．队列中所有元素呈线性特征 B．队列具备“先进先出、后进后出”的特点 C．队列中允许插入的一端称为队首 D．队列可以是空的，也可以包含多个元素 【解析】 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首，选项C错误。 变式1下列事件执行过程和队列特征不相符的是(　C　) A．在汽车加油站排队时不允许插队 B．当主机运行速度与打印机的打印速度不匹配时为打印机设置一个打印数据缓冲区 C．把书叠放成一摞，最底下的书要最后才能拿出来 D．CPU 分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 【解析】 队列是一种先进先出的线性表，选项C不符合队列的特点，选项C错误。 　　若用一个规模为20的数组来实现队列，当前指针head和tail的值分别为3、6，对队列先进行两次入队操作，再进行一次出队操作，最后再进行一次入队操作，则最后指针head和tail的值分别为(　B　) A．3和9　　　　　　B．4和9　　　　　　C．4和10　　　　　　D．5和10 【解析】 在队列的操作中，tail指针变量跟踪各元素的入队，出队时head指针变量依次加1，最后指针head和tail的值分别为4，9，选项B正确。 变式1假设高铁站的售票窗口平均每分钟过来一个人购票，每人的购票时间平均约为2分钟，某车站在中午时段开了一个售票窗口，12：01：00的时候有1个人刚开始购票，3个人在等待，那么12：11：00 时队伍中等待购票的人数为(　C　) A．7 B．8 C．9 D．10 【解析】 10分钟过来了10个人购票，总共14人，期间4人结束购票，所以队伍还有10人，1人在购票，9人在等待，选项C正确。 　　2023·温州中学检测有1 个队列，队首到队尾的元素依次为8，10，12，9。若队首元素是偶数，则先出队，再将偶数整除2 后重新入队；若队首元素是奇数，则直接出队。入队或出队各算一次操作，经过6 次操作后，队列中队首到队尾的元素依次为(　D　) A．2，3 B．6，2，3 C．9，4，5 D．9，4，5，6 【解析】 根据队列的特点“先进先出、后进后出”原则以及结合题意可得：8 出队整除2 后入队(2 次)，10 出队整除2 后入队(2 次)，12 出队整除2 后入队(2 次)。共6 次，其结果为9，4，5，6。故选项D正确。 变式12023·浙江1月选考有1 个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T 操作是指队列中1 个元素出队后再入队，Q 操作是指队列中1 个元素出队。则经过TTTQTTQ 系列操作后，队列中队首到队尾的元素依次为(　B　) A．2，9，5 B．2，5，8 C．5，8，2 D．8，3，2 【解析】 TTT 之后，队列为：9，5，8，3，2。Q 后，队列为：5，8，3，2；TT 之后，队列为：3，2，5，8。Q 后，队列为：2，5，8。故选项B正确。 　　有如下Python 程序段： s＝”ABCDEF”；head＝0；tail＝0 que＝[””]*100 for i in range(len(s))： if i%2＝＝0： 　　que[tail]＝s[i] else： 　　que[tail]＝s[len(s)－i] tail＝tail＋1 for i in range(len(s))： print(que[head]，end＝””) head＝head＋1 执行该程序段后，输出的列表情况是(　D　) A．ABCDEF B．FEDCBA C．ACEFDB D．AFCDEB 【解析】 i 的值与入队的字符如下表所示，然后将队列中的字符逐个出队输出，故选项D 正确。 0 1 2 3 4 5 A B C D E F i 0 1 2 3 4 5 s[i] A C E s[len(s)－i] F D B 变式1有如下Python程序段： n＝30 que＝[－1]*n head，tail＝0，0 for i in range(1，n)： if i%4＝＝0 or i%5＝＝0： que[tail]＝i tail＋＝1 print(tail－head) 执行该程序段后，输出的值为(　B　) A．10 B．11 C．12 D．30 【解析】 题目中的程序实现把1～30范围内能被4或被5整除的数进行入队操作，并输出最终队列que里面的元素个数，选项B正确。 变式22022·诸暨统测有如下Python程序段： st＝[”3”，”8”，”5”，”a”，”9”] que＝[0]*20 key＝2 head＝0；tail＝0 for i in range(len(st))： if ”0”<＝st[i]<＝”9”： que[tail]＝(int(st[i])＋key)%10 tail＋＝1 else： 　　head＋＝1 while head！＝tail： print(que[head]，end＝””) head＋＝1 执行该程序段后， 输出的结果是(　A　) A．0 7 1 B．5 0 7 1 C．5 0 7 c 1 D．”5” ”0” ”7” ”c” ”1” 【解析】 for循环依次取出st中的每个字符，如果该字符是数字字符，将其对应数值加2对10取余后的结果加入对列；否则，将对头元素出列。最后，程序输出队列中的所有元素。执行for循环时，st[i]＝”3” 时，5入队；st[i]＝”8”时，0入队；st[i]＝”5”时，7入队：st[i]＝”a”时，5出队，st[i]＝”9”时， 1入队。故队列中的元素依次为：0，7，1， 选项A正确。 　　利用数组a[n]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元素x入队时所执行的操作为(　B　) A．a[r%n＋1]＝x B．a[(r＋1)%n]＝x C．a[r%n－1]＝x D．a[(r－1)%n]＝x 【解析】 插入元素是在队列的尾部进行的，插入前先要将队尾指针往后移动一个位置，因为是在循环队列中插入元素，因此可用语句a[(r＋1)%n]＝x来实现，选项B正确。 变式1有如下Python程序段： q＝[”h”，”o”，”n”，”e”，”p”，”y”，”t”] head，tail＝4，3 while head！＝tail： print(q[head]，end＝””) head＝(head＋1)%len(q) 执行该程序段后，输出的结果是(　B　) A．pythone B．python C．epython D．epytho 【解析】 题目中变量q可以看作为循环队列，head和tail的初始值为4和3，while循环实现队列元素的出队过程，当head＝＝tail时停止出队，head加1往后移，移出队列q最后一个元素位置时，将返回起始位置继续往后移，直到移动至tail的位置，选项B正确。 　　输入一个字符串S1S2S3…Sn，按如下过程操作：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…SnS2；接着将S3取出，S4放到字符串的末尾S2后面……直到最后一个字符Sn被取出。这些字符按取出的顺序形成一个新的字符串，并输出这个新字符串，实现相应功能的Python程序段如下： s＝input(”请输入字符串：　”) que＝[””]*100 #该空队列可以满足需要 head＝0 tail＝0 for i in range(①　　　　　　)： #原字符串全部字符依次入队 que[tail]＝s[i] tail＋＝1 print(”加密后的串为： ”) while head<tail： #队列非空时 print(que[head]，end＝””) ②　　　　　　 if head<tail： #队列非空时，出队的元素加入队尾 ③　　　　　　 tail＋＝1 head＋＝1 上述程序段中①、②、③处填入的代码分别为(　C　) A．①len(s)＋1　②head＋＝1　③que[tail]＝que[head] B．①len(s)＋1　②tail＋＝1　③que[head]＝que[tail] C．①len(s)　②head＋＝1　③que[tail]＝que[head] D．①len(s)　②tail＋＝1　③que[head]＝que[tail] 【解析】 ①字符串的索引从0开始，从0到len(s)－1，共有n个，选项A和B排除；②que[head]出队，队首后移，填入head＋＝1；③队列非空时，出队的元素加入队尾，则填入que[tail]＝que[head]，选项C正确。 变式1 n个人站成一排，从左向右的编号分别为1～n，现在从左往右报数“1，2，1，2，…”，数到“1”的人立即站到队伍的最右端，数到“2”的人出列，反复进行，直到n个人出列为止。实现相应功能的Python程序段如下： q＝[i for i in range(9)]　#初始化编号 n＝8 head，tail＝1，0 count＝0 while head！＝tail： if count＝2： print(q[head]，”－>”，end＝””) else： 　　q[tail]＝q[head] 　　 上述程序段中加框处的代码由以下四部分组成： ①tail＝(tail＋1)%n　②head＝(head＋1)%n　③count＝0　④count＋＝1 执行程序后，输出的结果是2－>4－>6－>8－>3－>7－>5－>1－>， 则下列选项中，代码顺序正确的是(　C　) A．①②③④ B．③④②① C．④③①② D．④③②① 【解析】 每次都有出队操作，那么②head＝(head＋1)%n 必然是循环的最后一条语句，队头元素出队同时入队，所以第三条语句是队尾指针后移。数到“2”后，将count变量重新设为初始值。第一条就是count变量累加。选项C正确。 　　有如下Python程序段： import queue s＝input() q＝queue.Queue() for ch in s： q．put(int(ch)) ans＝0 while not q．empty()： ans＝ans*2＋q.get() print(ans) 若输入为1010，则输出的结果是(　B　) A．1010 B．10 C．5 D．2 【解析】 第1个循环入队操作q.put()；第2个循环出队操作q.get()；入队是高位先入队，出队是高位先出队，转换为十进制数，选项B正确。 |随|堂|检|测| 1．下列关于队列的入队和出队操作的说法中，不正确的是(　C　) A．入队操作是在队尾进行的 B．出队操作是在队首进行的 C．入队和出队操作可以在同一端进行 D．最先入队的元素肯定最先出队 【解析】 队列允许在队尾进行入队操作，允许在队首进行出队操作，不可以在同一端进行入队和出队操作，选项C错误。 2． 在某餐厅点餐系统中，利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有顾客，head和tail的关系是(　A　) A．head＝＝tail B．head<tail C．head>tail D．head！＝tail 【解析】 队列元素出队的过程中，队首指针加1，向队尾方向移动，当head＝＝tail时队列为空，选项A正确。 3．某队列的数据结构如图所示，head 和tail 分别是队列的头指针和尾指针。现对该队列进行下列操作：①队首元素出队后再入队、②队首元素出队并输出、③重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　C　) A．Python B．Ptoynh C．yhntPo D．yhntoP 【解析】 根据题意，队列出队入队过程如下(加框为出队输出)，可知出队序列为yhntPo，即为输出顺序，选项C 正确。 队列que P t o P o o 下标 0 1 2 3 4 5 6 7 8 9 10 4．2023·丽水中学检测某短信平台对短信内容长度进行审查，超过100 个字符的短信将被过滤掉，将符合要求的短信根据推送的时间逐一发送。 #所有短信按推送过来的时间已经存放在列表s 中，共有1000 条待发送的短信 q＝[””]*1000 head＝0；tail＝0 for i in range(1000)： if len(s[i])<＝100： while ： print(”现在发送的消息内容为：　”，q[head]) head＋＝1 上述程序段中加框处可选的代码有： ①tail＝tail－1　②tail＝tail＋1　③q[tail]＝s[i]　④head<＝tail　⑤head！＝tail 下列选项中，代码顺序正确的是(　C　) A．②③⑤ B．③②④ C．③②⑤ D．③①⑤ 【解析】 ①②入队操作，由于tail＝0，所以先入队(q[tail]＝s[i])，再tail后移(tail＝tail＋1)；最后循环出队，队列非空的判断语句为head！＝tail，选项C正确。 学科网（北京）股份有限公司 $$