2023学年完整公开课版队列的构造

队列的构造2在一端删除，在另一端插入的线性表删除端叫队头(head)，插入端叫队尾(tail)。特性：先进先出(FIFO,FirstInFirstOut)什么是队列？a0

a1

a2

an-1headtail3enqueue：入队列，进队在队尾插入元素。dequeue：出队列 删除队头元素

peek：取队头元素查看队列的基本操作4__init__(self) 创建队列is_empty(self) 判断队列是否为空，空返回trueenqueue(self,elem) 入对列，使elem成为新的队尾dequeue(self) 出对列，若对列为空，抛出异常peek(self) 查看队头，若对列为空，抛出异常ADTQueue5队列的链接表实现用线性表的技术实现队列，就是利用元素位置的顺序表示入队的先后。先进先出需要在表的两端操作，实现起来比栈麻烦一些首先考虑用链接表的实现，为操作的效率，考虑带表尾指针的链接表这样才能保证入队/出队操作都能在O(1)时间完成如果没有表尾指针，入队就是O(n)操作，不好采用带表尾结点指针的链接表，后端插入为O(1)操作：^入队在表尾进行，出队在表头进行，都是O(1)时间操作。实现很简单显然，前面相应链表的实现技术可以直接用于实现队列 只需修改操作名，把append改为enqueue，pop改为dequeue6队列的顺序表实现现在考虑用顺序表技术实现队列假设用尾端插入实现enqueue，出队操作应在表的首端进行为维护表中数据的完整性，出队操作取出首元素后，必须把它之后的元素逐个前移，这样得到的是O(n)操作反过来实现：虽然从尾端弹出元素是O(1)操作，但首端插入也是O(n)操作。也出现了O(n)操作，同样很不理想考虑首元素出队后元素不前移，记住新队头位置。这一设计也有问题：反复入队出队，如果元素存储区固定，一定会在某次入队时出现队尾溢出表尾（表满）的情况出现这种溢出时，顺序表前部一般会留下一些空位这是“假溢出”，并不是真的用完了整个元素区如果元素存储区自动增长（如list），首端将留下越来越大的空区。而且这片空区永远也用不到（完全浪费了）7队列的顺序表实现简单实现方式有问题的示意图（设q是队列对象）：q.headq.rear空队列e0e1e2q.headq.rearq.rearq.heade7e6再存入就导致顺序表出界实现方法不合适！8队列的顺序表实现人们提出了一种称为“环形队列”的技术，来解决这个问题q.rearq.head队列空的情况

环形队列（把数组看成环形）实现中的不变关系（不变式）：q.rear是最后元素之后空位的下标q.head是首元素的下标[q.head,q.rear)是队列中所有元素（看作按照环形排列）入队时，先存入，后移位当q.head==q.rear时队列空队列满如何判断？条件不能与队列空判断相同9队列的顺序表实现k1k2k7k6k5k4k3q.headq.rear一种方案，队列满用下面条件判断：(q.rear+1)%q.len==q.head这样做实际上总是有一个单元空置入队出队时的下标更新语句q.head=(q.head+1)%q.lenq.rear=(q.rear+1)%q.len保证更新后的下标的值正确存在其他设计。下面考虑：用head域记录队头元素位置，num记录队中元素个数队尾空位在（q.len是表长）(q.head+q.elnum)%q.len基于这两个变量实现操作，就可以不留空置单元10队列的list实现可以基于Python的list实现顺序表示的队列最简单的实现方法得到O(1)的enqueue和O(n)的dequeue由于Pythonlist没提供检查元素存储区容量的机制，我们很难利用其自动扩充元素区的机制，但是可以自己做（看下面的做法）首先，队列可能由于空而无法dequeue，自定义一个异常classQueueUnderflow(ValueError):passSQueue类的基本考虑：用SQueue对象的一个list类型的成分_elems存放队列元素用_head和_num记录首元素所在位置的下标和表中元素个数为能判断存储区满以便换一个表，需要记录表的长度，用_len11数据不变式这里的队列实现是一个比较复杂的问题要考虑一组操作和队列对象的一组成分，其中一些操作的执行可能改变一些对象成分的取值。问题：允许怎样的改变？如果一个操作有错或与其他操作不一致，就会破坏整个对象。可见，所有操作在成分修改方面必须有统一的原则，相互合作为保证对象的完整性，各操作的实现都必须遵循这些些原则为解决这类问题（一个数据结构的操作需相互协调，具有某种统一性），人们提出了“数据不变式”概念，它刻画“什么是一个完好的对象”数据不变式基于对象的成分，描述它们应满足的逻辑约束关系对象的成分取值满足数据不变式，说明这是一个状态正确的对象数据不变式提出了对操作的约束和基本保证：构造对象的操作必须把对象成分设置为满足数据不变式的状态每个操作保证其对于对象成分的修改不打破数据不变式12数据不变式针对下面实现，考虑的数据不变式是（用非形式的描述方式）：_elems成分引用着队列的元素存储区，是一个list对象，_len是该存储区的有效容量（我们并不知道该list对象的实际大小）_head是队列首元素（当时在队列里的存入最早的那个元素）的下标，_num始终记录着队列中元素的个数队列里的元素在_elems里连续存放，但需要在下标_len存入元素时，操作改在下标0的位置存入在_num==_len时出现的入队列操作将自动扩张存储区下面用一个类实现一种连续表示的队列__init__操作建立空队列，设置对象成分保证上述不变式成立两个修改对象的变动操作都维持不变式的成立，我们将仔细检查有关情况。这样一组操作形成了一套相互协调的实现前面提出过队列的其他设计，同样可以写出有关的数据不变式13队列的list实现类定义里的几个简单方法：classSQueue():def__init__(self,init_len=8):self._len=init_len#存储区长度

self._elems=[0]*init_len#元素存储

self._head=0#表头元素下标

self._num=0#元素个数defis_empty(self):returnself._num==0defpeek(self):ifself._num==0:raiseQueueUnderflowreturnself._elems[self._head]#（下页继续）14队列的list实现出队列的方法很简单#注意head更新的计算，defdequeue(self):ifself._num==0:raiseQueueUnderflowe=self._elems[self._head]self._head=(self._head+1)%self._lenself._num-=1returne入队列操作比较麻烦需要检查队列存储区是否已满存储区满时需要建一个新的，拷贝已有元素15队列的list实现入队列方法，

defenqueue(self,elem):ifself._num==self._len:self.__extend()self._elems[(self._head+self._num)%self._len]=eself._num+=1def__extend(self):old_len=self._lenself._len*=2new_elems=[0]*self._len