首页 > 其他分享 >数据结构---栈

数据结构---栈

时间:2023-12-12 19:57:30浏览次数:30  
标签:运算符 实现 元素 撤销 --- 算法 操作 数据结构

栈(Stack)是一种线性数据结构,它按照后进先出(LIFO, Last In First Out)的原则存储和管理数据。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。

栈的主要操作包括:

压栈(Push):在栈的顶部添加一个元素。
弹栈(Pop):移除栈顶部的元素。
查看栈顶(Peek/Top):查看栈顶部的元素但不移除。
判断栈是否为空(IsEmpty):检查栈是否包含任何元素。
获取栈的大小(Size):返回栈中元素的数量。
在实际应用中,栈有很多用途。例如,它们可以用于实现撤销和重做功能,因为它们可以存储和恢复先前的状态。在计算机科学中,它们也用于实现函数调用堆栈和回溯算法等。

栈的优点主要包括:

实现简单:栈只需要两种基本操作,入栈和出栈,操作比较直观,不需要复杂的算法。
占用空间小:栈只占用很小的内存空间,甚至可以使用栈实现递归调用。
在栈中查找元素容易:栈顶的元素是最后一个入栈的元素,因此在查找时只需要从栈顶向下查找就可以了。
可以实现递归调用:如果使用栈来实现递归调用,程序的效率会很高。
此外,栈也易于操作、方便编程,且对于某些场景,如括号匹配、表达式求值、深度优先搜索等,使用栈可以简化问题并提高效率。
用图进行简易理解:

栈在许多场景中都特别有用,包括:

