设计循环队列
简单记录一下思路:
1, 队列为空状态:head = tail = -1;
2, 入队:如果入队前是空的,则将head 和 tail 都向右移一位,也就是下标为0的地方; 否则只需右移tail
3, 出队:如果出队时队列不为空且为最后一个元素(head == tail),则置head = tail = -1, 否则只需右移head
4, 取队首:只要队不为空,head指向队首元素
5, 取对尾:同理,tail指向队尾元素
6, 判空:见1
7, 判满:tail右移发现与head重合了,则没有地方放入新的元素了,此时为满
class MyCircularQueue:
def __init__(self, k: int):
self.head, self.tail = -1, -1
self.list = {}
self.size = k
def enQueue(self, value: int) -> bool:
if self.isEmpty():
self.head = 0
self.tail = 0
self.list[self.tail] = value
return True
if self.isFull():
return False
self.tail = (self.tail+1) % self.size
self.list[self.tail] = value
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
if self.head == self.tail:
self.head = -1
self.tail = -1
return True
self.head = (self.head+1) % self.size
return True
def Front(self) -> int:
if self.isEmpty():
return -1
return self.list[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.list[self.tail]
def isEmpty(self) -> bool:
if self.tail == self.head and self.head == -1:
return True
return False
def isFull(self) -> bool:
if (self.tail+1) % self.size == self.head:
return True
return False
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
又想了下,主要是要约定什么状态是队列为空的,且有两个状态比较特殊:
一个是,队列为空的时候插入的第一个元素(需要同时移动head 和 tail),此时head = tail = 0,
另一个是,队列只有一个元素且要删除的时候(需要同时置head 和 tail 为 -1)