力扣 641. 设计循环双端队列
设计实现双端队列。
实现 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。
方案一：基于数组实现，定义头尾指针用作实现循环。
type MyCircularDeque struct {
arr []int // 数组
front int // 头指针
rear int // 尾指针
cnt int // 当前元素数量
}
func Constructor(k int) MyCircularDeque {
return MyCircularDeque{
arr: make([]int, k),
front: 1, // 让头指针和尾指针错开
rear: 0,
cnt: 0,
}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
// 边界判断
if this.front--; this.front == -1 {
this.front = cap(this.arr) - 1
}
this.arr[this.front] = value
this.cnt++
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
// 边界判断
if this.rear++; this.rear == cap(this.arr) {
this.rear = 0
}
this.arr[this.rear] = value
this.cnt++
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
// 边界判断
if this.front++; this.front == cap(this.arr) {
this.front = 0
}
this.cnt--
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
// 边界判断
if this.rear--; this.rear == -1 {
this.rear = cap(this.arr) - 1
}
this.cnt--
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.arr[this.front]
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.arr[this.rear]
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.cnt == 0
}
func (this *MyCircularDeque) IsFull() bool {
return this.cnt == cap(this.arr)
}
/**
* 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 {
value int
pre *node
next *node
}
type MyCircularDeque struct {
head *node
tail *node
capacity int
size int
}
func Constructor(k int) MyCircularDeque {
head, tail := &node{}, &node{}
head.next, tail.pre = tail, head
return MyCircularDeque{
head: head,
tail: tail,
capacity: k,
size: 0,
}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
cur := &node{value: value}
cur.next = this.head.next
this.head.next.pre = cur
this.head.next = cur
cur.pre = this.head
this.size++
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
cur := &node{value: value}
this.tail.pre.next = cur
cur.pre = this.tail.pre
this.tail.pre = cur
cur.next = this.tail
this.size++
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
this.head.next.next.pre = this.head
this.head.next = this.head.next.next
this.size--
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
this.tail.pre.pre.next = this.tail
this.tail.pre = this.tail.pre.pre
this.size--
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.head.next.value
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.tail.pre.value
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularDeque) IsFull() bool {
return this.size == this.capacity
}
/**
* 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();
*/