• 技术文章 >web前端 >js教程

    JavaScript中队列的详细介绍(代码示例)

    不言不言2019-02-13 09:36:09转载217

    本篇文章给大家带来的内容是关于JavaScript中队列的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

    队列的定义

    队列是遵循先进先出原则的一组有序的项,与栈的不同的是,栈不管是入栈还是出栈操作都是在栈顶操作,队列则是在队尾添加元素,队顶移除,用一个图来表示大概是这样事的:

    990741674-5c635e164859b_articlex.png

    用一个更形象的例子就是:排队服务,总是先排队的人会先接受服务,当然不考虑插队的情况

    队列的创建

    与栈的创建类似,首先创建一个表示队列的函数,然后定义一个数组用来保存队列里的元素:

    function Queue() {
      let items = []
    }

    创建队列后需要为其定义一些方法,一般来说队列包含以下方法:

    具体实现:

    function Queue() {
      let items = []
      // 向队列的尾部添加新元素
      this.enqueue = function (element) {
        items.push(element)
      }
      // 遵循先进先出原则,从队列的头部移除元素
      this.dequeue = function () {
        return items.shift()
      }
      // 返回队列最前面的项
      this.front = function () {
        return items[0]
      }
      // 返回队列是否为空
      this.isEmpty = function () {
        return items.length === 0
      }
      // 返回队列的长度
      this.size = function () {
        return items.length
      }
      // 打印队列,方便观察
      this.print = function () {
        console.log(items.toString())
      }
    }

    队列的使用

    接下来让我们看看队列的使用:

    let queue = new Queue()
    queue.enqueue('a')
    queue.enqueue('b')
    queue.enqueue('c')
    queue.dequeue()
    queue.print()

    首先向队列中添加三个元素:a,b,c,然后移除队列中的一个元素,最后打印现有队列,让我们一起图解这个过程:

    349148906-5c635e1654bb9_articlex.png

    es6实现Queue

    和实现Stack类一样,也可以用es6的class语法实现Queue类,用WeakMap保存私用属性items,并用闭包返回Queue类,来看具体实现:

    let Queue = (function () {
      let items = new WeakMap
      class Queue {
        constructor () {
          items.set(this, [])
        }
        enqueue (element) {
          let q = items.get(this)
          q.push(element)
        }
        dequeue () {
          let q = items.get(this)
          return q.shift()
        }
        front () {
          let q = items.get(this)
          return q[0]
        }
        isEmpty () {
          let q = items.get(this)
          return q.length === 0
        }
        size () {
          let q = items.get(this)
          return q.length
        }
        print () {
          let q = items.get(this)
          console.log(q.toString())
        }
      }
      return Queue
    })()
    let queue = new Queue()
    queue.enqueue('a')
    queue.enqueue('b')
    queue.enqueue('c')
    queue.dequeue()
    queue.print()

    优先队列

    优先队列顾名思义就是:队列中的每个元素都会有各自的优先级,在插入的时候会根据优先级的高低顺序进行插入操作,和前面队列实现有点不太一样的地方,队列中的元素多了有先级的属性,下面来看具体代码:

    function PriorityQueue() {
      let items = []
      // 队列元素,多定义一个优先级变量
      function QueueElement(element, priority) {
        this.element = element
        this.priority = priority
      }
      this.enqueue = function (element, priority) {
        let queueElement = new QueueElement(element, priority)
        let added = false
        for (let i = 0; i < items.length; i++) {
          //数字越小优先级越高
          if (queueElement.priority < items[i].priority) {
            items.splice(i, 0, queueElement)
            added = true
            break
          }
        }
        if (!added) {
          items.push(queueElement)
        }
      }
      this.dequeue = function () {
        return items.shift()
      }
      this.front = function () {
        return items[0]
      }
      this.isEmpty = function () {
        return items.length === 0
      }
      this.size = function () {
        return items.length
      }
      this.print = function () {
        for (let i = 0; i < items.length; i++) {
          console.log(`${items[i].priority}-${items[i].element}`)
        }
      }
    }
    let priorityQueue = new PriorityQueue()
    priorityQueue.enqueue('a', 3)
    priorityQueue.enqueue('b', 2)
    priorityQueue.enqueue('c', 1)
    priorityQueue.dequeue()
    priorityQueue.print()

    入队时如果队列为空直接加入队列,否则进行比较,priority小的优先级高,优先级越高放在队列的越前面,下面用一个图来看调用过程:

    1995639241-5c635e16641e9_articlex.png

    循环队列

    循环队列顾名思义就是:给定一个数,然后迭代队列,从队列开头移除一项,然后再将其加到队列末尾,当循环到给定数字时跳出循环,从队首移除一项,直至剩余一个元素,下面来看具体代码:

    unction Queue() {
      let items = []
      this.enqueue = function (element) {
        items.push(element)
      }
      this.dequeue = function () {
        return items.shift()
      }
      this.front = function () {
        return items[0]
      }
      this.isEmpty = function () {
        return items.length === 0
      }
      this.size = function () {
        return items.length
      }
      this.print = function () {
        console.log(items.toString())
      }
    }
    function loopQueue(list, num) {
      let queue = new Queue()
      for (let i = 0; i<list.length; i++) {
        queue.enqueue(list[i])
      }
      while (queue.size() > 1) {
        for (let j = 0; j<num; j++) {
          queue.enqueue(queue.dequeue())
        }
        let out = queue.dequeue()
        console.log('出队列:' + out)
      }
      return queue.dequeue()
    }
    console.log('last:' + loopQueue(['a', 'b', 'c', 'd', 'e'], 3))

    以上就是JavaScript中队列的详细介绍(代码示例)的详细内容,更多请关注php中文网其它相关文章!

    第八期线上培训班
    专题推荐:数据结构 javascript
    上一篇:javascript中的数据类型有哪些 下一篇:JavaScrip数据结构之数组的相关操作介绍(附示例)

    相关文章推荐

    • JavaScript根据CSS的Media Queries来判断浏览设备的方法_javascript技巧• JS实现登录页面记住密码和enter键登录方法推荐_javascript技巧• js实现的简单图片浮动效果完整实例_javascript技巧• Bootstrap Fileinput文件上传组件用法详解_javascript技巧

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网