说说你对栈、队列的理解?应用场景?

在这里插入图片描述

一、栈

栈(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

如果对您有所帮助,欢迎您点个关注,我会定时更新技术文档,大家一起讨论学习,一起进步。
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/536968.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Python实践应用】使用Python加载栅格数据

下面的代码实现的是加载伊宁市NDVI数据,首先进行相关的python包的导入,然后定义和读取我们需要加载的数据,这里我们使用的NDVI数据是将伊宁23年的NDVI数据合并成为了一张栅格图像,每个波段表示一年的 NDVI,我们这里显示…

备战蓝桥杯---刷杂题2

显然我们直接看前一半&#xff0c;然后我们按照斜行看&#xff0c;我们发现斜行是递增的&#xff0c;而同一行从左向右也是递增的&#xff0c;因此我们可以直接二分&#xff0c;同时我们发现对称轴的数为Ck,2k. 我们从16斜行枚举即可 #include<bits/stdc.h> using name…

探索AI工具导航网站

在现代科技发展迅猛的时代&#xff0c;人工智能&#xff08;AI&#xff09;已经成为了各行各业中不可或缺的一部分。了解和利用最新的AI工具对于工作、学习和娱乐都具有重大意义。在这篇博客中&#xff0c;我们将探索一些最新的人工智能工具导航网站&#xff0c;以及其中一款名…

liunx系统发布.net core项目

liunx系统发布.net core项目 准备.net6程序运行环境部署nginx&#xff0c;通过一个地址既能访问web api&#xff0c;又能访问web项目有一个客户把web api放到docker中&#xff0c;想通过nginx转发&#xff0c;nginx也支持配置多个程序api接口的其它 liunx系统&#xff1a;cento…

【vue】ref 和 reactive 对比

ref&#xff1a;存储单个数据&#xff0c;如数值&#xff0c;字符串reactive&#xff1a;存储复杂数据&#xff0c;如对象&#xff0c;数组 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"vie…

短剧小程序系统开发,让短剧观看与创作更加便捷。短剧系统源码搭建

一、目前短剧发展趋势 1. 市场规模&#xff1a;根据数据来看&#xff0c;2023年中国微短剧市场规模达到了373.9亿元&#xff0c;同比上升了267.65%。预计2024年市场规模将超过500亿元。这一市场规模的增长速度非常显著&#xff0c;显示出短剧行业的巨大潜力和发展前景。 2. 投…

3款热门婴儿洗衣机全面对比测评:希亦、小吉、觉飞哪款性能最强?

经常洗大人衣物的传统洗衣机&#xff0c;很少有专门的高温除菌等功能&#xff0c;所以洗衣机里有可能会有一些大人身上带有的细菌&#xff0c;特别是婴儿衣物&#xff0c;婴儿抵抗能力弱&#xff0c;衣物混洗可能让宝宝感染细菌而导致生病&#xff0c;这种事情是有过发生的&…

SI案例分享--实用的单端口Delta-L测试方法

目录 0 引言 1 单端口Delta-L技术 2 基于单端口Delta-L方法的反射灵敏度分析 3 用充分表征的材料系统验证该方法 4 在单端口法中提取总损耗 5 总结 0 引言 Intel Delta-L方法已被公认为一种常规方法&#xff0c;通过对测试线进行2端口测量来提取层压板材料的Dk和插入损耗…

FX110网:汇市经纪商Prospero Markets被ASIC发出正式清盘令

澳大利亚联邦法院已批准金融监管机构 ASIC 的请求&#xff0c;向ASIC 许可的&#xff08;前&#xff09;零售外汇和差价合约经纪商 Prospero Markets Pty Ltd 发出正式清盘令。 相关阅读&#xff1a;《ASIC请求下令清盘汇市经纪商Prospero Markets》 法院于周四发布命令&#…

JVM调优工具详解-jps、jmap、jstat、jstack

jps 用于查看相关java线程的相关信息 选项作用-q仅显示进程 ID&#xff0c;而不显示类名或 JAR 文件的路径-m显示传递给主类的参数-l显示完整的主类名或 JAR 文件的路径-v显示传递给 Java 虚拟机的参数 jmap 此命令用来查看内存信息&#xff0c;实例个数以及占内存大小 jmap…

Ant Design 表单基础用法综合示例

Ant Design 的表单组件设计得非常出色,极大地简化了表单开发的复杂度,让开发者能够快速构建出功能丰富、交互友好的表单界面。 接下来总结一下 Ant Design 中表单的基本用法。 Form 组件 用于定义整个表单,可以设置表单的布局方式、提交行为等。通常会将表单字段组件嵌套在 F…

从ChatGPT到多模态大模型:现状与未来(多模态)

ChatGPT 训练的核心技术主要包括: 预训练语言模型;有监督微调;基于人类反馈的 强 化 学 习 (ReinforcementLearningfrom Human Feedback,RLHF) 首先,通过自监督预训练使语言模型从大规模语料库中学习语言规律,具备基础 理解和生成能力;然后,通过构造指令微调数据集 并对模型进…

VMware导出虚拟机vmkd格式转换qcow2

VMware虚拟机导出qcow2格式可以上传至云服务 1、需要导出的虚拟机 2、克隆虚拟机 3、选择克隆源 4、创建完整克隆 5、完成 6、找到VMware安装路径 7、找到vmware-vdiskmanager所在路径使用cmd或Windows PowerShell进入目录 进入vmware-vdiskmanager目录 cd F:\软件\VMware Wo…

CSS特效---百分比加载特效

1、演示 2、一切尽在代码中 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title&…

【NLP】多标签分类【下】

文章目录 简介个人博客与相关链接1 实验数据与任务说明2 模型介绍2.1 TransformerTransformer能做什么&#xff1f; 2.2 Hugging FaceHugging Face的Transformers库社区支持和资源预训练模型的应用 2.3 T5模型&#xff08;Text-To-Text Transfer Transformer&#xff09;T5的核…

VUE3组合式API

create-vue create-vue是Vue官方新的脚手架工具&#xff0c;底层切换到了vite,为开发提供极速相应 使用create-vue 1.安装16.0或者更高版本的Node.js 2.npm init vuelatest指令会安装并执行create-vue 项目目录和关键文件 组合式API Vue 3引入了组合式API&#xff08;Com…

走进MySQL:从认识到入门(针对初学者)

一&#xff0c;引言 MySQL是一款久负盛名且广泛应用的关系型数据库管理系统&#xff0c;自1995年Michael Widenius和David Axmark在瑞典和芬兰发起研发以来&#xff0c;其发展历程可谓辉煌且深远。作为开源软件的代表&#xff0c;MySQL以其卓越的成本效益、高性能及高可靠性赢得…

Linux使用宝塔面板部署Discuz结合内网穿透实现公网访问本地论坛

文章目录 前言1.安装基础环境2.一键部署Discuz3.安装cpolar工具4.配置域名访问Discuz5.固定域名公网地址6.配置Discuz论坛 前言 Crossday Discuz! Board&#xff08;以下简称 Discuz!&#xff09;是一套通用的社区论坛软件系统&#xff0c;用户可以在不需要任何编程的基础上&a…

ZLMediaKit ubantu 下编译

1、获取代码 #国内用户推荐从同步镜像网站gitee下载 git clone --depth 1 https://gitee.com/xia-chu/ZLMediaKit cd ZLMediaKit #千万不要忘记执行这句命令 git submodule update --init二、依赖库 Debian系(包括ubuntu&#xff09;系统下安装依赖的方法&#xff1a; #除了…

【考研数学】《660》+《880》高分搭配方法

&#x1f4dd;《660题》和《880题》高效刷题方法 1️⃣做题要有针对性&#xff0c;不要为了做题而做题 &#x1f4aa;660和880题虽然多&#xff0c;但是你不用全都做完&#xff0c;你可以把它当成是题源&#xff0c;里面的每一道题都很经典&#xff0c;如果搞懂一道&#xff…