一.队列的基本概念
队列是一种特殊的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。在队列中允许进行插入操作的一端称为队尾，允许进行删除操作的另一端称为队首。在队列{a0,a1,...an-1}中a0称为队首元素，an-1称为队尾元素。通常，队列的插入操作叫做入队，队列的删除操作叫做出队。没有数据元素的队列称为空队列。
二.顺序队列
1.顺序队列
顺序队列的存储可用数组实现，因为入队和出队操作分别在队尾和队首进行，所以增加变量front来指示队首元素的位置，rear指示队尾元素的下一个存储单元位置。
入队操作
（1）判断队列是否为满，满则抛出异常
（2）将x插入到队列成为队尾元素
（3）rear加1
def offer(self,x): """将数据元素x插入到队列成为队尾元素""" if self.rear == self.maxSize: raise Exception("队列已满") self.queueElem[self.rear] = x self.rear += 1
出队操作
（1）判断队列是否为空，若空则返回null
(2) 返回font指针的值
（3）font指针加1
def poll(self,x): """将队首元素删除并返回其值""" if self.isEmpty(): return None p = self.queueElem(self.front) self.front += 1 return p
2.循环队列
顺序队列的多次入队、出队操作会造成有存储空间却不能进行入队操作的“假溢出”。
出现“假溢出”是因为顺序队列的存储单元没有重复使用机制，为了解决因数组下标越界而引起的“溢出问题”，可将顺序序列的首尾相连，形成循环顺序队列
然后我们发现了新的问题，队空和队满的判断条件一样，都是front==rear,解决这个问题可以少利用一个存储单元，队列最多存放maxSize-1个元素，队空的条件为front==rear，队满的条件为front=(rear+1)%maxSize
与之前的入队、出队比较
def offer(self, x): """将数据元素x插入到队列成为队尾元素""" if (self.rear+1) % self.maxSize == self.front: raise Exception("队列已满") self.queueElem[self.rear] = x self.rear = (self.rear+1) % self.maxSize def poll(self, x): """将队首元素删除并返回其值""" if self.isEmpty(): return None p = self.queueElem(self.front) self.front = (self.front + 1) % self.maxSize return p
三.链队列
链队列利用单链表实现，由于入队出队分别在队列的队尾和队首进行，不存在在队列的任意位置进行插入和删除的情况，所以不需要设置头节点，只需要将指针front和rear分别指向队首节点和队尾节点。
def offer(self, x): """将数据元素x插入到队列成为队尾元素""" s = Node(x,None) if not self.isEmpty(): self.rear.next = s else: self.front = s self.rear = s
def poll(self, x): """将队首元素删除并返回其值""" if self.isEmpty(): return None p = self.front self.front = self.front.next if p == self.rear:#删除节点为队尾节点时需要修改rear self.rear = None return p.data