python-数据结构 循环队列的实现 设计循环队列

1.设计你的循环队列

Leet Code 原题链接
Leet Code 原题动画演示视频
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support the following operations:

• MyCircularQueue(k): Constructor, set the size of the queue to be k.
• Front: Get the front item from the queue. If the queue is empty, return -1.
• Rear: Get the last item from the queue. If the queue is empty, return -1.
• enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
• deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
• isEmpty(): Checks whether the circular queue is empty or not.
• isFull(): Checks whether the circular queue is full or not.

2.我的思路

我们仔细研究一下Leet Code 原题动画演示视频这一个视频，发现来判断队空和队满的条件。假定我们有两个指针，分别为头指针head和尾指针tail。

• 从视频中可以看出假定head为-1且tail为-1的时候，是一个队空的条件。
• 当head==tail的时候，整个队列就只剩下一个element.
• 当(tail+1) % max_length 等于 head的时候，代表队满。
  理解这三个条件后，我们可以写出如下代码。

class MyCircularQueue(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        :type k: int
        """
        self.queue = [""] * k
        self.max_length = k
        self.head = -1
        self.tail = -1

    def enQueue(self, value):
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """

        if not self.isFull():
            if self.head == -1:
                self.head = 0
            self.tail = (self.tail + 1) % self.max_length  # 移动tail指针位置
            self.queue[self.tail] = value  # 将值插入
            return True
        else:
            return False

    def deQueue(self):
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            if self.head == self.tail:  # the last element,we will delete tha last element
                self.head, self.tail = -1, -1  # 标记这个队列为一个空队列
            else:
                # 移动head指针位置，删除这个节点只需要移动head就行
                self.head = (self.head + 1) % self.max_length  
            return True
        else:
            return False

    def Front(self):
        """
        Get the front item from the queue.
        :rtype: int
        """
        return -1 if self.isEmpty() else self.queue[self.head]

    def Rear(self):
        """
        Get the last item from the queue.
        :rtype: int
        """
        return -1 if self.isEmpty() else self.queue[self.tail]

    def isEmpty(self):
        """
        Checks whether the circular queue is empty or not.
        :rtype: bool
        """
        return self.head == -1 and self.tail == -1  # 队空条件

    def isFull(self):
        """
        Checks whether the circular queue is full or not.
        :rtype: bool
        """
        return (self.tail + 1) % self.max_length == self.head  # 如果成立，则代表队满

毛遂自荐wzxJayce的博客站点