JavaScript数据结构《队列》

发布时间:2019-08-19 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了JavaScript数据结构《队列》脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

队列和栈非常的类似,但是他们采用了不同的原则,栈采用的是后进先出,队列正好相反,采用的是先进先出的原则。队列的定义如下

队列是遵循FIFO(先进先出)原则的有序集合,新添加的元素保存在队列的尾部,要移除的元素保存在队列的顶部。在队列的这种数据结构里面,新增的元素都在尾部,要移除的元素都在顶部。

举一个生活中的例子,在我们平时去肯德基吃饭时肯定要排队,这条队伍就可以看做是一个队列,排在队伍前面的就是队列的顶部,队伍后面的就是队列的尾部,后来的人都要排在队伍的后面(队列的尾部),这就符合了队列先进先出的原则了(先排队的可以先点餐)。

代码实现

下面用代码来实现队列这个数据结构,同样都采用ES6的语法,我们先定义一个类Queue来表示队列,然后在这个类的基础上定义一下方法来模拟队列的行为。

class Queue {

  constructor() {
    // 定义一个数组来保存队列里面的元素
    this.ITems = []
  }

  // 在队列尾部添加一个或者多个元素
  enqueue(element) { }
    
  // 移除队列顶部的元素,并返回被移除的元素
  dequeue() { }
    
  // 清空队列
  remove() { }
    
  // 返回队列顶部的元素,不对队列本身做修改
  front() { }
    
  // 判断队列是否为空
  iSEMpty() { }
    
  // 返回队列里面元素的个数
  length() { }
}

这样我们就定义好一个基类了,下面来分别实现队列的行为方法

enqueue

第一个要实现的就是enqueue方法,这个方法接收一个参数,然后把该参数插入队列的尾部,因为这里我们是用数组来存储队列的元素的,所以可以用数组的push方法来实现该操作,代码如下

 enqueue (element) {
   this.items.push(element)
 }

dequeue

下面接着实现dequeue方法,这个方法会从队列里面移除项,由于队列遵循的是先进先出的原则,所以我们要移除的元素就是队列顶部的元素,同样因为这里我们是用数组来存储队列的元素的,所以可以用数组的shift方法来实现该操作。代码如下

dequeue () {
    return this.items.shift()
}

remove

接着来实现remove方法,改方法会移除队列里面所有的项,同理我们把保存队列元素的数组置空就好了,代码如下

remove () {
    this.items = []
}

front

上面的方法都是对队列本身有修改的,接下来要实现的方法front做的是只读操作,front方法会返回队列顶部的元素但不对队列本身进行修改,代码实现如下

front () {
    return this.items[0]
}

isEmpty

isEmpty方法判断队列是否为空,也就是保存队列的数组的长度是否等于0,代码实现如下

isEmpty () {
    return this.items.length === 0
}

length

最后一个方法返回队列的长度,同理就是返回保存队列元素的数组的长度就好了,代码如下

length () {
    return this.item.length
}

这里和栈一样添加一个辅助方法PRint来打印栈里面的元素,方便我们观察调试,这个方法和队列的行为无关,只是一个辅助方法

print(){
    this.items.foreach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
}

这样队列的方法就全部写好了,最后完整Queue类的代码如下

class Queue {

  constructor() {
    // 定义一个数组来保存队列里面的元素
    this.items = []
  }

  // 在队列尾部添加一个或者多个元素
  enqueue (element) {
      this.items.push(element)
  }
  // 移除队列顶部的元素,并返回被移除的元素
  dequeue() { 
      return this.items.shift()
  }
  // 清空队列
  remove() {
      this.items = []
  }
  // 返回队列顶部的元素,不对队列本身做修改
  front() { 
      return this.items[0]
  }
  // 判断队列是否为空
  isEmpty() { 
      return this.items.length === 0
  }
  // 返回队列里面元素的个数
  length() { 
      return this.item.length
  }
    
  print(){
      this.items.forEach((item, index) => {
          console.log(`${index+1}:${item}`)
      })
  }
}

使用Queue类

要使用这个类我们得先实例化它

const queue = new Queue()

queue.isEmpty() // true

queue.push('我是队列的第一个元素')
queue.push('我是队列的第二个元素')

queue.print() // 1: 我是队列的第一个元素 2:我是队列的第二个元素

queue.dequeue() // 我是队列的第一个元素

queue.front() // 我是队列的第二个元素

queue.length() // 1

queue.isEmpty() // false

queue.remove() // 这时队列里面已经没有元素了

queue.isEmpty() // true

总结

队列这种数据结构运用的是非常的广泛的,就比如javaScript的运行机制,我们都知道javaScript是单线程的,是不能同时执行多个任务,但是单线程就意味着所有任务需要排队。但是在javaScript里面,很多时候阻止线程运行的很慢的是网络IO之类,这时候CPU是空闲的,这样就会造成资的浪费。所以javaScript在主线程之外实现了一个任务队列,像IO之类比较慢的操作暂时都会挂在任务队列上,这样不会影响到主线程上任务的执行,等到IO的响应回来后再回到主线程上来执行挂起的任务。例子就是我们的Ajax请求,定时器等。

脚本宝典总结

以上是脚本宝典为你收集整理的JavaScript数据结构《队列》全部内容,希望文章能够帮你解决JavaScript数据结构《队列》所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。