专栏首页前端迷数据结构与前端(二)-队列

数据结构与前端(二)-队列

概念

队列一个线性结构,特点是在某一端添加数据,在另一端删除数据,遵循先进先出的原则。

实现

这里会讲解两种实现队列的方式,分别是单链队列和循环队列。

单链队列

class Queue {
  constructor() {
    this.queue = []
  }
  enQueue(item) {
    this.queue.push(item)
  }
  deQueue() {
    return this.queue.shift()
  }
  getHeader() {
    return this.queue[0]
  }
  getLength() {
    return this.queue.length
  }
  isEmpty() {
    return this.getLength() === 0
  }
}

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

循环队列

class SqQueue {
  constructor(length) {
    this.queue = new Array(length + 1)
    // 队头
    this.first = 0
    // 队尾
    this.last = 0
    // 当前队列大小
    this.size = 0
  }
  enQueue(item) {
    // 判断队尾 + 1 是否为队头
    // 如果是就代表需要扩容数组
    // % this.queue.length 是为了防止数组越界
    if (this.first === (this.last + 1) % this.queue.length) {
      this.resize(this.getLength() * 2 + 1)
    }
    this.queue[this.last] = item
    this.size++
    this.last = (this.last + 1) % this.queue.length
  }
  deQueue() {
    if (this.isEmpty()) {
      throw Error('Queue is empty')
    }
    let r = this.queue[this.first]
    this.queue[this.first] = null
    this.first = (this.first + 1) % this.queue.length
    this.size--
    // 判断当前队列大小是否过小
    // 为了保证不浪费空间,在队列空间等于总长度四分之一时
    // 且不为 2 时缩小总长度为当前的一半
    if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
      this.resize(this.getLength() / 2)
    }
    return r
  }
  getHeader() {
    if (this.isEmpty()) {
      throw Error('Queue is empty')
    }
    return this.queue[this.first]
  }
  getLength() {
    return this.queue.length - 1
  }
  isEmpty() {
    return this.first === this.last
  }
  resize(length) {
    let q = new Array(length)
    for (let i = 0; i < length; i++) {
      q[i] = this.queue[(i + this.first) % this.queue.length]
    }
    this.queue = q
    this.first = 0
    this.last = this.size
  }
}

本文分享自微信公众号 - 前端迷(love_frontend)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 双十一,教你给你女朋友不一样的表白(程序员版)

    https://ru23.com/11?name=front,这样会自动把源码中you换成女朋友的名字

    前端迷
  • webpack的运行机制详解

    webpack是现代前端开发中最火的模块打包工具,只需要通过简单的配置,便可以完成模块的加载和打包。那它是怎么做到通过对一些插件的配置,便可以轻松实现对代码的构...

    前端迷
  • Vue 源码解析:深入响应式原理

    Vue.js 最显著的功能就是响应式系统,它是一个典型的 MVVM 框架,模型(Model)只是普通的 JavaScript 对象,修改它则视图(View)会自...

    前端迷
  • JS 中 this 在各个场景下的指向

    很多时候, JS 中的 this 对于咱们的初学者很容易产生困惑不解。 this 的功能很强大,但需要一定付出才能慢慢理解它。

    前端小智@大迁世界
  • jsvascript—谜之this?

    版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

    空空云
  • Flutter基础widgets教程-AppBar篇

    青年码农
  • 微信小游戏初体验

    前言 上周【跳一跳】小游戏刷遍了朋友圈,也代表了微信小程序拥有了搭载游戏的功能(早该往这方面发展了,这才是应该有的形态嘛)。作为一个前端er,我的大刀早已经饥渴...

    极乐君
  • React Native 自定义控件之验证码和Toast

    React Native通过近两年的迭代和维护,最新版本已经到了0.45.1。 话说回来,尽管迭代的挺快,但还是有很多坑,很多基础的组件和API还是不完善。 今...

    xiangzhihong
  • 如何理解JavaScript中的this

    JavaScript中的 this 对于初学者来说是个难点,对于老手也会困惑。之前有一个小伙伴一直问我this的相关问题,所以今天抽出点时间深入的带大家理解th...

    ZEHAN

扫码关注云+社区

领取腾讯云代金券