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

| 15页
| 173人阅读
| 1人下载
教辅
浙江良品图书有限公司
进店逛逛

新版页眉

学科网 zxxk.com学科网 zxxk.com

第9课 队列1——初识队列(见学生用书P69)

 

——3.2 队列,教材P74~81

1.理解队列的概念和特性。 2.掌握队列的基本操作,并能编程实现。

1.队列的概念与特性

(1)队列的概念

①队列是一种 先进先出 的线性表,允许插入的一端称为 队尾 ,允许删除的一端称为 队首 。

②队列中的数据元素称为 队列元素 。在队列中插入一个元素称为 入队 ,从队列中删除一个元素称为 出队 。

(2)队列的特性

①队列具备“先进先出、后进后出”的特点。

②队列是一种线性表结构,元素个数是 有限 的。队列可以是空的,也可以包含多个元素。队列中所有元素呈现 线性特征 ,队首元素只有一个后继点,队尾元素只有一个前驱点,其他元素既有一个前驱点,又有一个后继点。

2.队列的基本操作

队列一般按顺序结构存储,可以用数组来实现。设置头指针变量head和尾指针变量tail记录队首元素所在的位置和队尾元素的下一个位置。page number 0

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

(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)

判断队空的语句为:page number 1

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

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表示队满

 

page number 2

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。