JavaScript数据结构之栈实例用法

原创 年树先生 随笔 JavaScript 1891阅读 27 天前 举报

在本篇文章里小编给大家分享了关于JavaScript数据结构之栈实例用法内容,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。


先来看一道题
Leetcode 32 Longest Valid Parentheses (最长有效括号)
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:

什么是栈?

栈是一种先进后出(LIFO)的有序集合,新添加的元素在栈顶,旧元素在栈底。
以下图为例,1、2、3、4、5、6、7先后进栈:

创建栈

创建一个类来表示栈:

注意

因为 JavaScript 的类内暂时无法定义私有成员,所以可以在类外访问到存储栈元素的数组 items,这个操作是很危险的。

这时可以使用闭包和IIFE进行避免,这是一个很无奈的办法:

WeakMap: WeakMap是类似Map的键值对集合,但WeakMap的键是弱引用的,只要不存在引用,垃圾回收机制就会回收掉占用的内存,相当于自动删除,而不用手动删除。

用栈解题

思路:
变量start存放有效括号起始下标,maxLen存放最大长度;
栈只存放左括号的下标,遇到左括号,将其下标存入栈中;
遇到右括号,若此时栈为空,跳过本次循环并更新start;若栈不为空,则栈顶元素出栈;
栈顶元素出栈后,若栈为空,则计算当前下标和start的距离,并更新maxLen;
栈顶元素出栈后,若栈不为空,则计算当前下标和栈顶存放的下标的距离,并更新maxLen;
循环遍历直至结束。

结语

感谢您的观看,如有不足之处,欢迎批评指正。

获取资料

本次给大家推荐一个免费的学习群,里面概括移动应用网站开发,css,html,webpack,vue node angular以及面试资源等。
对web开发技术感兴趣的同学,欢迎加入Q群:619586920,不管你是小白还是大牛我都欢迎,还有大牛整理的一套高效率学习路线和教程与您免费分享,同时每天更新视频资料。
最后,祝大家早日学有所成,拿到满意offer,快速升职加薪,走上人生巅峰。

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复