11.受限线性表_队列、栈 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修

*受限线性表* 第十一章 队列、栈 一、队列 1.队列的特性 (1)队列是一种先入先出（FIFO）的线性表。允许插入的一端称为队尾tail，允许删除的一段称为队首head。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。 (2)队列也是一种线性表结构，元素个数是有限的。但由于队列插入、删除只能在两端执行，操作时受限，故我们又称其为受限线性表。 (3)队列只规定了插入和删除的方式，但并未规定其存储结构，所以队列既可以用数组实现，又可以用链表实现。 2.基于数组的队列结构 2.1创建队列 用数组创建队列时，需要创建头指针head和尾指针tail。这里需要特别指出两个指针的定义：队首指针head指向队列的第一个元素；队尾指针tail指向队列的最后一个元素的下一个位置。 head = 0 #队首指针 tail = 0   #队尾指针 que = ['']*4   #存储空间 从定义可以得到两个结论： ①队列为空的判断依据：head == tail（因为tail指向空单元） ②队列中的元素个数：num = tail - head 2.2入队和出队操作 #入队 que[tail] = 'a'  #从队尾入队 tail += 1       #队尾后移 que[tail] = 'b'  #从队尾入队 tail += 1        #队尾后移 #出队 if head != tail: #判断队列不为空     print(que[head]) #输出队首内容，出队     head += 1         #队首后移 2.3“假溢出”和循环队列 由于数组本身的存储空间是固定的，在进行多次入队和出队操作后，出现如下图所示的情况： 队尾已经超出了索引值范围，无法再执行入队操作；而队首在索引值2的位置，前面两个元素已经出队，存储空间可以继续使用。这种状况我们称为“假溢出”。当存储空间有限时，我们可以使用循环队列增加存储空间的利用率。 #入队 if (tail+1)%len(que)!=head:     que[tail] = 'a'     tail=(tail+1)%len(que) #出队 if head != tail: #判断队列不为空     print(que[head])     head=(head+1)%len(que) 这里需要注意几点： ①循环队列中队首队尾指针的定义不变，故循环队列为空的条件为：head==tail ②由于队尾定义仍是指向空单元，故循环队列需要始终留一个位置被队尾指针使用，实际可用空间只有len(que)-1。 ③循环队列计算存储空间:(tail-head)%len(que)。 ④循环队列满：(tail+1)%len(que)==head 或 (tail-head)%len(que)==len(que)-1 3.基于链表的队列结构 用链表创建队列时，队首指针head和链表头指针定义相同。但由于链表存储空间不连续且不固定，队尾指针tail只能指向队尾节点。 #创建链表队列 item = [] head = tail = -1 #入队 item.append([data,-1]) #添加新节点 if head == -1: #判断队列是否为空 head = tail = len(item)-1 #同时更新队首队尾 else: item[tail][1]=len(item)-1 #更新前向节点指针域 tail = item[tail][1] #更新尾指针 #出队 if head != -1: print(item[head][0]) head = item[head][1] #更新队首指针 基于链表队列的几个特点： ①队列为空的判断依据：head == -1 ②空队列入队时需要同时修改队首队尾指针 ③链表不存在存储空间不足的问题，但也没有办法直接统计队列长度。可以通过链表遍历，或创建变量在出入队时±1的方式计算队列长度。 4.Python自带的队列模块 import queue q = queue.Queue(10)  #生成一个长度为10的队列q q.put("A")       #入队 print(q.qsize())    #输出队列中的元素的个数,个数为1 print(q.get())      #队首元素出队，出队的元素为'A' print(q.empty())    #判断队列是否为空,空则返回True,否则返回False print(q.full())     #判断