资讯专栏INFORMATION COLUMN

JS数据结构学习:队列

OpenDigg / 2504人阅读

队列的定义

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

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

队列的创建

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

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 1) {
    for (let j = 0; j
总结

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/101627.html

相关文章

  • 我对JS队列学习

    摘要:我对队列的学习什么是队列队列是遵循先进先出原则的一组有序的项。最新添加的元素必须排在队列的末尾。队列的学习队列的操作其实是和栈是差不多的,但是队列只允许新数据在后端进行添加。这里是最小优先队列,优先值较小的元素被放置在队列最前面。 我对JS队列的学习 什么是队列 队列是遵循FIFO(先进先出)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。...

    Cristic 评论0 收藏0
  • 学习JavaScript异步、事件循环

    摘要:使用关键字来表示,在函数内部使用来表示异步。执行完了后,执行栈再次为空,事件触发线程会重复上一步操作,再取出一个消息队列中的任务,这种机制就被称为事件循环机制。 async 函数是 Generator 函数的语法糖。使用 关键字 async 来表示,在函数内部使用 await 来表示异步。想较于 Generator,Async 函数的改进在于下面四点: 内置执行器 Generato...

    nemo 评论0 收藏0
  • [js高手之路]javascript腾讯面试题学习封装一个简易的异步队列

    摘要:这道的面试题,是这样的,页面上有一个按钮,一个,点击按钮的时候,每隔秒钟向的后面追加一个一共追加个,的内容从开始技术,首先我们用闭包封装一个创建元素的函数页面上的个元素点我代码点击按钮的时候,用回调函数嵌套方式,这里我加入个,就已经快受不了 这道js的面试题,是这样的,页面上有一个按钮,一个ul,点击按钮的时候,每隔1秒钟向ul的后面追加一个li, 一共追加10个,li的内容从0开始技...

    hzx 评论0 收藏0
  • JS数据结构与算法_栈&队列

    摘要:下一篇数据结构与算法链表写在前面说明数据结构与算法系列文章的代码和示例均可在此找到原计划是把你不知道的三部全部看完的,偶然间朋友推荐了数据结构与算法的一套入门视频,学之。手头上恰好有学习数据结构与算法的书籍,便转而先把数据结构与算法学习。 下一篇:JS数据结构与算法_链表 写在前面 说明:JS数据结构与算法 系列文章的代码和示例均可在此找到 原计划是把《你不知道的Javascript》...

    AndroidTraveler 评论0 收藏0
  • Promise学习总结

    摘要:引擎线程也称为内核,负责处理脚本程序例如引擎引擎线程负责解析脚本,运行代码。对象代表一个未完成但预计将来会完成的操作。注意一旦新建就会立即执行它属于,无法取消。 写在前面: 第一遍学Promise时, 只是大概过了一遍, 感觉学的不够深入, 这一篇算是对之前的一个总结吧. Promise在ES6中也属于一个较难理解的一部分; 所以在学习一个比较难理解的知识点时, 我们可以围绕这个知识点...

    twohappy 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<