JavaScript数据结构《队列》

saucxs 发布于2019-08-21 16:47 / 488人阅读

摘要：在队列的这种数据结构里面，新增的元素都在尾部，要移除的元素都在顶部。代码实现下面用代码来实现队列这个数据结构，同样都采用的语法，我们先定义一个类来表示队列，然后在这个类的基础上定义一下方法来模拟队列的行为。

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

队列是遵循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请求，定时器等。

GPU云服务器云服务器 javascript实现队列链表数据结构队列 java队列处理数据 javascript数据结构

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

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

学习javascript数据结构(一)——栈和队列

摘要：原文地址学习数据结构一栈和队列博主博客地址的个人博客几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。他们就是栈和队列。我们称作栈顶，而另一端我们称作栈底。移除栈顶的元素，同时返回被移除元素。前言只要你不计较得失，人生还有什么不能想法子克服的。原文地址：学习javascript数据结构(一)——栈和队列博主博客地址：Damonare的个人博客几乎所有的编程...

doodlewind 2019-08-21 14:42 评论0 收藏0
【Javascript】探究javascript中的堆/栈/任务队列与并发模型 event loop

摘要：而函数调用结束返回时，运行时会将栈顶的调用结构弹出。并发模型与引擎是单线程的，它的并发模型基于事件循环当线程中的同步任务执行完，执行栈为空时，则从任务队列中取出异步任务进行处理。在当前的微任务没有执行完成时，是不会执行下一个宏任务的。堆/栈/队列在javascript中，存在调用栈 (call stack)和内存堆(memory heap) ,程序中函数依次进入栈中等待执行,若执行...

desdik 2019-08-26 13:47 评论0 收藏0
Javascript系列之javascript机制

摘要：异步任务必须指定回调函数，当异步任务从任务队列回到执行栈，回调函数就会执行。事件循环主线程从任务队列中读取事件，这个过程是循环不断的，所以整个的这种运行机制又称为。事件循环事件循环是指主线程重复从消息队列中取消息执行的过程。参考链接：这一次，彻底弄懂 JavaScript 执行机制https://zhuanlan.zhihu.com/p/...从浏览器多进程到JS单线程，JS运行机制...

13651657101 2019-08-22 15:50 评论0 收藏0
泡杯茶，我们坐下聊聊Javascript的事件环

摘要：是怎么执行的一开始先简单聊了聊基本的数据结构，它和我们现在说的事件环有什么关系么当然有，首先要明确的一点是，代码的执行全都在栈里，不论是同步代码还是异步代码，这个一定要清楚。栈和队列在计算机内存中存取数据，基本的数据结构分为栈和队列。栈（Stack）是一种后进先出的数据结构，注意，有时候也管栈叫做堆栈，但是堆又是另一种复杂的数据结构，它和栈完全是两码事。栈的特点是操作只在一端进行...

douzifly 2019-08-23 11:50 评论0 收藏0
JavaScript队列数据结构详解

　　今天我们讲讲JavaScript队列数据结构详解。什么是队列？　　队列是一种先进先出的数据结构，队列有两种操作：插入和删除；入队和出队。简单来说就是允许插入的一端称为队尾、允许删除的一端称为队头；　　如下图展示了栈这个数据结构：　　JavaScript中的队列　　要知道JavaScript中没有有关队列的数据模型，因此我们需要通过数组进行模拟，当数组中提供的push()和shift()选...

3403771864 2022-09-21 22:28 评论0 收藏0