622.设计循环队列

题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

示例 1：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

解法一原生

使用原生的数组和方法实现循环队列，只关注功能实现

思路是利用原生数组已有队列的特性，使用 push (入队) 和 shift (出队) 很容易实现，再判断下数组的长度即可。和题目的描述不一致但能实现全部操作先实现一遍吧。

代码实现

/**
 * @param {number} k
 */
var MyCircularQueue = function (k) {
  this.k = k // 队列长度
  this.queue = [] // 队列
}

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) {
    return false
  } else {
    this.queue.push(value)
    return true
  }
}

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) {
    return false
  } else {
    this.queue.shift()
    return true
  }
}

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) {
    return -1
  }
  return this.queue[0]
}

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) {
    return -1
  }
  return this.queue[this.queue.length - 1]
}

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function () {
  return this.queue.length === 0
}

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

解法二模拟

在一个固定长度的队列里，入队时添加一个元素，出队时队首往后移一位，如果假溢出那么重头开始存储。

一个固定长度循环队列的特性，会使用之前已经空闲的空间，如上图 3 所示，当已经到达队列最尾部的时候，前面的还有空间可以使用达到一个循环的效果。

1. 在 js 中可以使用 new Array(k)，元素为 empty 长度为 k 的一个数组。
2. 初始的时候队首和队尾的索引都在开头 0 的位置。
3. 当有元素入队时候，元素是添加在队尾的位置的，之后再把队尾往后移动一位。
4. 当有元素出队的时候，把队首往后移动一位那么队首之前的元素已经空出来了无用了。
5. 当入队和出队的时候要记录现有元素的个数，入队加 1 、出队减 1。用于判断是满队(count = k)还是空队(count = 0)。
6. 假溢出问题解决。虽然队首和队尾一直往后移动索引会超过队列的长度，可以利用 取余 让索引重头开始。

代码实现

/**
 * @param {number} k
 */
var MyCircularQueue = function (k) {
  this.k = k // 队列长度
  this.queue = new Array(k) // 指定长度的队列
  this.head = 0 // 队首索引
  this.tail = 0 // 队尾索引
  this.count = 0 // 已入队的元素数量
}

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) {
    return false
  }

  // 往队尾增加一个元素
  this.queue[this.tail] = value
  // 让队尾往后移动一位。(取余操作时为了当假溢出的时候重头开始，达到循环效果)
  this.tail = (this.tail + 1) % this.k
  // 队列里的元素数量加一
  this.count += 1

  return true
}

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) {
    return false
  }

  // 让队首往后移动一位，代表出队了一个。
  this.head = (this.head + 1) % this.k
  // 队列里的元素数量减一
  this.count -= 1

  return true
}

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) {
    return -1
  }

  return this.queue[this.head]
}

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) {
    return -1
  }

  // 队首的索引 + 元素个数 - 1 = 队尾的索引
  return this.queue[(this.head + this.count - 1) % this.k]
}

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

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function () {
  return this.count === this.k
}

// ===================================================================
// ========================== @test ==================================
// ===================================================================
let circularQueue = new MyCircularQueue(3) // 设置长度为 3
console.log(circularQueue.enQueue(1)) // 返回 true
console.log(circularQueue.enQueue(2)) // 返回 true
console.log(circularQueue.enQueue(3)) // 返回 true
console.log(circularQueue.enQueue(4)) // 返回 false，队列已满
console.log(circularQueue.Rear()) // 返回 3
console.log(circularQueue.isFull()) // 返回 true
console.log(circularQueue.deQueue()) // 返回 true
console.log(circularQueue.enQueue(4)) // 返回 true
console.log(circularQueue.Rear()) // 返回 4

本文参与

本文正在参与「掘金 2021 春招闯关活动」, 点击查看活动详情。