python - 在设计循环队列中将 queue.front 初始化为 -1 或 0
问题描述
我正在从问题设计循环队列中学习队列 - LeetCode
设计循环队列的实现。循环队列是一种线性数据结构,其操作基于FIFO(先进先出)原则,最后一个位置与第一个位置连接形成一个圆圈。它也被称为“环形缓冲区”。
循环队列的好处之一是我们可以利用队列前面的空间。在普通队列中,一旦队列满了,即使队列前面有空间,我们也无法插入下一个元素。但是使用循环队列,我们可以使用空间来存储新值。
您的实现应支持以下操作:
MyCircularQueue(k)
:构造函数,设置队列大小为k。Front
:从队列中获取最前面的项目。如果队列为空,则返回 -1。Rear
:从队列中获取最后一项。如果队列为空,则返回 -1。enQueue(value)
: 将一个元素插入循环队列。如果操作成功,则返回 true。deQueue()
:从循环队列中删除一个元素。如果操作成功,则返回 true。isEmpty()
:检查循环队列是否为空。isFull()
:检查循环队列是否已满。例子:
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
笔记:
- 所有值都将在 [0, 1000] 的范围内。
- 操作数将在 [1, 1000] 范围内。
- 请不要使用内置的 Queue 库。
我模仿古德里奇的教科书《Python 中的数据结构和算法》,并编写了一个友好易读的解决方案
1、只有三个数据(_queue, _len, and _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
什么?
解决方案
我总结了常见解决方案和您的解决方案之间的主要区别是:
- 使用
rear
指针标记尾部 - 当循环队列为空时,设置
front
和rear
-1
- 更多
if
else
逻辑分支
总的来说,我认为这两种解决方案没有太大区别,只是趋势不同。如果您想知道这背后的细微差别,我将为您解释。
在您看来,您倾向于使用较少的变量并尝试将所有逻辑统一在一起,并使代码清晰易懂。
相比之下,他想提高性能(也许只是一点点),并做出更好的抽象。我将详细解释:
增强性能:
- 您可以将
rear
其视为“以空间换时间”。每一个涉及到的地方rear
,你都会从中rear
得到(self._front + self._len - 1) % self._capacity
,而他只是从中得到rear
。他缓存rear
高频使用。
缓存可以加快查询速度,但会增加维护成本(修改时)。所以实际上是否应该使用缓存是基于场景的。如果查询比修改更频繁,您应该使用它。在这个特定的问题中,如果Rear
使用超过enQueue
和deQueue
,您可以使用rear
来降低重新计算成本。 - 他在和中使用了更多
if
else
的逻辑分支。它可以通过处理特定条件来稍微提高性能。具体来说,它减少了空、满或单元素情况下的操作。enQueue
deQueue
+-%
- 您可以将
抽象:
他的解决方案是更加面向对象的设计。对于循环队列,哪些属性很重要?当然,front
,rear
, andstate
(empty, full or else)。所以他保留rear
并在为空时分配-1
以表示特殊状态。
好的抽象将有利于功能的可扩展性。例如,我们想添加更多的功能到MyCircularQueue
, 或许rear
并且state
在这里是有帮助的。
所有这些都是我个人的看法,可能不正确,仅供参考。:)
推荐阅读
- android - 在 Kotlin 代码中将 focusable 和 focusableInTouchMode 属性设置为 false
- input - 仅在“层节点”上方输入
- cassandra - Cassandra nodetool rebuild_index在nodetool compactionstats中卡在100%,如何刷新它并强制完成?
- c - 在这种情况下,负 0 会成为问题吗?
- ssl - 烧瓶 SSL 证书中的 OIDC SSO 验证失败
- crystal-reports - 平均水晶报表的总和
- firebase - Firebase - 如何检查项目创建者
- excel - Excel 图像参考
- r - 这种回归对吗?面板数据集的问题
- json - 将右括号更改为左括号的正则表达式