中等

问题描述

设计实现双端队列。

实现 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 <= 1000
• 0 <= value <= 1000
• insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

数组

初始化时，创建一个长度为 $k$ 的数组并使用个$-1$填充，使用变量 $cnt$ 表示当前队列中元素的个数，变量 $head$ 和 $tail$ 表示当前队首和队尾的元素下标：

• 从队首插入元素时，若当前队列已满，则直接返回 $false$，否则判断当前 $head$ 所指元素是否为 $-1$，若是，则可以直接插入，否则应该循环左移一个下标后插入。若插入前队列为空，则此时队尾指针应对也指向当前元素，然后统计值 $+1$
• 从队尾插入元素时，若当前队列已满，则直接返回 $false$，否则判断当前 $tail$ 所指元素是否为 $-1$，若是，则可以直接插入，否则应该循环右移一个下标后插入。若插入前队列为空，则此时队首指针应对也指向当前元素，然后统计值 $+1$
• 删除队首元素时，若当前队列为空，则直接返回 $false$，否则当前 $head$ 所指元素重置为 $-1$，$head$ 指针循环右移一位，统计值 $-1$
• 删除队尾元素时，若当前队列为空，则直接返回 $false$，否则当前 $tail$ 所指元素重置为 $-1$，$tail$ 指针循环左移一位，统计值 $-1$
• 获取队首元素时，直接返回 $head$ 所指元素
• 获取队尾元素时，直接返回 $tail$ 所指元素
• 判断队列是否为空时，判断 $cnt$ 是否为 $0$
• 判断队列是否已满时，判断 $cnt$ 是否为队列长度

/**
 * @param {number} k
 */
var MyCircularDeque = function (k) {
  this.queue = new Array(k).fill(-1)
  this.cnt = 0
  this.head = 0
  this.tail = 0
}

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function (value) {
  if (this.isFull()) return false
  if (this.queue[this.head] !== -1) {
    this.head = (this.head - 1 + this.k) % this.k
  }
  this.queue[this.head] = value
  if (this.isEmpty()) this.tail = this.head
  this.cnt++
  return true
}

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function (value) {
  if (this.isFull()) return false
  if (this.queue[this.tail] !== -1) {
    this.tail = (this.tail + 1 + this.k) % this.k
  }
  this.queue[this.tail] = value
  if (this.isEmpty()) this.head = this.tail
  this.cnt++
  return true
}

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function () {
  if (this.isEmpty()) return false
  this.queue[this.head] = -1
  this.head = (this.head + 1 + this.k) % this.k
  this.cnt--
  return true
}

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function () {
  if (this.isEmpty()) return false
  this.queue[this.tail] = -1
  this.tail = (this.tail - 1 + this.k) % this.k
  this.cnt--
  return true
}

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function () {
  return this.queue[this.head]
}

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function () {
  return this.queue[this.tail]
}

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function () {
  return this.cnt === 0
}

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function () {
  return this.cnt === this.queue.length
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */

• 时间复杂度：除在初始化函数中构造容器复杂度为 $O(k)$ 以外，其余操作复杂度均为 $O(1)$
• 空间复杂度：$O(k)$