第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表示队满 |
|
学科网(北京)股份有限公司