侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

前端实现栈(stack)与队列(queue)示例

前端  /  管理员 发布于 8年前   553
目录
一、栈
二、队列
三、应用场景
栈
队列
参考文献

stack_queue

# 面试官:说说你对栈、队列的理解?应用场景?

# 一、栈

栈(stack)又名堆栈,它是一种运算受限的线性表,限定仅在表尾进行插入和删除操作的线性表

表尾这一端被称为栈顶,相反地另一端被称为栈底,向栈顶插入元素被称为进栈、入栈、压栈,从栈顶删除元素又称作出栈

所以其按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据,具有记忆作用

关于栈的简单实现,如下:

class Stack {
  constructor() {
    this.items = [];
  }

  /**
   * 添加一个(或几个)新元素到栈顶
   * @param {*} element 新元素
   */
  push(element) {
    this.items.push(element)
  }

  /**
   * 移除栈顶的元素,同时返回被移除的元素
   */
  pop() {
    return this.items.pop()
  }

  /**
   * 返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)
   */
  peek() {
    return this.items[this.items.length - 1]
  }

  /**
   * 如果栈里没有任何元素就返回true,否则返回false
   */
  isEmpty() {
    return this.items.length === 0
  }

  /**
   * 移除栈里的所有元素
   */
  clear() {
    this.items = []
  }

  /**
   * 返回栈里的元素个数。这个方法和数组的length属性很类似
   */
  size() {
    return this.items.length
  }
}

关于栈的操作主要的方法如下:

  • push:入栈操作
  • pop:出栈操作

# 二、队列

跟栈十分相似,队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作

进行插入操作的端称为队尾,进行删除操作的端称为队头,当队列中没有元素时,称为空队列

在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出

简单实现一个队列的方式,如下:

class Queue {
    constructor() {
        this.list = []
        this.frontIndex = 0
        this.tailIndex = 0
    }
    enqueue(item) {
        this.list[this.tailIndex++] = item
    }
    unqueue() {
        const item  = this.list[this.frontIndex]
        this.frontIndex++        
        return item
    }
}

上述这种入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用

当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作,出该现象称为"假溢"

在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:

无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置,这种队列也就是循环队列

下面实现一个循环队列,如下:

class Queue {
    constructor(size) {
        this.size = size; // 长度需要限制, 来达到空间的利用, 代表空间的长度
        this.list = [];
        this.font = 0; // 指向首元素
        this.rear = 0;  // 指向准备插入元素的位置
    }
    enQueue() {
        if (this.isFull() == true) {
            return false
        }
        this.rear = this.rear % this.k;
        this._data[this.rear++] = value;
        return true
    }
    deQueue() {
        if(this.isEmpty()){
            return false;
        }
        this.font++;
        this.font = this.font % this.k;
        return true;
    }
    isEmpty() {
        return this.font == this.rear - 1;
    }
    isFull() {
        return this.rear % this.k == this.font;
    }
}

上述通过求余的形式代表首尾指针增1 时超出了所分配的队列空间

# 三、应用场景

# 栈

借助栈的先进后出的特性,可以简单实现一个逆序数处的功能,首先把所有元素依次入栈,然后把所有元素出栈并输出

包括编译器的在对输入的语法进行分析的时候,例如"()"、"{}"、"[]"这些成对出现的符号,借助栈的特性,凡是遇到括号的前半部分,即把这个元素入栈,凡是遇到括号的后半部分就比对栈顶元素是否该元素相匹配,如果匹配,则前半部分出栈,否则就是匹配出错

包括函数调用和递归的时候,每调用一个函数,底层都会进行入栈操作,出栈则返回函数的返回值

生活中的例子,可以把乒乓球盒比喻成一个堆栈,球一个一个放进去(入栈),最先放进去的要等其后面的全部拿出来后才能出来(出栈),这种就是典型的先进后出模型

# 队列

当我们需要按照一定的顺序来处理数据,而该数据的数据量在不断地变化的时候,则需要队列来帮助解题

队列的使用广泛应用在广度优先搜索种,例如层次遍历一个二叉树的节点值(后续将到)

生活中的例子,排队买票,排在队头的永远先处理,后面的必须等到前面的全部处理完毕再进行处理,这也是典型的先进先出模型

# 参考文献

  • https://baike.baidu.com/item/%E6%A0%88/12808149
  • https://baike.baidu.com/item/%E9%98%9F%E5%88%97/14580481

  • 上一条:
    多种排序算法浅析分享
    下一条:
    数据结构浅析
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 使用 Alpine.js 排序插件对元素进行排序(0个评论)
    • 在js中使用jszip + file-saver实现批量下载OSS文件功能示例(0个评论)
    • 在vue中实现父页面按钮显示子组件中的el-dialog效果(0个评论)
    • 使用mock-server实现模拟接口对接流程步骤(0个评论)
    • vue项目打包程序实现把项目打包成一个exe可执行程序(0个评论)
    • 近期文章
    • 智能合约Solidity学习CryptoZombie第三课:组建僵尸军队(高级Solidity理论)(0个评论)
    • 智能合约Solidity学习CryptoZombie第二课:让你的僵尸猎食(0个评论)
    • 智能合约Solidity学习CryptoZombie第一课:生成一只你的僵尸(0个评论)
    • 在go中实现一个常用的先进先出的缓存淘汰算法示例代码(0个评论)
    • 在go+gin中使用"github.com/skip2/go-qrcode"实现url转二维码功能(0个评论)
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客