循环队列的思考

队列

• 先入先出的数据结构
• 典型的FIFO解构
  在FIFO数据结构中首先将处理添加到队列的第一个元素。
  
  如上图所示，插入新元素(insert)操作也叫做入队(enQueue)，始终被添加到队尾，而删除元素，则始终移除第一个元素称之为出队(deQueue)。

实现

通过python

class MyQueue:
    def __init__(self):
        self.data = []
        self.head = 0
        self.size = len(self.data)

    def enQueue(self, value):
        self.data.append(value)
        return True

    def deQueue(self):
        if self.isEmpty():
            return False
        self.head += 1
        return True

    def Front(self):
        return self.data[self.head]

    def isEmpty(self):
        return self.head >= len(self.data)

if __name__ == '__main__':
    queue = MyQueue()
    queue.enQueue(2)
    queue.enQueue(4)
    queue.enQueue(6)
    queue.deQueue()
    queue.enQueue(7)
    print(queue.Front())

普通队列的缺点

当我们这样添加新元素时，队尾是有可以添加的位置的，但是如果我们遇到下面一幅图的情况呢

当我们删除元素时 (队列出队始终删除第一个元素) 第一个元素的位置将会被浪费（入队新元素始终添加在队尾）
因此大家想出了解决办法 那就是循环队列。

循环队列（浪费可耻）

• 原理
  使用固定大小的列表和两个指针来指示起始位置和结束位置。 目的是重用我们之前被浪费的内存地址。
  
  如图所示，当我们出队操作完成后只需要重新移动 tail的位置将其放在队首，我们就可以继续利用之前被浪费的空间，插入新元素。
• 关键点
  1.定义初始化大小的列表(python) list = [ ]*size
  2 .判空 ((self.tail + 1) % self.size) == self.head
  3 .改变队尾指针 self.tail = ((self.tail + 1) % self.size)
  4 .改变队头指针 self.head = ((self.head + 1) % self.size)
• 实现

class MyCircularQueue:

    def __init__(self, k):
        """
   		初始化队列，设置队列大小
        """
        self.data = [None] * k
        self.head = -1
        self.tail = -1
        self.size = k

    def enQueue(self, value):
        """
       	插入新元素
        """
        if self.isFull():
            return False
        if self.isEmpty():
            self.head = 0
        self.tail = ((self.tail + 1) % self.size)
        self.data[self.tail] = value
        return True

    def deQueue(self):
        """
        出队
        """
        if self.isEmpty():
            return False
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
            return True
        self.head = ((self.head + 1) % self.size)
        return True

    def Front(self):
        """
       获得队首
        """
        if self.isEmpty():
            return -1
        return self.data[self.head]
    def Rear(self):
        """
        获得队尾，因为有尾指针很方便
        """
        if self.isEmpty():
            return -1
        return self.data[self.tail]
    def isEmpty(self):
        """
    	判空
        """
        return self.head == -1

    def isFull(self):
        """
        判断是否已满
        """
        return ((self.tail + 1) % self.size) == self.head

if __name__ == '__main__':
    queue = MyCircularQueue(4)
    queue.enQueue(1)
    queue.enQueue(2)
    queue.enQueue(4)
    queue.enQueue(6)
    queue.deQueue()
    print(queue.Front())
    queue.enQueue(7)
    print(queue.Rear())

下一篇博客将会，带来队列在实际开发过程中的应用，以及队列在BFS（广度优先算法）上的使用。

写在最后

最近推出了公众号 coding趣谈，一位在读学生的技术提升之路，为您提供一系列我在学习路上的笔记，经验，以及感悟。往与君共勉，共同进步！ 欢迎大家来关注哦