JavaScript数据构造之栈的用途示例-百分百源码网

JavaScript数据构造之栈的用途示例

发布时间：09/01 来源：未知浏览：关键词：

本篇文章给大家带来的内容是关于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数据构造之栈的用途示例的具体内容，更多请关注百分百源码网其它相关文章！

打赏