Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

1. What is a stack?

• An in – out data structure;
• JavaScript doesn’t have a stack structure; You can use arrays to implement stack functions
  • A push into stack (x);
  • A stack of pop ();

const stack = [];

/ / into the stack
stack.push(1);
stack.push(2);

/ / out of the stack
const item1 = stack.pop();
const item2 = stack.pop();
Copy the code

2. When is stack used

All lifO structures.

2.1 Decimal conversion to binary: the final remainder should be output in reverse order to correct binary;

• The remainder that comes out after is going to come out first
• The remainder can be stacked and then out of the stack to achieve the remainder output in reverse order.

2.2 Checking whether parentheses are valid: The left parentheses go into the stack, the right parentheses go out of the stack, and the empty stack is valid;

• The further back the left parenthesis, the further forward the corresponding right parenthesis
• Open parenthesis on the stack, close parenthesis off the stack, and finally empty stack is legal

2.3 Function call stack: The function called last is executed first.

• The function called last is executed first
• The JS interpreter uses stacks to control the order of function calls

3. leetcode: 20. Valid brackets

valid-parentheses

3.1 Solution idea

For an unclosed open parenthesis, the further back the open parenthesis, the further forward the corresponding close parenthesis

Input:"{[]}"Output:true
Copy the code

3.2 Steps to solve the problem

• Create a new stack
• If the left parenthesis type matches the top parenthesis type, it will be removed from the stack. If the type does not match, it will be judged as illegal

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function (s) {
    if (s.length % 2= = =1) { return false }
    const stack = [];
    for (let i = 0; i < s.length; i += 1) {
        const c = s[i];
        if (c === '(' || c === '{' || c === '[') {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1];
            if (
                (t === '(' && c === ') ') ||
                (t === '{' && c === '} ') ||
                (t === '[' && c === '] ')
            ) {
                stack.pop();
            } else {
                return false; }}}return stack.length === 0;
};
Copy the code

4. Front-end and stack: function call stack in JS

Last in, first out

    const func1 = () = > {
        func2();
    };
    const func2 = () = > {
        func3();
    };
    const func3 = () = > {};

    func1();
Copy the code

5. LeetCode:144. Antecedent traversal of binary trees

What is a binary tree

Advanced:Recursion is simple, can you do it iteratively?

Use stack to simulate recursion and rewrite recursion

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function (root) {
    const res = [];
    const stack = [];
    if (root) stack.push(root)
    while (stack.length) {
        const n = stack.pop();
        res.push(n.val)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
    return res
};
Copy the code

6. Stack – Summary

• A stack is a lifO data structure
• JavaScript doesn’t have a stack structure; You can use arrays to implement stack functions
• Common stack operations:A push into stack (x); 、 A stack of pop ();,Last element stack[stack.length-1]