本篇文章给大家带来的内容是关于JavaScript数据结构之栈的用法示例,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
栈
先来看一道题
Leetcode 32 Longest Valid Parentheses (最长有效括号)
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
这道题可以用动态规划来做,也能用简洁明了的栈来解决。
什么是栈?
栈是一种先进后出(LIFO)的有序集合,新添加的元素在栈顶,旧元素在栈底。
以下图为例,1、2、3、4、5、6、7先后进栈:
创建栈
创建一个类来表示栈:
class Stack { // 初始化类,创建数组 items 存放入栈元素 constructor() { this.items = []; } // push 方法进行元素入栈(可同时入栈一或多个元素),无返回值 push() { this.items.push(...arguments); } // pop 方法出栈一个元素,返回出栈元素 pop() { return this.items.pop(); } // peek 方法返回栈顶元素,不对栈本身做任何操作 peek() { return this.items[this.items.length-1]; } // size 方法返回栈内元素个数 size() { return this.items.length; } // isEmpty 方法查看栈是否为空,返回布尔值 isEmpty() { return this.items.length == 0; } // clear 方法清空栈,无返回值 clear() { this.items = []; } // print 方法打印栈内元素 print() { console.log(this.items.toString()); } } // 测试 let stack = new Stack(); stack.push(1,2,3,4); stack.print(); // 1,2,3,4 stack.isEmpty(); // false stack.size(); // 4 stack.pop(); // 4 stack.peek(); // 3 stack.clear();
注意
因为 JavaScript 的类内暂时无法定义私有成员,所以可以在类外访问到存储栈元素的数组 items,这个操作是很危险的。
stack.items; // [1, 2, 3, 4]
这时可以使用闭包和IIFE
进行避免,这是一个很无奈的办法:
let Stack = (function () { // 使用 WeakMap 存储数组(数组存放进栈元素) let items = new WeakMap(); class Stack { constructor() { items.set(this, []); } push() { items.get(this).push(...arguments); } // 其他方法 } return Stack; })(); let s = new Stack(); // 无法访问到 items s.items; // undefined
WeakMap: WeakMap
是类似Map
的键值对集合,但WeakMap
的键是弱引用的,只要不存在引用,垃圾回收机制就会回收掉占用的内存,相当于自动删除,而不用手动删除。
用栈解题
思路:
变量
start
存放有效括号起始下标,maxLen
存放最大长度;栈只存放左括号的下标,遇到左括号,将其下标存入栈中;
遇到右括号,若此时栈为空,跳过本次循环并更新
start
;若栈不为空,则栈顶元素出栈;栈顶元素出栈后,若栈为空,则计算当前下标和
start
的距离,并更新maxLen
;栈顶元素出栈后,若栈不为空,则计算当前下标和栈顶存放的下标的距离,并更新
maxLen
;循环遍历直至结束。
function test(str) { let stack = new Stack(); let start = 0; let maxLen = 0; for(let i=0; i<str.length; i++) { // 如果是左括号,下标入栈 if (str[i] == '(') { stack.push(i); } else { // 如果是右括号 /* 栈内为空,说明本次有效括号匹配已结束,跳过本次循环并更新 start */ if (stack.isEmpty()) { start = i+1; continue; } else { // 栈内不为空,则出栈一个左括号进行匹配 stack.pop(); // 栈顶元素出栈后,栈为空 if (stack.isEmpty()) { // 根据当前下标和 start 去更新 maxLen maxLen = Math.max(maxLen, i-start+1); } else { // 栈不为空,根据当前下标和栈顶存放的下标去更新 maxLen maxLen = Math.max(maxLen, i-stack.peek()); } } } } return maxLen; } test('(()'); // 2 test(')()())'); // 4
以上是JavaScript数据结构之栈的用法示例的详细内容。更多信息请关注PHP中文网其他相关文章!

JavaScript在现实世界中的应用包括服务器端编程、移动应用开发和物联网控制:1.通过Node.js实现服务器端编程,适用于高并发请求处理。2.通过ReactNative进行移动应用开发,支持跨平台部署。3.通过Johnny-Five库用于物联网设备控制,适用于硬件交互。

我使用您的日常技术工具构建了功能性的多租户SaaS应用程序(一个Edtech应用程序),您可以做同样的事情。 首先,什么是多租户SaaS应用程序? 多租户SaaS应用程序可让您从唱歌中为多个客户提供服务

本文展示了与许可证确保的后端的前端集成,并使用Next.js构建功能性Edtech SaaS应用程序。 前端获取用户权限以控制UI的可见性并确保API要求遵守角色库

JavaScript是现代Web开发的核心语言,因其多样性和灵活性而广泛应用。1)前端开发:通过DOM操作和现代框架(如React、Vue.js、Angular)构建动态网页和单页面应用。2)服务器端开发:Node.js利用非阻塞I/O模型处理高并发和实时应用。3)移动和桌面应用开发:通过ReactNative和Electron实现跨平台开发,提高开发效率。

JavaScript的最新趋势包括TypeScript的崛起、现代框架和库的流行以及WebAssembly的应用。未来前景涵盖更强大的类型系统、服务器端JavaScript的发展、人工智能和机器学习的扩展以及物联网和边缘计算的潜力。

JavaScript是现代Web开发的基石,它的主要功能包括事件驱动编程、动态内容生成和异步编程。1)事件驱动编程允许网页根据用户操作动态变化。2)动态内容生成使得页面内容可以根据条件调整。3)异步编程确保用户界面不被阻塞。JavaScript广泛应用于网页交互、单页面应用和服务器端开发,极大地提升了用户体验和跨平台开发的灵活性。

Python更适合数据科学和机器学习,JavaScript更适合前端和全栈开发。 1.Python以简洁语法和丰富库生态着称,适用于数据分析和Web开发。 2.JavaScript是前端开发核心,Node.js支持服务器端编程,适用于全栈开发。

JavaScript不需要安装,因为它已内置于现代浏览器中。你只需文本编辑器和浏览器即可开始使用。1)在浏览器环境中,通过标签嵌入HTML文件中运行。2)在Node.js环境中,下载并安装Node.js后,通过命令行运行JavaScript文件。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

Dreamweaver Mac版
视觉化网页开发工具

MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

VSCode Windows 64位 下载
微软推出的免费、功能强大的一款IDE编辑器

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能