JavaScript: Stacks in Detail

In computer science, the stack is an important data structure that follows the last-in-first-out (LIFO) principle. This means that the last element added to the stack is the first to be removed. Because of this property, stacks are useful in many programming scenarios, such as function calls, dealing with bracket matching, reversing strings, and so on. In JavaScript, there is no built-in stack type, but we can use arrays to emulate all the features of a stack.

 Basic concepts of stacks

A stack is a special list that allows insertion or deletion operations only at one end. There are four main types of stack operations:

•  Push: Place an element on top of the stack.
•  Pop: Removes the top element of the stack and returns it.
• 
  See top of stack (peek) : Returns the top element of the stack without modifying it.
• 
  Check if the stack is empty (isEmpty) : Determines if the stack is empty, returns a boolean value.

 illustrate

Next, we can make a simple illustration of the “stacking” and “stack popping” operations. This will help to understand how elements are added and removed.

 JavaScript implementation of the stack

In JavaScript, there is no special stack to realize the function of moving elements in and out of one end, but we can use arrays to realize the function of a stack. We consider an array as a stack, and then only insertion and deletion operations are performed on one end.

 Here is a simple implementation of the stack class:

 1. Push

A press-stack operation is the addition of a new element to the top of the stack. This is one of the most common operations in stack data structures.

push(element) {
    this.items.push(element); 
}

 2. Pop

A stack popping operation is one that removes an element from the top of the stack and returns the removed element. This is the basic operation of the stack, following the principle of last-in-first-out (LIFO).

pop() {
    if (this.items.length == 0) {
        return "Underflow"; 
    }
    return this.items.pop(); 
}

 3. Viewing the top of the stack (peek)

A view top of stack operation is one that returns the element at the top of the stack, but does not remove it. This allows us to view the last element added to the stack.

peek() {
    return this.items[this.items.length - 1]; 
}

 4. Check if the stack is empty (isEmpty)

Checking whether the stack is empty is a utility operation that determines whether there are still elements on the stack. If the stack is empty, true is returned; otherwise, false is returned.

isEmpty() {
    return this.items.length === 0; 
}

This stack class uses the array items to store the elements of the stack. push Methods are used to add elements to the top of the stack, pop is used to remove the top of the stack, peek returns the top of the stack without removing it, and isEmpty is used to check if the stack is empty.

 Stack application scenarios

Stacks are widely used in algorithms and everyday programming. For example, managing the function call process in the browser’s function call stack, or using the stack to handle operators and operands when parsing and executing expressions. In addition, stacks are often used in backtracking algorithms, such as solving mazes or bracket matching problems.

 Sample Algorithmic Problems

Design an algorithm to determine whether a given string is a valid sequence of parentheses. The sequence of parentheses consists of parentheses ‘(‘ and ‘)’, middle parentheses ‘[‘ and ‘]’, and curly braces ‘{‘ and ‘}’, and the parentheses must be closed in the correct order.

例如：

1.  Input: “()”, Output: true
2.  Input: “()[]{}”, Output: true
3.  Input: “(]”, output: false
4.  Input: “([)]”, output: false
5.  Input: “{[]}”, output: true

Ans: This problem can be solved using the stack. Iterate through the string, and when a left bracket is encountered, press it onto the stack; when a right bracket is encountered, determine whether the top of the stack is the corresponding left bracket, and if it is, pop the top element of the stack, otherwise return false. finally, if the stack is empty, then all the brackets have been correctly closed, return true; otherwise, return false.

 Here is a detailed breakdown of the algorithm:

function isValid(s) {
    let stack = [];
    let mapping = {')': '(', ']': '[', '}': '{'};
    
    for (let char of s) {
        if (char in mapping.values()) {
            stack.push(char);
        }
        else if (char in mapping) {
            if (stack.length === 0 || mapping[char] !== stack.pop()) {
                return false;
            }
        }
        else {
            continue;
        }
    }
    
    return stack.length === 0;
}

console.log(isValid("()"));      // true
console.log(isValid("()[]{}"));  // true
console.log(isValid("(]"));      // false
console.log(isValid("([)]"));    // false
console.log(isValid("{[]}"));    // true

The time complexity of this algorithm is O(n), where n is the length of the input string. Since we need to traverse the input string only once and the stack operations are all of O(1) time complexity.

The simplicity and efficiency of stacks make them useful in solving similar problems. Mastering stack operations and applications can help you better understand and implement complex algorithms and data structures. Through this article, you not only learned how to implement and use the stack in JavaScript, but also solved a common algorithmic problem, and hope that you will be able to use the stack flexibly to simplify the problem solving process in your future programming and algorithm learning.