数据结构-队列

一.队列的基本概念

队列是一种特殊的线性表,其插入操作只能在表的尾部进行,删除操作只能在表头进行。在队列中允许进行插入操作的一端称为队尾,允许进行删除操作的另一端称为队首。在队列{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