1.設計你的循環(huán)隊列
Leet Code 原題鏈接
Leet Code 原題動畫演示視頻
設計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。
你的實現(xiàn)應該支持如下操作：
- MyCircularQueue(k): 構造器，設置隊列長度為 k 。
- Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
- Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
- enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
- deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
- isEmpty(): 檢查循環(huán)隊列是否為空。
- isFull(): 檢查循環(huán)隊列是否已滿。
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 原題動畫演示視頻這一個視頻，發(fā)現(xiàn)來判斷隊空和隊滿的條件。假定我們有兩個指針，分別為頭指針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指針位置，刪除這個節(jié)點只需要移動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 # 如果成立，則代表隊滿
