Application of stack – Describes data structures in JavaScript

A stack, also known as a stack, is a linear table with limited operations. The limitation is that only one end of the table is allowed for insert and delete operations. This end is called the top of the stack, and the other end is called the bottom of the stack.

A, the implementation of a Stack class Stack

Based on the stack feature, you can use arrays as linear tables for storage. Initialize the Stack class as follows:

function Stack(){
    this.space = [];
}

Stack.prototype = {
    constructor: Stack,
    /* Interface code */
};
Copy the code

Next, is in the prototype, on the stack, out of the stack, empty the stack, read the top of the stack, read the entire stack of data these interfaces. The Stack class defaults to the head of the array as the bottom of the Stack and the tail as the top.

1.1 into the stackpush

You can use the JS array push method to push data into the end of the array.

Stack.prototype = {
    push: function(value){
        return this.space.push(value); }}Copy the code

1.2 the stackpop

Out of the stack is also the use of JS array pop method, at the end of the array to push data.

Stack.prototype = {
    pop: function(){
        return this.space.pop(); }}Copy the code

1.3 empty stackclear

Emptying the stack is relatively simple, simply resetting the array storing the data to an empty array.

Stack.prototype = {
    clear: function(){
        this.space = []; }}Copy the code

1.4 Reading top of stackreadTop

Read the data on the top of the stack, using the array subscript way to obtain. As a bonus, undefined is returned when the subscript is outside the valid range of the array.

Stack.prototype = {
    readTop: function(){
        return this.space[this.space.length - 1]; }}Copy the code

1.4 Reading the entire stackread

Read the entire stack and return the current array.

Stack.prototype = {
    read: function(){
        return this.space; }}Copy the code

1.5 the aggregation

Finally, after all the functionality is aggregated, as shown below, you have a stack of data structures.

function Stack(){
    this.space = [];
}

Stack.prototype = {
    constructor: Stack,
    push: function(value){
        return this.space.push(value);
    },
    pop: function(){
        return this.space.pop();
    },
    clear: function(){
        this.space = [];
    },
    readTop: function(){
        return this.space[this.space.length - 1];
    },
    read: function(){
        return this.space; }};Copy the code

Second, the actual combat

Learning data structures and algorithms is to solve engineering problems better and more efficiently. Here are a few real examples of how data structures and algorithms work 🙂

2.1 an arrayreverseThe implementation of the

In this case, the stack will be used to reverse the array.

function reverse(arr){
    var ArrStack = new Stack();

    for(var i = arr.length - 1; i >= 0; i--){
        ArrStack.push(arr[i]);
    }

    return ArrStack.read();
}
Copy the code

As shown in the code, it can be divided into the following steps:

• Instantiate a stack to store data
• The incoming arrays are traversed in reverse order and pushed onto the stack one by one
• Finally usingreadInterface, output data

It seems very simple, don’t worry about it, the complexity comes later 🙂

2.2 Converting decimal to binary

The problem of numerical conversion to base is a small test of the stack. To explain the conversion method, let’s take a quick example:

Convert the decimal 13 to binary

    2 | 13      1￣ ￣ ￣2 |  6      0￣ ￣ ￣2 |  3      1￣ ￣ ￣ ￣1      1
Copy the code

As shown above: the binary code of 13 is 1101. To turn the manual conversion into stack storage, just push the results of mod 2 onto the stack and save, and finally reverse the output.

function binary(number){
    var tmp = number;
    var ArrStack = new Stack();

    if(number === 0) {return 0;
    }

    while(tmp){
        ArrStack.push(tmp % 2);
        tmp = parseInt(tmp / 2.10);
    }

    return reverse(ArrStack.read()).join(' ');
}

binary(14); // Output => "1110"
binary(1024); // Output => "10000000000"
Copy the code

2.3 Expression evaluation

This case can be interpreted as a simplified eval method. This is the evaluation of 1 plus 7 times 4 minus 2.

Before entering the subject, it is necessary to understand the following mathematical theories:

