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 # 如果成立，则代表队满
