JavaScript 设计循环队列

队列

• 是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。（特点：先进先出）

• 题目：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

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

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

• 示例：

rcularQueue 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

来源：力扣（LeetCode）

• 直接上代码

ES5 版

 function MyCircularQueue (k) {
      // 保存长度 为 k 的数据结构
      this.list = Array(k)
      // 对首的指针
      this.front = 0
      // 队尾的指针
      this.rear = 0
      // 对列的长度
      this.max = k
    }

    // 向循环队列插入一个元素。如果成功插入则返回真。否则返回 false
    MyCircularQueue.prototype.enQueue = function(value) {
      if (this.isFull()) {
        return false
      } else {
        this.list[this.rear] = value
        // 把指针 + 1， % 因为指针到末尾后，要在重新指回到第一个
        this.rear = (this.rear + 1) % this.max
        return true
      }
    }
    // deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    MyCircularQueue.prototype.deQueue = function() {
      // 取出第一个元素
      const f = this.list[this.front]
      // 删除元素
      this.list[this.front] = ''
      // 同样的道理 front 的指针 + 1
      this.front = (this.front + 1) % this.max
      // 返回元素
      return !!f
    }

    // Front: 从队首获取元素。如果队列为空，返回 -1 。
    MyCircularQueue.prototype.Front = function() {
      return this.list[this.front] ? this.list[this.front] : -1
    }

    // Rear: 获取队尾元素。如果队列为空，返回 -1 。
    MyCircularQueue.prototype.Rear = function() {
      if (this.isEmpty()) {
        return -1
      } else {
        // 获取 index
        const rear = this.rear - 1
        // 判断当前的 index
        const cur = rear < 0 ? this.max - 1 : rear
        return this.list[cur]
      }
    }

    // isEmpty(): 检查循环队列是否为空。
    MyCircularQueue.prototype.isEmpty = function() {
      // 两个指针相同，并且元素为空
      return this.front === this.rear && !this.list[this.front]
    }
    // isFull(): 检查循环队列是否已满。
    MyCircularQueue.prototype.isFull = function() {
      return this.front === this.rear && !!this.list[this.front]
    }
    const circularQueue = new MyCircularQueue1(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(4)) // 3
    console.log(circularQueue.Front(4)) // true
    console.log(circularQueue.deQueue(4)) // true
    console.log(circularQueue.enQueue(4)) // true
    console.log(circularQueue.Rear(4)) // 4

ES6 版

class MyCircularQueue1 {
      constructor(k) {
        this.list = Array(k)
        this.front = 0
        this.rear = 0
        this.max = k
      }

      enQueue(value) {
        if (this.isFull()) {
        return false
        } else {
          this.list[this.rear] = value
          this.rear = (this.rear + 1) % this.max
          return true
        }
      }

      deQueue() {
        const f = this.list[this.front]
        this.list[this.front] = ''
        this.front = (this.front + 1) % this.max
        return !!f
      }

      Front() {
        return this.list[this.front] ? this.list[this.front] : -1
      }

      Rear() {
        if (this.isEmpty()) {
          return -1
        } else {
          // 获取 index
          const rear = this.rear - 1
          // 判断当前的 index
          const cur = rear < 0 ? this.max - 1 : rear
          return this.list[cur]
        }
      }

      isEmpty() {
        return this.front === this.rear && !this.list[this.front]
      }

      isFull() {
        return this.front === this.rear && !!this.list[this.front]
      }
    }
    const circularQueue1 = new MyCircularQueue1(3)
    console.log(circularQueue1.enQueue(1)) // true
    console.log(circularQueue1.enQueue(2)) // true
    console.log(circularQueue1.enQueue(3)) // true
    console.log(circularQueue1.enQueue(4)) // false
    console.log(circularQueue1.Rear(4)) // 3
    console.log(circularQueue1.Front(4)) // true
    console.log(circularQueue1.deQueue(4)) // true
    console.log(circularQueue1.enQueue(4)) // true
    console.log(circularQueue1.Rear(4)) // 4

• 查看更多内容