JS: 数据结构与算法之栈

栈

先来看一道题

---

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

用栈解题

---

思路：

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] == '(') {
            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

备注

---

终于从大半个月的考试和课设中解放出来了，每天早起晚睡，还是很累的。