Understanding of stack and practical application scenarios

​

Stack It's a data structure , stay js We know that , The basic data type is stored in stack memory , A reference data type is an address reference stored on the stack , It is actually stored in heap memory , Today we are going to see leetcode subject , Deepen the understanding of the stack , Match valid parentheses , This is the application of stack

The title means : Given one only includes '(',')','{','}','[',']' String s , Determines whether the string is valid .

requirement ：

1、 Opening parentheses must be closed with closing parentheses of the same type

2、 The left parentheses must be closed in the correct order

The core of the topic is about Stack Usage scenarios of , And we can use stack to solve this problem

Let's get rid of this algorithm problem , What is stack? , Understanding stack , Use a diagram to understand

stay js We can use arrays to simulate Stack Characteristics , In and out of the stack , We often hear that the stack is first in and last out , Last in, first out , How to understand this seems to know , But it is always a concept of shell burning

We use an array to simulate the stack

Push

//  Construct a stack structure , Define an array 
var stack = [];
//  Push 
stack.push(1);
//  Keep getting on the stack , Sometimes it is also called pressing stack 
stack.push(2);
stack.push(3,4);
console.log(stack) // [1,2,3,4]

Copy

Out of the stack

...
let value = null;
value = stack.pop(); // 4  It bounced out 
console.log(stack); // [1,2,3];
value = stack.pop(); // 3  It bounced out 
console.log(stack); // [1,2];
value = stack.pop(); // 2  It bounced out 
console.log(stack); // [1];
value = stack.pop(); // 1  It bounced out 
console.log(stack); // []; //  Finally, the length of the stack is empty 

Copy

You can combine the above figure to understand the above code of stack entry and stack exit , When each stack out operation is performed , The arrays added later are popped out in turn . A more vivid metaphor is , The one who gets on the bus first sits on the tail of the bus , The one who got on the bus in the back , Standing at the door , When the car stops every time , Coming in the back , The one standing at the door went out first .

Get down to business , Understand the characteristics of stack structure , Then this problem can be solved by stack

const isValid = (s) => {
  var stack = [];
  for (let i=0;i<s.length;i++) {
    const val = s[i]
    //  Into the stack, 
    if (val === '(') {
        stack.push(')')
    } else if (val === '[') {
      stack.push(']'); //  Into the stack, 
    } else if (val === '{') {
      stack.push('}'); //  Into the stack, 
    } else if (val !== stack.pop()) {
      // pop Extract value , Compare the following in turn , If it is not equal to the extracted value , Then it's a mismatch , return false
      return false;
    }
  }
  return stack.length === 0 //  All last pop Come out , Array is empty , Prove that all match 
}

Copy

Is there any other solution besides this way ？ Let's look at other ways

const isValid2 = (s) => {
  const stack = [];
  const map = new Map([
    ['(', ')'],
    ['[', ']'],
    ['{', '}']
  ]);
  for (let i=0;i<s.length;i++) {
    const c = s[i];
    if (map.has(c)) {
        //  Judge map There is key value , Into the stack, 
        stack.push(c)
    } else {
      //  Get the value of the stack 
      const mapKey = stack[stack.length -1];
      //  obtain map Value 
      if (map.get(mapKey) === c) {
         stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0
}

Copy

summary

1、 Understand stack structure characteristics , First in, then out , Last in first out feature

2、 Array emulation stack feature ,push Push ,pop Out of the stack

3、 Application of symbol matching , Judge whether it is in the loop (,[,{, Then stack the corresponding symmetric symbol , Judge whether the current value is not equal to the stack value , Then the return false, until stackpop Find all the values , Stack length is empty , Prove that all symbols match .

4、 utilize map The symbols corresponding to the mapping match , Loop string , If map Yes key, Put the current key Add to stack , without , First, take out the corresponding stack key, Then use the current key, Go to map.get(key) Whether the obtained value is equal to the current value , If equal , Just pop The value cannot be found , If it's not equal, it goes back to false, Until the end of the cycle , The length of the stack is 0, Prove that all symbols match .

5、code example[1]

6、 Source of this question leetcode-20[2]

Reference material

[1]code example: https://github.com/maicFir/lessonNote/blob/master/leetcode/leetcode-20.js

[2]leetcode-20: https://leetcode.cn/problems/valid-parentheses/