JS数据结构学习:队列

2019-02-13 admin

队列的定义

队列是遵循先进先出原则的一组有序的项,与栈的不同的是,栈不管是入栈还是出栈操作都是在栈顶操作,队列则是在队尾添加元素,队顶移除,用一个图来表示大概是这样事的: 用一个更形象的例子就是:排队服务,总是先排队的人会先接受服务,当然不考虑插队的情况

队列的创建

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

function Queue() {
  let items = []
}

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

  • enqueue(element):向队的尾部添加一个新的项
  • dequeue():移除队列第一项,并返回被移除的元素
  • front():返回队列第一项,队列不做任何变动
  • isEmpty():如果队列中没有任何元素返回true,否则返回false
  • size():返回队列包含的元素个数

具体实现:

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,然后移除队列中的一个元素,最后打印现有队列,让我们一起图解这个过程:

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小的优先级高,优先级越高放在队列的越前面,下面用一个图来看调用过程:

循环队列

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

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))

总结

这篇文章主要对队列做了简单介绍,对队列以及相关应用做了简单实现。如果有错误或不严谨的地方,欢迎批评指正,如果喜欢,欢迎点赞。

[转载]原文链接:https://segmentfault.com/a/1190000018132297

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-53619.html

文章标题:JS数据结构学习:队列

相关文章
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot;&gt; &lt;head&gt; ...
2017-03-13
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
three.js实现围绕某物体旋转
话不多说,请看代码: 可以拖动右上角观察变化 &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot; style=&quot;width: 100%; height:100%;&quot;&gt...
2017-02-17
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
NodeJS参考手册pdf版
下载地址:Nodejs参考手册PDF版下载 ...
2015-11-12
Node.js学习(1)----HTTP服务器与客户端
Node.js 标准库提供了 http 模块,其中封装了一个高效的 HTTP 服务器和一个简易的HTTP 客户端。http.Server 是一个基于事件的 HTTP 服务器,它的核心由 Node.js 下层 C++部分实现,而接口由 Jav...
2015-11-12
Riot.js:不足1KB的MVP客户端框架
Riot.js是一款MVP(模型-视图-呈现)开源客户端框架,其最大的特点就是体积非常小,不足1KB,虽然体积小,但它可以帮助用户构建大规模的Web应用程序。 Riot.js是由Moot公司开发,目前最新版本为v0.9.2,遵循MIT开源许...
2016-03-11
使用jspdf生成pdf报表
由于前台html已经动态生成报表,而且,前台有一个功能,一个date range组件,当你拖动的时候,报表会在不提交到后台的情况下动态变化。 因此需要用到js生成生报表: 用到的组件: jquery.js jspdf.js canvg.js...
2017-03-25
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
jsdom 中文文档(纯翻译)
jsdom是一个纯粹由 javascript 实现的一系列 web标准,特别是 WHATWG 组织制定的DOM和 HTML 标准,用于在 nodejs 中使用。大体上来说,该项目的目标是模拟足够的Web浏览器子集,以便用于测试和挖掘真实世界...
2018-05-14
回到顶部