Learn about the JavaScript stack in one article

This article brings you relevant knowledge about javascript. It mainly introduces an article to help you quickly understand the JavaScript stack. The full name of the stack is a stack, which is a first-in, last-out data structure. There are only two basic operations in the stack, namely insertion and deletion, that is, push and pop operations. Only one end of the stack can perform push and pop operations. I hope it will be helpful to everyone.

[Related recommendations: javascript video tutorial, web front-end]

What is a stack?

The full name of stack is stack, which is a first in, last out data structure. There are only two basic operations in the stack, namely insert and delete , that is, push and pop operations, Only one end of the stack can be pushed and popped , we call it top of stack , the other end is called Stack bottom; the following figure shows the stack data structure:

Stack in JavaScript

JavaScript There is no data type of stack, but it can be simulated through an array, and the push() and pop() options provided in the array just implement first-in, last-out operation.

The sample code is as follows:

const stack = []

// 入栈
stack.push(1)
stack.push(2)
// 出栈
const v1 = stack.pop() // 2
const v2 = stack.pop() // 1

Application scenarios of the stack

The stack is the most commonly used auxiliary structure in algorithms and programs, and its applications are very wide. Stacks are used in every scenario that requires first in, last out, for example:

• Function call stack
• Determine whether the string brackets are valid

Next, let’s look at it in turn:

Function call stack

The function call stack in JavaScript is a typical example of an application stack, such as the following code:

function f1() {}
function f2() {
  f1()
}
function f3() {
  f2()
}
f3()

As shown below:

##The execution process is as follows:

Call function
• f3() and push f3 onto the stack;
calls
• f2(() in f3() ), pushing f2 onto the stack;
calls
• f1() again in f2(), pushing f1Push onto the stack;
Only when
• f1() is completed can execution continue, so f1() is popped off the stack first, and so on. .

Effective parentheses

Effective parentheses is an algorithm question about stacks in Likou. The main idea of ​​the question is to determine whether the parentheses in a given string match, and return # if they match. ##true

, otherwise false is returned.

The problem-solving idea is as follows:

Determine whether the length of the string is an even number. If it is not an even number, it will directly return

false
• , because of the brackets They all appear in pairs; Create a new stack;
• Traverse the string, and when each item is traversed, if it is a left bracket, push it onto the stack; if it is a right bracket, and Compare the top of the stack. If there is a match, pop the stack. If not, return
false
• .

The implementation code is as follows:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    const stack = []
    for(let i = 0; i<s.length; i++) {
        const c = s[i] // 记录当前项
        if (c === &#39;(&#39; || c === &#39;[&#39; || c===&#39;{&#39;) {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1] // 获取栈顶元素
            if (
                (t === &#39;(&#39; && c === &#39;)&#39;) ||
                (t === &#39;[&#39; && c === &#39;]&#39;) ||
                (t === &#39;{&#39; && c === &#39;}&#39;)
            ) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    // 如果为0表示全部匹配，有剩余则表示不匹配
    return stack.length === 0
};

There may be a better way to write it, but the violent solution is used directly here.

【Related recommendations:

javascript video tutorial

, web front-end】

The above is the detailed content of Learn about the JavaScript stack in one article. For more information, please follow other related articles on the PHP Chinese website!