Usage example of JavaScript data structure stack

The content of this article is about the usage examples of JavaScript data structure stack. It has certain reference value. Friends in need can refer to it. I hope It will help you.

Stack

Let’s look at a question first

Leetcode 32 Longest Valid Parenthesis

Given a For a string containing only '(' and ')', find the length of the longest substring containing valid parentheses.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid bracket substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid bracket substring is "()()"

This problem can be solved using dynamic programming, or it can be solved using a concise and clear stack.

What is a stack?

The stack is a first-in-last-out (LIFO) ordered collection, with newly added elements at the top of the stack and old elements at the bottom of the stack.

The following figure is an example, 1, 2, 3, 4, 5, 6, and 7 are pushed into the stack one after another:

Create stack

Create a class to represent the stack:

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();

Note

Because private members cannot be defined temporarily in JavaScript classes, the array items that store stack elements can be accessed outside the class. This operation is Very dangerous.

stack.items; // [1, 2, 3, 4]

You can use closure and IIFE to avoid this. This is a very helpless method:

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 is a collection of key-value pairs similar to Map, but the keys of WeakMap are weak references. As long as there are no references, the garbage collection mechanism will Recycling the occupied memory is equivalent to automatic deletion instead of manual deletion.

Use stack to solve problems

Idea:

1. VariablestartStores the starting subscript of valid brackets, maxLen Store the maximum length;

2. The stack only stores the subscript of the left bracket. When encountering a left bracket, store its subscript in the stack;

3. When a right parenthesis is encountered, if the stack is empty at this time, skip this loop and update start; if the stack is not empty, pop the top element of the stack;

4. After the top element of the stack is popped, if the stack is empty, calculate the distance between the current subscript and start, and update maxLen;

5. After the top element of the stack is popped, if the stack is not empty, calculate the distance between the current subscript and the subscript stored on the top of the stack, and update maxLen;

6. Loop through until the end.

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

The above is the detailed content of Usage example of JavaScript data structure stack. For more information, please follow other related articles on the PHP Chinese website!