1 题目
设计实现双端队列。
你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
2 解析
需要初始一个长度为k+1的数组和两个指针，因为为了避免「队列为空」和「队列为满」的判别条件冲突，我们有意占用一个空位置；
front：指向队列头部第 1 个有效数据的位置；
rear：指向队列尾部（即最后 1 个有效数据）的 下一个位置，即下一个从队尾入队元素的位置。
（1）insertFront()
在头部插入后，指针前移一位
front = (front-1+L)%L
L表示数组长度
（2）insertLast()
在尾部插入后，指针后移一位
rear = (rear+1)%L
L表示数组长度
（3）deleteFront()
只需要指针后移一位
front = (front+1)%L
（4）deleteLast()
只需要指针前移一位
rear = (rear-1+L)%L
（5）getFront()
根据front指针取值即可
（6）getRear()
注意：
因为数组多了一个占位符，倒数第二个才是真正rear的位置，再取值
index = (rear-1+L)%L
（7）isEmpty()
判别队列为空的条件是：front == rear;
（8）isFull()
判别队列为满的条件是：(rear + 1) % capacity == front
3 python 实现
class MyCircularDeque:
def __init__(self, k: int):
self.front = 0
self.rear = 0
self.capacity = k+1
self.arr = [0]*self.capacity
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.front = (self.front-1+self.capacity)%self.capacity
self.arr[self.front] = value
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
self.arr[self.rear] = value
self.rear = (self.rear+1)%self.capacity
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front+1)%self.capacity
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.rear = (self.rear-1+self.capacity)%self.capacity
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.arr[self.front]
def getRear(self) -> int:
if self.isEmpty():
return -1
return self.arr[(self.rear-1+self.capacity)%self.capacity]
def isEmpty(self) -> bool:
return self.front ==self.rear
def isFull(self) -> bool:
return (self.rear+1)%self.capacity==self.front