1. Infix notation (or infix notation) is a general representation of an arithmetic or logical formula in which the operators are infix form in the middle of the operands (e.g. 3 + 4).
2. Reverse Polish notation (RPN, or Reverse Polish notation) is a mathematical notation system introduced by Polish mathematician Jan Vukasiewicz in 1920. In Reverse Polish notation, all the operators are placed after the operands. It is also called postfix notation. Inverse polish notation does not require parentheses to identify the precedence of the operator. The regular infix “3-4 + 5” is written as “3 4-5 +” in inverse Polish notation.
3. Shunting Yard Algorithm is a classical Algorithm for converting infix expressions into suffixes. It was introduced by Eziger Dijkstra and named for its operation similar to train marshals.

To be clear, this is just a simple implementation. So there are two rules:

1. The number must be an integer
2. Redundant whitespace is not allowed in expressions

The implementation code is as follows:

function calculate(exp){
    var valueStack = new Stack(); / / value stack
    var operatorStack = new Stack(); // operator stack
    var expArr = exp.split(' '); // Cut the string expression
    var FIRST_OPERATOR = ['+'.The '-']; // Add and subtract operators
    var SECOND_OPERATOR = [The '*'.'/']; // The multiplication and division operator
    var SPECIAL_OPERATOR = ['('.') ']; / / brackets
    var tmp; // Temporarily store the currently processed characters
    var tmpOperator; // Temporarily store the current operator

    // iterate over the expression
    for(var i = 0, len = expArr.length; i < len; i++){
        tmp = expArr[i];
        switch(tmp){
            case '(':
                operatorStack.push(tmp);
                break;
            case ') ':
                // When a close parenthesis is encountered, the data inside the parenthesis is pushed first
                while( (tmpOperator = operatorStack.pop()) ! = ='(' && 
                    typeoftmpOperator ! = ='undefined' ){
                    valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
                }
                break;
            case '+':
            case The '-':
                while( typeofoperatorStack.readTop() ! = ='undefined' && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === - 1&& (SECOND_OPERATOR.indexOf(operatorStack.readTop()) ! = =- 1|| tmp ! = operatorStack.readTop()) ){// The top of the stack is multiplication, division or the same priority operation
                    valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            case The '*':
            case '/':
                while( typeofoperatorStack.readTop() ! ='undefined' && 
                    FIRST_OPERATOR.indexOf(operatorStack.readTop()) === - 1 && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === - 1&& tmp ! = operatorStack.readTop()){// The top of the stack is the same priority operation, first out of the stack
                    valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            default: valueStack.push(tmp); }}// Handle stack data
    while( typeof(tmpOperator = operatorStack.pop()) ! = ='undefined' ){
        valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
    }

    return valueStack.pop(); // Deduce the calculated result

    /* @param operator @param initiativeNum Active value @param passivityNum Passive value */
    function calculator(operator, passivityNum, initiativeNum){
        var result = 0;

        initiativeNum = typeof initiativeNum === 'undefined' ? 0 : parseInt(initiativeNum, 10);
        passivityNum = typeof passivityNum === 'undefined' ? 0 : parseInt(passivityNum, 10);

        switch(operator){
            case '+':
                result = initiativeNum + passivityNum;
                console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
                break;
            case The '-':
                result = initiativeNum - passivityNum;
                console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
                break;
            case The '*':
                result = initiativeNum * passivityNum;
                console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
                break;
            case '/':
                result = initiativeNum / passivityNum;
                console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
                break;
            default:;
        }

        returnresult; }}Copy the code

Implementation idea:

1. usingScheduling field algorithm, read the infix expression, and perform reasonable operation on the result.
2. Critical point adoptionoperatorStack.readTop() ! == 'undefined'Make a decision. Some books use#Personally, IT’s a bit of a drag.
3. Use the string expressionsplitSplit it, then read it through and push it onto the stack. There are results to be calculated in advance, the corresponding stack processing.
4. Encapsulate a method for calculating partial results into a separate methodcalculator. Because the numbers before and after the multiplication and division operators are different in the operation, they cannot be arbitrarily swapped.

2.4 Conversion of Infix Expressions to Postfix Expressions (Inverse Polish notation)

Inverse Polish notation is a computer-friendly notation that does not require the use of parentheses. The following case is a workaround of the previous case, and also uses the scheduling field algorithm to convert infix expression into suffix expression.

function rpn(exp){
    var valueStack = new Stack(); / / value stack
    var operatorStack = new Stack(); // operator stack
    var expArr = exp.split(' ');
    var FIRST_OPERATOR = ['+'.The '-'];
    var SECOND_OPERATOR = [The '*'.'/'];
    var SPECIAL_OPERATOR = ['('.') '];
    var tmp;
    var tmpOperator;

    for(var i = 0, len = expArr.length; i < len; i++){
        tmp = expArr[i];
        switch(tmp){
            case '(':
                operatorStack.push(tmp);
                break;
            case ') ':
                // When a close parenthesis is encountered, the data inside the parenthesis is pushed first
                while( (tmpOperator = operatorStack.pop()) ! = ='(' && 
                    typeoftmpOperator ! = ='undefined' ){
                    valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
                }
                break;
            case '+':
            case The '-':
                while( typeofoperatorStack.readTop() ! = ='undefined' && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === - 1&& (SECOND_OPERATOR.indexOf(operatorStack.readTop()) ! = =- 1|| tmp ! = operatorStack.readTop()) ){// The top of the stack is multiplication, division or the same priority operation
                    valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            case The '*':
            case '/':
                while( typeofoperatorStack.readTop() ! ='undefined' && 
                    FIRST_OPERATOR.indexOf(operatorStack.readTop()) === - 1 && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === - 1&& tmp ! = operatorStack.readTop()){// The top of the stack is the same priority operation, first out of the stack
                    valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            default: valueStack.push(tmp); }}while( typeof(tmpOperator = operatorStack.pop()) ! = ='undefined' ){
        valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
    }

    return valueStack.pop(); // Deduce the calculated result

    /* @param operator @param initiativeNum Active value @param passivityNum Passive value */
    function translate(operator, passivityNum, initiativeNum){
        var result = ' ';

        switch(operator){
            case '+':
                result = `${initiativeNum} ${passivityNum}+ `;
                console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
                break;
            case The '-':
                result = `${initiativeNum} ${passivityNum}- `;
                console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
                break;
            case The '*':
                result = `${initiativeNum} ${passivityNum}* `;
                console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
                break;
            case '/':
                result = `${initiativeNum} ${passivityNum}/ `;
                console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
                break;
            default:;
        }

        return result;
    }
}

rpn('1 + 7 * (4 - (2)'); // Output => "1 7 4 2 - * +"
Copy the code

2.5 Hanoi

Hannott Tower is A mathematical problem formed according to A legend: there are three poles A, B and C. Rod A has N (N>1) perforated disks, the size of the disk from bottom to top decreasing. All disks are required to be moved to C rod according to the following rules:

1. You can only move one disk at a time;
2. The large plate cannot be piled on top of the small plate.

The classical application of stack algorithm, the first is hannott tower.

To understand the algorithm, note the following:

1. Don’t delve into every movement, understand it abstractly
2. Step 1: All disks that do not meet the requirements are moved from Tower A to the cache in Tower B
3. Step 2: Move the matching disk to tower C
4. Step 3: Move all disks cached in Tower B to Tower C

Here is the code implementation:

var ATower = new Stack(); / / A tower
var BTower = new Stack(); / / B tower
var CTower = new Stack(); // C tower
var TIER = 4; / / layer

for(var i = TIER; i > 0; i--){
    ATower.push(i);
}

function Hanoi(n, from, to, buffer){
    if(n > 0){
        Hanoi(n - 1.from, buffer, to);  // All disks (n-1) that do not meet the requirements are moved from Tower A to the cache in Tower B
        to.push(from.pop()); // Move the matching disk (n) to tower C
        Hanoi(n - 1, buffer, to, from); // Move all disks cached in tower B to tower C
    }
}

Hanoi(ATower.read().length, ATower, CTower, BTower);
Copy the code

Hannotta’s emphasis, again, is on recursion. Take a big problem, recursively, and keep breaking it down into smaller problems. Then, focus on solving small problems.

Third, summary

Somehow, it’s a little too much ORZ. References to later chapters are recommended. Perhaps with this article, you will have a better understanding.

reference

[1] Infix notation [2] suffix notation [3] Scheduling field algorithm [4] Hannott tower

---

Friends who like my articles can follow me in the following ways:

• “Star” or “watch” my GitHub blog
• RSS subscribe to my personal blog:Mr. Wang’s base