搜索
首页web前端js教程JavaScript数据结构之栈的用法示例

JavaScript数据结构之栈的用法示例

Jan 18, 2019 am 11:10 AM
javascript

本篇文章给大家带来的内容是关于JavaScript数据结构之栈的用法示例,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

先来看一道题

Leetcode 32 Longest Valid Parentheses (最长有效括号)

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

这道题可以用动态规划来做,也能用简洁明了的栈来解决。

什么是栈?

栈是一种先进后出(LIFO)的有序集合,新添加的元素在栈顶,旧元素在栈底。

以下图为例,1、2、3、4、5、6、7先后进栈:

stack.bmp

创建栈

创建一个类来表示栈:

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的键是弱引用的,只要不存在引用,垃圾回收机制就会回收掉占用的内存,相当于自动删除,而不用手动删除。

用栈解题

思路:

  1. 变量start存放有效括号起始下标,maxLen存放最大长度;

  2. 栈只存放左括号的下标,遇到左括号,将其下标存入栈中;

  3. 遇到右括号,若此时栈为空,跳过本次循环并更新start;若栈不为空,则栈顶元素出栈;

  4. 栈顶元素出栈后,若栈为空,则计算当前下标和start的距离,并更新maxLen

  5. 栈顶元素出栈后,若栈不为空,则计算当前下标和栈顶存放的下标的距离,并更新maxLen

  6. 循环遍历直至结束。

function test(str) {
    let stack = new Stack();
    let start = 0;
    let maxLen = 0;

    for(let i=0; i<str.length; i++) {
        // 如果是左括号,下标入栈
        if (str[i] == &#39;(&#39;) {
            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(&#39;(()&#39;); // 2
test(&#39;)()())&#39;); // 4

以上是JavaScript数据结构之栈的用法示例的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:博客园。如有侵权,请联系admin@php.cn删除
超越浏览器:现实世界中的JavaScript超越浏览器:现实世界中的JavaScriptApr 12, 2025 am 12:06 AM

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

使用Next.js(后端集成)构建多租户SaaS应用程序使用Next.js(后端集成)构建多租户SaaS应用程序Apr 11, 2025 am 08:23 AM

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

如何使用Next.js(前端集成)构建多租户SaaS应用程序如何使用Next.js(前端集成)构建多租户SaaS应用程序Apr 11, 2025 am 08:22 AM

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

JavaScript:探索网络语言的多功能性JavaScript:探索网络语言的多功能性Apr 11, 2025 am 12:01 AM

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

JavaScript的演变:当前的趋势和未来前景JavaScript的演变:当前的趋势和未来前景Apr 10, 2025 am 09:33 AM

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

神秘的JavaScript:它的作用以及为什么重要神秘的JavaScript:它的作用以及为什么重要Apr 09, 2025 am 12:07 AM

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

Python还是JavaScript更好?Python还是JavaScript更好?Apr 06, 2025 am 12:14 AM

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

如何安装JavaScript?如何安装JavaScript?Apr 05, 2025 am 12:16 AM

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

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

SecLists

SecLists

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

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

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

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能