LeetCode 641 设计循环双端队列
1 题目描述
请设计对双端队列的实现。
实现需支持如下操作：
a）MyCircularDeque(k): 构造器，设置双端队列的容量
b）insertFront(): 在头部插入元素，若操作成功则返回true
c）insertLast(): 在尾部插入元素，若操作成功则返回true
d）deleteFront(): 删除头部元素，若操作成功则返回true
e）deleteLast(): 删除尾部元素，若操作成功则返回true
f）getFront(): 查询头部元素，若队列为空返回-1
g）getRear(): 查询尾部元素，若队列为空返回-1
h）isEmpty(): 队列是否为空
i）isFull(): 队列是否已满
例子：
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4
注：
a）所有元素值位于区间[0,1000]；
b）所有操作个数位于区间[1,1000]；
c）请勿直接使用内置双端队列实现。
题目出处：LeetCode
2 简版解决思路及代码
使用内置slice数据结构，取头或取尾、在头插入，在尾插入都有现成函数，实现起来简单，但性能不佳。
type MyCircularDeque struct {
stores []int
cap int
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{cap: k}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.cap == len(this.stores) {
return false
}
this.stores = append([]int{value}, this.stores...)
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.cap == len(this.stores) {
return false
}
this.stores = append(this.stores, value)
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if 0 == len(this.stores) {
return false
}
this.stores = this.stores[1:]
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if 0 == len(this.stores) {
return false
}
this.stores = this.stores[:len(this.stores)-1]
return true
}
func (this *MyCircularDeque) GetFront() int {
if 0 == len(this.stores) {
return -1
}
return this.stores[0]
}
func (this *MyCircularDeque) GetRear() int {
if 0 == len(this.stores) {
return -1
}
return this.stores[len(this.stores)-1]
}
func (this *MyCircularDeque) IsEmpty() bool {
return 0 == len(this.stores)
}
func (this *MyCircularDeque) IsFull() bool {
return this.cap == len(this.stores)
}
3 优化版解决思路及代码
因插入仅在头部或尾部，查询也仅在头部或尾部，所以使用双向链表数据结构实现较为合适。
双端队列只要记录链表的头指针和尾指针即可，这样查询或者插入非常效率。
https://github.com/leileiluoluo/
type node struct {
val int
pre *node
next *node
}
type MyCircularDeque struct {
front *node
rear *node
len int
cap int
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{&node{}, &node{}, 0, k}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.cap == this.len {
return false
}
if 0 == this.len {
this.front = &node{val: value}
this.rear = this.front
} else {
front := this.front
this.front = &node{val: value, next: front}
front.pre = this.front
}
this.len++
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.cap == this.len {
return false
}
if 0 == this.len {
this.rear = &node{val: value}
this.front = this.rear
} else {
rear := this.rear
this.rear = &node{val: value, pre: rear}
rear.next = this.rear
}
this.len++
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if 0 == this.len {
return false
}
next := this.front.next
if nil == next {
this.front = nil
this.rear = nil
} else {
this.front = this.front.next
this.front.pre = nil
}
this.len--
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if 0 == this.len {
return false
}
pre := this.rear.pre
if nil == pre {
this.rear = nil
this.front = nil
} else {
this.rear = this.rear.pre
this.rear.next = nil
}
this.len--
return true
}
func (this *MyCircularDeque) GetFront() int {
if 0 == this.len {
return -1
}
return this.front.val
}
func (this *MyCircularDeque) GetRear() int {
if 0 == this.len {
return -1
}
return this.rear.val
}
func (this *MyCircularDeque) IsEmpty() bool {
return 0 == this.len
}
func (this *MyCircularDeque) IsFull() bool {
return this.cap == this.len
}
版权声明：该博客文章由作者通过「知识共享署名 4.0 许可证」进行授权，转载须注明文章原始链接。
相关文章
评论
正在加载评论......