Go 刷 LeetCode 系列:经典(7) 设计双端队列

设计实现双端队列。

你的实现需要支持以下操作：

MyCircularDeque(k)：构造函数,双端队列的大小为k。insertFront()：将一个元素添加到双端队列头部。如果操作成功返回 true。insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。deleteFront()：从双端队列头部删除一个元素。如果操作成功返回 true。deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。getRear()：获得双端队列的最后一个元素。如果双端队列为空，返回 -1。isEmpty()：检查双端队列是否为空。isFull()：检查双端队列是否满了。示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3circularDeque.insertLast(1);              // 返回 truecircularDeque.insertLast(2);              // 返回 truecircularDeque.insertFront(3);              // 返回 truecircularDeque.insertFront(4);              // 已经满了，返回 falsecircularDeque.getRear();          // 返回 2circularDeque.isFull();                // 返回 truecircularDeque.deleteLast();              // 返回 truecircularDeque.insertFront(4);              // 返回 truecircularDeque.getFront();        // 返回 4

提示：

所有值的范围为 [1, 1000]

操作次数的范围为 [1, 1000]

请不要使用内置的双端队列库。

解题思路：

1、定义循环变量 front 和 rear 。一直保持这个定义，到底是先赋值还是先移动指针就很容易想清楚了。

front：指向队列头部第 1 个有效数据的位置；

rear：指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置。

（说明：这个定义是依据“动态数组”的定义模仿而来。）

2、为了避免“队列为空”和“队列为满”的判别条件冲突，我们有意浪费了一个位置。

浪费一个位置是指：循环数组中任何时刻一定至少有一个位置不存放有效元素。

判别队列为空的条件是：front == rear;

判别队列为满的条件是：(rear + 1) % capacity == front;。可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满。

3、因为有循环的出现，要特别注意处理数组下标可能越界的情况。

（1）指针后移的时候，索引 + 1，要取模；

（2）指针前移的时候，为了循环到数组的末尾，需要先加上数组的长度，然后再对数组长度取模。

4，如果队列为空

插入元素的时候要注意，

（1）头部插入，rear 后移

 （2）尾部插入，rear后移

代码实现

type MyCircularDeque struct {    length int    data []int    head int    rear int}

/** Initialize your data structure here. Set the size of the deque to be k. */func Constructor(k int) MyCircularDeque {    return MyCircularDeque{        length:k+1,        data:make([]int,k+1), //空一个位置区分满和空        head:0,        rear:0,    }}/** Adds an item at the front of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) InsertFront(value int) bool {    if this.IsFull(){       return false   }   if this.IsEmpty(){       if this.rear==this.length-1{           this.rear=0       }else{           this.rear++       }       this.data[this.head]=value       return true   }   if this.head==0{       this.head=this.length-1   }else{       this.head--   }    this.data[this.head]=value   return true}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) InsertLast(value int) bool {  if this.IsFull(){      return false  }  if this.IsEmpty(){      this.data[this.rear]=value     if this.rear==this.length-1{          this.rear=0     }else{         this.rear++     }     return true  }  this.data[this.rear]=value  if this.rear==this.length-1{      this.rear=0  }else{      this.rear++  }  return true}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) DeleteFront() bool {  if this.IsEmpty(){      return false  }  if this.head==this.length-1{      this.head=0  }else{      this.head++  }  return true}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) DeleteLast() bool {    if this.IsEmpty(){        return false    }    if this.rear==0{        this.rear=this.length-1    }else{        this.rear--    }    return true}

/** Get the front item from the deque. */func (this *MyCircularDeque) GetFront() int {        if this.IsEmpty(){            return -1        }        return this.data[this.head]}

/** Get the last item from the deque. */func (this *MyCircularDeque) GetRear() int {        if this.IsEmpty(){            return -1        }        if this.rear==0{            return this.data[this.length-1]        }      return this.data[this.rear-1]}

/** Checks whether the circular deque is empty or not. */func (this *MyCircularDeque) IsEmpty() bool {    return this.head==this.rear}

/** Checks whether the circular deque is full or not. */func (this *MyCircularDeque) IsFull() bool {    return (this.rear+1)%this.length==this.head}

/** * 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(); */

推荐阅读

• Go 刷 LeetCode 系列：经典（6） 实现跳表
  

喜欢本文的朋友，欢迎关注“Go语言中文网”：

Go语言中文网启用微信学习交流群，欢迎加微信：274768166，投稿亦欢迎