JavaScript 设计循环队列

作者: 阿畅_ | 来源:发表于2020-05-10 22:16 被阅读0次

    队列

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

    • 题目:

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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
    

    相关文章

      网友评论

        本文标题:JavaScript 设计循环队列

        本文链接:https://www.haomeiwen.com/subject/tuusnhtx.html