python - 在设计循环队列中将queue.front初始化为-1或0

Question

我正在从问题Design Circular Queue - LeetCode中学习队列

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 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.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

• All values will be in the range of [0, 1000].
• The number of operations will be in the range of [1, 1000].
• Please do not use the built-in Queue library.

我模仿古德里奇的教科书Data Structures and Algorithms in Python并编写了一个友好可读的解决方案

1、只有三个数据(_queue、_len、_front)

2、初始化self._front为0

class MyCircularQueue:
     #Runtime: 76 ms, faster than 53.17%
     #Memory Usage: 13.6 MB, less than 7.24% 

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self._queue = [None] * k #the basic 
        self._capacity = k 
        self._len = 0 
        #The first three categorize as a group, the 4th as the second group
        self._front = 0
        #self._rear is not necessary, because rear = front + length -1

    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull(): return False
        avail = (self._front + self._len) % (self._capacity)
        self._queue[avail] = value 
        self._len += 1
        return True 

    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False 
        self._queue[self._front] = None #overrode the current node 
        self._front = (self._front+1) % self._capacity 
        self._len -= 1
        return True

    def Front(self) -> int:
        """
        Get the front item from the queue.
        """
        if not self.isEmpty():
            return self._queue[self._front]
        else:
            return -1


    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """
        if not self.isEmpty():
            _rear = (self._front + self._len - 1) % self._capacity
            return self._queue[_rear]
        else:
            return -1


    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return self._len == 0 


    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        return self._len == self._capacity 

Goodrich 的设计非常好，读起来省力。

但是，在阅读其他提交后，常见的做法是将 self._fornt 和 self._rear 初始化为 -1，认为这是努力阅读或写作。

摘录一个性能优于98%的案例

def deQueue(self):
    """
    Delete an element from the circular queue. Return true if the operation is successful.
    :rtype: bool
    """
    if self.isEmpty():
        return False 
    self.head = (self.head+1) % self.maxlen
    self.currlen -= 1
    if self.isEmpty(): #have to take care of self.head and self.tail
        self.head = -1
        self.tail = -1

   #another submission which initialize front and rear =-1
    def enQueue(self, value: 'int') -> 'bool':
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if (self.len == self.capacity): return False

        # To check if full
        #if (self.rear == self.front - 1 or (self.rear == self.capacity - 1 and self.front == 0) )
        if (self.front == -1):
            self.front, self.rear = 0, 0
        elif (self.rear == self.capacity - 1 and self.front != 0):
            # make rear start (case when element was removed from start)
            self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity
        self.data[self.rear] = value
        self.len += 1
        return True

由于 python 隐藏了大多数实现细节，

采用front或rear作为-1有什么优势？

Answer 1

我总结了常见解决方案和您的解决方案之间的主要区别是:

1. 使用rear指针来标记尾部
2. 当循环队列为空时，将front和rear设置为-1
3. 更多if else逻辑分支

总的来说，我认为这两种解决方案没有太大区别，只是倾向不同。如果你想知道这背后的细微差别，我会为你解释。

在您看来，您倾向于使用较少的变量并尝试将所有逻辑统一在一起，并使代码干净且易于理解。

相比之下，他想提高性能(也许只是一点点)，并做出更好的摘要。我来详细解释一下:

1. 提高性能:

   • 您可以将后方视为“以空间换时间”。每一个与rear相关的地方，都会通过(self._front + self._len - 1) % self._capacity重新计算当前的rear，但是他刚刚从后方过来。他缓存后方以供高频使用。
     缓存可以加快查询速度，但会增加维护(修改时)的成本。所以实际上是否应该使用缓存是根据场景而定的。如果查询比修改更频繁，则应该使用它。在此特定问题中，如果 Rear 使用超过 enQueue 和 deQueue，您可以使用 rear 来降低重新计算成本.
   • 他在enQueue和deQueue中使用了更多的if else逻辑分支。通过处理特定的条件可以稍微提高性能。具体来说，它减少了空、满或单元素情况下的 +-% 操作。

2. 抽象:
   他的解决方案是更加面向对象的设计。对于循环队列，哪些属性很重要？当然，前、后和状态(空、满或其他)。因此他保留rear，并在空时分配-1以表示特殊状态。
   良好的抽象将有利于功能的可扩展性。例如，我们想向MyCircularQueue添加更多功能，也许rear和state在这里很有帮助。

以上均为个人观点，可能不正确，仅供引用。 :)