撤销和重做功能:许多软件应用程序在实现撤销功能时会使用栈。每当用户执行一个操作时,比如添加、删除或修改,相关信息将被推入栈中。当用户选择撤销时,程序将从栈中弹出最近的操作并还原到上一个状态。
后退/前进功能:网页浏览器中的后退和前进按钮也可以使用栈来实现。在浏览网页时,每次访问一个新页面时,当前页面的信息将被推入栈中。当用户点击后退按钮时,程序将从栈中弹出最近的访问页面,并显示上一个页面。
递归算法:递归算法也使用栈来实现。在递归函数中,每次递归调用时,函数的当前状态(包括参数和局部变量)会被推入栈中。当递归函数结束时,栈会弹出并还原上一个状态。
括号匹配:假设表达式中只包含三种括号,圆括号 ()、方括号[]和花括号{},并且它们可以任意嵌套。 比如,{[] ()[{}]}或[{()}([])]等都为合法格式,而{[}()]或[({)]为不合法的格式。 我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。
表达式求值:编译器通过两个栈来实现,一个栈用来保存操作数,一个栈用来保存运算符。 从左到右遍历表达式,当遇到数字,压入操作数栈,当遇到运算符,与运算符栈栈顶进行比较 如果比运算符栈顶元素优先级高,就将当前运算符压入栈。 否则从运算符栈中取栈顶运算符,从操作符栈中取两个数进行计算,把运算结果压入操作数栈,继续比较。

在撤销和重做功能中,栈的使用方式如下:

撤销操作:当用户执行某个操作时,将该操作及其相关数据压入栈中。如果用户想要撤销该操作,就从栈中弹出最近的操作,并按照该操作的逆操作进行还原。
重做操作:如果用户想要重做某个已撤销的操作,只需将该操作从栈中弹出,并再次执行它。
通过这种方式,栈实现了撤销和重做功能,使得用户可以方便地回退或重复执行操作。

总结

栈算法是一种基于栈数据结构的算法,它通常用于解决一些需要后进先出(LIFO)操作的问题。栈算法的主要特点是可以方便地实现数据的入栈和出栈操作,并且可以高效地处理数据的后进先出顺序。

总的来说,栈算法在很多问题中都有广泛的应用,其优点包括实现简单、空间利用率高、可以高效地处理后进先出的问题等。但同时也要注意其可能存在的缺点,如可能会导致栈溢出或效率低下等问题。因此在使用栈算法时需要根据具体问题谨慎考虑其适用性和效率。

标签:运算符,实现,元素,撤销,---,算法,操作,数据结构
From: https://www.cnblogs.com/ywx1207/p/17897681.html

相关文章

  • Docker_harbor-网络排查以及redi排查
    仓库registry公共仓库DockerHub这样的公共仓库 本地仓库docker-registry是官方提供的工具,可以用于构建私有的镜像仓库。 Harbor是构建企业级私有docker镜像的仓库的开源解决方案,它是DockerRegistry的更高级封装还整合了两个开源的安全组件,一个是N......
  • 1.变量的声明-原始类型
    变量的声明-基础类型/*前言:如果变量的声明和赋值是同时进行的,TS可以自动对变量进行类型检测这里ts自动将variable推断为boolean类型----类型推断机制*/letvariable=false;variable=true;1.number数字类型/*注意:TypeScript里的所有数字都是浮点数,没有......
  • 侯哥的Python分享--系列教程
    合集-mysql(26) 1.侯哥的Python分享2019-04-162.MySQL基础1-关系型数据库与非关系型数据库2022-03-173.MySQL基础2-数据库及表的操作2022-03-174.MySQL基础3-数据库增删改操作2022-03-175.MySQL基础4-数据查询07-176.MySQL基础5-用户及权限管理07-187.MySQL基础6-常用数......
  • IDEA插件Apipost-Helper使用介绍
    IDEA是一款功能强大的集成开发环境(IDE),它可以帮助开发人员更加高效地编写、调试和部署软件应用程序。我们在编写完接口代码后需要进行接口调试等操作,一般需要打开额外的调试工具。今天给大家介绍一款IDEA插件:Apipost-Helper-2.0。代码写完直接编辑器内调试、还支持生成接口文档、接......
  • C语言-文件操作
    在接触文件操作之前,我们写的程序都是在内存中存储着,一旦程序结束内存中存储的数据都会被擦除,所以如果想要程序结束数据仍然要保留,那就需要将其持久化,就需要用文件操作,将需要保留的数据存储在硬盘中。下次使用时再打开即可。那么关于文件主要介绍以下几个部分:什么是文件磁盘上的文件......
  • 无涯教程-Java - Singleton Classes函数
    Singleton的目的是控制对象的创建,将对象的数量限制为一个。由于只有一个Singleton实例,因此Singleton的任何实例字段在每个类中只会出现一次,就像static字段一样。单例通常控制对资源的访问,例如数据库连接或Socket。例如,如果您仅对数据库的一个连接拥有许可证,或者JDBC驱动......
  • MySQL运维3-分库分表策略
    一、介绍单库瓶颈:如果在项目中使用的都是单MySQL服务器,则会随着互联网及移动互联网的发展,应用系统的数据量也是成指数式增长,若采用单数据库进行存储,存在一下性能瓶颈:IO瓶颈:热点数据太多,数据库缓存不足,产生大量磁盘IO,效率低下,请求数据太多,带宽不够,网络IO瓶颈。CPU瓶颈:排序......
  • 记录--Echarts绘制气泡图
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助Echarts绘制气泡图气泡图是一种用于可视化三维数据的图表类型,其中两个变量用于确定数据点在平面上的位置,另一个变量用于确定气泡的大小。Echarts是一款基于JavaScript的数据可视化库,它提供了丰富的图表类型,包括灵......
  • go-zero开发入门之网关往rpc服务传递数据
    go-zero的网关往rpc服务传递数据时,可以使用headers,但需要注意前缀规则,否则会发现数据传递不过去,或者对方取不到数据。go-zero的网关对服务的调用使用了第三方库grpcurl,入口函数为InvokeRPC:grpcurl.InvokeRPC(r.Context(),source,cli.Conn(),rpcPath,s.prepareMetadat......
  • IDEA插件Apipost-Helper使用介绍
    IDEA是一款功能强大的集成开发环境(IDE),它可以帮助开发人员更加高效地编写、调试和部署软件应用程序。我们在编写完接口代码后需要进行接口调试等操作,一般需要打开额外的调试工具。今天给大家介绍一款IDEA插件:Apipost-Helper-2.0。代码写完直接编辑器内调试、还支持生成接口文档、......