【2022-08-15每日一题】641. 设计循环双端队列
2022-08-15
3分钟阅读时长
2022-08-15每日一题：641. 设计循环双端队列
- 难度：Medium
- 标签：设计 、 队列 、 数组 、 链表
设计实现双端队列。
实现 MyCircularDeque 类:
MyCircularDeque(int k)：构造函数,双端队列最大为k。boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回true，否则返回false。boolean insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回true，否则返回false。boolean deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回true，否则返回false。boolean deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回true，否则返回false。int getFront())：从双端队列头部获得一个元素。如果双端队列为空，返回-1。int getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回-1。boolean isEmpty()：若双端队列为空，则返回true，否则返回false。boolean isFull()：若双端队列满了，则返回true，否则返回false。
示例 1：
输入 ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] 输出 [null, true, true, true, false, 2, true, true, true, 4] 解释 MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3 circularDeque.insertLast(1); // 返回 true circularDeque.insertLast(2); // 返回 true circularDeque.insertFront(3); // 返回 true circularDeque.insertFront(4); // 已经满了，返回 false circularDeque.getRear(); // 返回 2 circularDeque.isFull(); // 返回 true circularDeque.deleteLast(); // 返回 true circularDeque.insertFront(4); // 返回 true circularDeque.getFront(); // 返回 4
提示：
1 <= k <= 10000 <= value <= 1000insertFront,insertLast,deleteFront,deleteLast,getFront,getRear,isEmpty,isFull调用次数不大于2000次
type MyCircularDeque struct {
queue []int
front, last, cap int
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{
queue: make([]int, k+1),
cap: k+1,
}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
this.front = (this.front - 1 + this.cap) % this.cap
this.queue[this.front] = value
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
this.queue[this.last] = value
this.last = (this.last + 1) % this.cap
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
this.front = (this.front + 1) % this.cap
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
this.last = (this.last - 1 + this.cap) % this.cap
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.queue[this.front]
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.queue[(this.last - 1 + this.cap)%this.cap]
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.front == this.last
}
func (this *MyCircularDeque) IsFull() bool {
return this.front == (this.last + 1) % this.cap
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.InsertFront(value);
* param_2 := obj.InsertLast(value);
* param_3 := obj.DeleteFront();
* param_4 := obj.DeleteLast();
* param_5 := obj.GetFront();
* param_6 := obj.GetRear();
* param_7 := obj.IsEmpty();
* param_8 := obj.IsFull();
*/
方法二：链表
type node struct {
prev, next *node
val int
}
type MyCircularDeque struct {
head, tail *node
capacity, size int
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{capacity: k}
}
func (q *MyCircularDeque) InsertFront(value int) bool {
if q.IsFull() {
return false
}
node := &node{val: value}
if q.IsEmpty() {
q.head = node
q.tail = node
} else {
node.next = q.head
q.head.prev = node
q.head = node
}
q.size++
return true
}
func (q *MyCircularDeque) InsertLast(value int) bool {
if q.IsFull() {
return false
}
node := &node{val: value}
if q.IsEmpty() {
q.head = node
q.tail = node
} else {
q.tail.next = node
node.prev = q.tail
q.tail = node
}
q.size++
return true
}
func (q *MyCircularDeque) DeleteFront() bool {
if q.IsEmpty() {
return false
}
q.head = q.head.next
if q.head != nil {
q.head.prev = nil
}
q.size--
return true
}
func (q *MyCircularDeque) DeleteLast() bool {
if q.IsEmpty() {
return false
}
q.tail = q.tail.prev
if q.tail != nil {
q.tail.next = nil
}
q.size--
return true
}
func (q MyCircularDeque) GetFront() int {
if q.IsEmpty() {
return -1
}
return q.head.val
}
func (q MyCircularDeque) GetRear() int {
if q.IsEmpty() {
return -1
}
return q.tail.val
}
func (q MyCircularDeque) IsEmpty() bool {
return q.size == 0
}
func (q MyCircularDeque) IsFull() bool {
return q.size == q.capacity
}