Javascript data structure stack (leetCode 20)

1, concept,

A stack, also known as a stack, is a linear table with limited operations. Defines linear tables that only perform insert and delete operations at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element. To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element. (PS: Source baidu Encyclopedia)

2. Stack in JS

Stack is a lifO data structure, js does not have a stack, but you can use Array to achieve all the functions of the stack.

// Create a data emulation stack
const stack = [];
/ / into the stack
stack.push(1); // stack: [1]
stack.push(2); / / stack: [1, 2]
/ / out of the stack
stack.pop() // stack: [1]
stack.pop() // stack: []
Copy the code

3. Application scenario of stack

• Need last in, first out scenario.
• For example: decimal conversion to arbitrary base 2-9 numbers, string parentheses are valid, function call stack…

For octal number 100, divide 100 by 8, then 12 has a remainder of 4, then 12 divided by 8 has a remainder of 4, then 1 divided by 8 has a remainder of 1, then 1 divided by 8 has a remainder of 1, then the third remainder of 1 is pushed, and finally the three remainder is pushed off the stack, and the octal number of 100 is 144.

4,leetCode

LeetCode20 valid parentheses

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order.

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function (s) {
    // Check whether the length is even
    if (s.length % 2= = =1) {
        return false;
    };
    // Define a map key for the open parenthesis value corresponding to the close parenthesis
    const map = new Map()
    map.set('('.') ')
    map.set('{'.'} ')
    map.set('['.'] ')
    // Create a stack
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        // Get the current parentheses
        const c = s[i];
        // Open parentheses are pushed directly into the stack
        if (map.get(c)) {
            stack.push(c);
        } else { / / right parenthesis
            // Get the bracket at the top of the stack (left bracket)
            const l = stack[stack.length - 1];
            // Check whether the parentheses at the top of the stack match the current parentheses.
            if (map.get(l) === c) {
                stack.pop();
            } else {
                return false; // Invalid if not matched}}}return stack.length === 0;  // If the stack length is 0, it is a valid parenthesis
};
Copy the code