JavaScript数据结构的堆栈实例用法

堆

我们先来看一个问题

Leetcode 32最长有效父项(最长有效括号)

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

示例1:

输入： '(()'输出： 2说明：的最长有效括号子字符串是' ()'

示例2:

输入： ')())'输出： 4解释：的最长有效括号子字符串是' () ()

这个问题可以通过动态编程来完成，也可以通过简单的栈来解决。

什么是堆栈？

堆栈是后进先出法的有序集合，新添加的元素在顶部，旧元素在底部。

以下图为例，1、2、3、4、5、6、7依次堆叠：

创建堆栈

创建一个类来表示堆栈：

Class Stack {//初始化类，创建一个项的数组，并将它们存储在Stack元素构造函数(){ this . items=[]；} //push方法堆叠元素(一个或多个元素可以同时堆叠)，无返回值push () {this。items.push(.论据)；} //pop方法弹出一个元素并返回pop(){ return this . items . pop()；} //peek方法返回堆栈的顶部元素，而不对堆栈本身执行任何操作peek(){ return this . items[this . items . length-1]；} //size方法返回堆栈大小(){ return this . items . length；} //isEmpty方法检查堆栈是否为空，并返回布尔值isempty () {return this。items . length==0；} //clear方法清空堆栈，没有返回值clear(){ this . items=[]；} //print方法打印堆栈中的元素print(){ console . log(this . items . tostring())；} }//测试让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类中定义，所以可以在类外访问存储栈元素的数组项，这是非常危险的。

stack.items//[1，2，3，4]闭包和IIFE可以用来避免这种情况，这是一种非常无奈的方式：

Let Stack=(function () {//使用WeakMap存储数组(数组存储堆栈元素)let items=new WeakMap()；类Stack { constructor(){ items . set(this，[])；} push() { items.get(this)。推送(.论据)；}//其他方法}返回Stack})();let s=new Stack()；//无法访问itemss.items//undefinedWeakMap: WeakMap是一组类似Map的键值对，但是WeakMap的键被弱引用，所以只要没有引用，垃圾收集机制就会回收占用的内存，相当于自动删除而不是手动删除。

用堆栈解决问题

思考：

变量start存储有效的括号起始下标，maxLen存储最大长度；

栈只存储左括号的下标，遇到左括号时把它的下标存储在栈中；

遇到右括号，如果此时栈是空的，跳过这个循环，更新开始；如果堆栈不为空，则弹出堆栈的顶部元素；

栈顶元素出栈后，如果栈是空的，计算当前下标到开始的距离，更新maxLen；

栈顶元素出栈后，如果栈不为空，计算当前下标与栈顶存储下标的距离，更新maxLen；

循环直到结束。

函数测试(str){ let Stack=new Stack()；让start=0；让Maxlen=0；for(设I=0；istr.lengthI) {//如果是左括号，栈上下标If(str[I]=='('){ stack . push(I)；} else {//如果是右括号/*，则堆栈为空，表示这个有效的括号匹配已经结束。跳过此循环并更新start */if(堆栈。isempty()){ start=I ^ 1；继续；} else {//如果栈不为空，弹出左括号匹配stack . pop()；//栈顶元素出栈后，如果(stack.isEmpty()) {//根据当前下标和开始，更新maxlen maxlen=math.max (maxlen，I-start1)，栈为空；} else {//栈不为空，根据当前下标和栈顶存储的下标更新maxlen maxlen=math.max (maxlen，I-stack . peek())；} } } }返回maxLen}测试(((()))；//2test(')()())')；//4