专栏首页M不作声用JS手动实现一个栈和队列

用JS手动实现一个栈和队列

栈是一个「线性」的数据结构。栈最重要的特征是「只允许从一端操作数据」。栈就像一叠书,或者盘子,每次只能从最上边拿,往最上边放。

栈遵循「先进后出」的原则。栈只能从一端操作数据,这一端被称为「栈顶」,另一端被称为「栈底」。栈对数据的操作只有两种,「入栈和出栈」

看到这里我们就能知道,由于入栈和出栈都在栈顶操作,所以插入或删除一个元素的复杂度为O(1)。

特殊情况下,当栈满的时候,再添加一个元素时,需要重新分配内存且移动所有的数据,复杂度为O(n)。

实现一个栈有很多方式,这里通过使用数组实现栈,代码实现:

class Stack{
  constructor{
    this.stack = []
  }

  // 入栈
  push(item) {
    this.stack.push(item)
  }

  // 出栈
  pop() {
    this.stack.pop()
  }

  // 获取栈长度
  getCount() {
    return this.stack.length
  }

  // 查看栈顶元素
  peek() {
    return this.stack[this.getCount() - 1]
  }

  // 判断是否为空
  isEmpty() {
    return this.getCount === 0
  }
}

栈的示意图:

队列

队列也是一个线性的存储结构,特点是「只能在一端添加数据,在另一端删除数据」,遵循「先进先出」的原则。

队列「插入数据的一端叫做队尾」,插入数据的操作叫「入队」「删除数据的一端叫做队头」,删除数据的操作叫做「出队」

队列的时间复杂度和栈一样分是否已满,当队列未满时,入队复杂度是O(1),出队移除一个数据,剩下的数据前移,所以时间复杂度是O(n);当队列满了之后,需要扩容且移动数据,时间复杂度为O(n)。

队列在生活中的相似场景为,车站的进出口,只能在进站口进站,出站口出站。队列常见的使用场景是作消息队列等。

我们还是用数组来实现一个单链队列,代码实现如下:

class Queue{
  constructor() {
    this.queue = []
  }
  
  // 入队
  enQueue(item) {
    return 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
  }
    
  // 判断是否为空
  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
  }
    
  // 入队
  enQueue(item) {
    // 判断是否需要扩容, 如果需要,扩容的原来的二倍
    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 Eorror('Queue is Empty')
    }
    let r = this.queue[this.first]
    this.queue[this.first] = null
    this.first = (this.first + 1) % this.queue.length
    this.size--
    // 节省空间
    if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
      this.resize(this.getLength() / 2)
    }
    return r
  }
    
  // 获取队头
  getHeader() {
    if (this.inEmpty()) {
      throw Error('Queue is empty')
    }
    return this.queue[this.first]
  }
    
  // 获取队列的长度
  getLength() {
    return this.queue.length - 1
  }
}

创建一个循环队列并操作:

创建循环队列并操作

对比

对比

对比:

  • 栈遵循先进后出的规则;队列遵循先进先出的规则。
  • 插入数据和删除数据都可以实现常数级的时间复杂度。
  • 两种数据结构都可以在元素满了的时候扩容。

栈和队列相关的面试题

由于篇幅的问题,面试题的思路和代码还是留给以后的文章。

跟栈相关的面试题:

  • 有效的括号,一串字符串中的所有括号(){}[],都能正确闭合。
  • 用两个栈实现队列。
  • 实现一个栈,要求入栈出栈、返回最小值,且时间复杂度为O(1)。
  • 一个数组实现两个栈。

跟队列相关的面试题:

  • 用两个队列实现栈。
  • 二叉树的广度优先遍历。
  • ...

本文分享自微信公众号 - 大前端合集(fe-stack),作者:M不作声

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

原始发表时间:2020-11-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript实现继承

    使用class继承非常简单。子类使用extends关键字表明继承于哪个类,并在子类中调用super(),这相当于使用call()改变this的指向。

    不作声
  • 栈和队列的相互实现

    队列的特性是先进先出,一端添加另一端删除;而栈的特性是先进后出,且只能在一端添加或删除数据。

    不作声
  • 人生苦短,何不用vim装13

    Vim是一个非常强大的文本编辑器。基本上所有的类Unix系统都会内置vi编辑器,Vim就是从vi发展来的一个编辑器。

    不作声
  • android断点下载

    断点下载往往用在大文件的下载过程中,如传统的迅雷下载用的就是断点下载技术,说起来原理比较简单:对文件进行分片,并对分片的文件进行标记,然后分片下载,下载完成后对...

    xiangzhihong
  • 简易路由实现——(hash路由)

    前阵子逛 github 的时候,看见一篇文章 《原生JS实现hash路由》, 想着照着 vue-router 的 api,参考这篇文章实现一个可直接用于 htm...

    小皮咖
  • React源码分析与实现(二):状态、属性更新 -> setState

    setState的源码比较简单,而在执行更新的过程比较复杂。我们直接跟着源码一点一点屡清楚。

    Nealyang
  • 聊聊rocketmq的registerConsumer与unregisterConsumer

    本文主要研究一下rocketmq的registerConsumer与unregisterConsumer

    codecraft
  • RocketMQ Topic创建【源码笔记】

    Topic的创建分为自动创建和通过命令行创建两种。通过broker配置参数autoCreateTopicEnable设置。 通常可以在非生产环境开启自动创建,生...

    瓜农老梁
  • React 学习:react 表单

    版权声明:欢迎关注博主公众号:矿洞程序员 https://blog.csdn.net/qq_...

    爱明依
  • 07-图6 旅游规划 (25分)

    有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果...

    AI那点小事

扫码关注云+社区

领取腾讯云代金券