Basic concepts of stacks

A stack is an ordered collection that follows LIFO. New elements added or to be removed are stored at the same end of the stack, called the top, and the other end is called the bottom. In the stack, the new elements are near the top of the stack, and the old elements are near the bottom of the stack.

Stacks are also used in programming language compilers and in memory to hold variables, method calls, and so on. The structure is shown in the figure below:

The stack structure is self-fulfilling

Implement a stack structure:

In accordance with the last in, first out principle, you need to restrict the function of inserting and deleting data.

Methods need to be implemented:

Push (eles) : Adds one or more elements to the top of the stack

Pop: Removes the element currently at the top of the stack and returns the removed element

Peek: Returns the element at the top of the stack without making any changes to the stack itself

IsEmpty: checks whether the stack isEmpty, returns true if there is nothing in the stack, false otherwise

Size: Returns the number of elements in the stack, similar to the length property of an array

Clear: Removes all elements in the stack

For of: Iterator interface that implements the stack structure

The code is as follows:

class Stack{ / / the stack class
    constructor(){
        this.count = 0; // The stack counter is used to count the number of elements inside the stack
        this.items = {}; // The actual data is stored in this object
    }
    
    push(. eles){ // Add one or more elements to the top of stack
        for(let i = 0, len = eles.length; i < len; i++){
            this.items[this.count] = eles[i]; 
            // Use the current value of the counter (a natural number from 0 to infinity) as the subscript key to store the actual data corresponding to the subscript
            The reason we use this.count instead of I in this.items is because I starts at 0 again when the next for loop starts
            
            this.count++; // Every time a data is pushed, the counter increases by 1}}size(){ // Returns the number of elements in the stack, similar to the length property of an array
        return this.count;
    }
    
    isEmpty(){ // Check whether the stack is empty
        return !this.count;
    }
    
    pop(){ // Remove the element currently at the top of the stack, and return the removed element
        if(this.isEmpty){ // Delete the content
           return undefined; // If the stack itself is empty, return undefined
        }
        this.count--; 
        // The index starts at 0 and the counter starts at 1, so the counter decrement by 1 gives the key at the top of the stack
        let result = this.items[this.count]; // Use a variable to hold the value that needs to be returned to the top of the stack
        delete this.items[this.count]; // Delete the top value of the stack
        return result;
    }
    
    peek(){ // Returns the element at the top of the stack without modifying the stack itself
        if(this.isEmpty()){ // Delete the content
           return undefined; // If the stack itself is empty, return undefined
        }
        return this.items[this.count - 1]; // Returns the current element at the top of the stack
    }
    
    clear(){
        while(!this.isEmpty()){ // Empty the stack only when it is not empty
            this.pop() // Try to implement other functions in the same way as you have already implemented them}}toString(){ // Output all contents of the stack as a string
        if(this.isEmpty()){ // Check whether it is null
           return ""; // If the stack itself is empty, return ""
        }
        let resultString = ""; // Define a result string, default is empty string
        for(let i = 0; i < this.count; i++){
            resultString = `${resultString}.The ${this.itmes[i]}`; // String concatenation is done for each loop
        }
        return resultString.slice(1); 
        // Because the first concatenation is empty string and element concatenation, we need to remove the comma left after the first concatenation
    }
    
    forEach(cb){ // Implement the forEach interface
        for(let i = 0; i < this.count; i++){
            cb(i, this.items[i], this); }} [Symbol.iterator](){ // Manually add the iterator interface to the stack
        let self = this;
        let index = 0;
        return {
            next(){
                if(index < self.count){ // If the index of the currently traversed element is less than this.count, the traversal is not complete
                    return {
                    	value: self.items[index++],
                    	done: false}}else{ // Otherwise, the traversal is complete
                    return {
                    	value: undefined.done: true
                	}
                }
            }
        }
    }
}

let arr = new Stack();
arr.push("hello") / / add value
arr.push("world")
arr.push("Hello"."Have you eaten?")
arr.peek() // Get the top of the stack
arr.pop() // Delete one
arr.size() // Get the length
arr.isEmpty() // Check whether it is null
arr.toString() // Outputs a string
for(let val of arr){
    console.log(val);
}
arr.forEach(function(index,item,arr){
    console.log({index,item});
})
arr.clear() / / to empty
Copy the code

Application of stack structure in algorithm

Base conversion:

Binary to decimal

For example: binary 1010, split it into

10 10 => 1×2 ^ 3 + 0×2 ^ 2 + 1×2 ^ 1 + 0×2 ^ 0 = 8 + 0 + 2 + 0 =10

So 1010 in binary is 10 in decimal

Decimal to binary

For example, 10 in decimal,

10/2 is 5, remainder is 0;

5/2=2, remainder 1;

2/2 is 1, remainder is 0;

1/2 is 0, remainder is 1;

The numbers are then pieced together backwards to form a binary 1010

The code is as follows:

// Import the stack structure you just implemented
class Stack{ / / the stack class
    constructor(){
        this.count = 0; // The stack counter is used to count the number of elements inside the stack
        this.items = {}; // The actual data is stored in this object
    }
    
    push(. eles){ // Add one or more elements to the top of stack
        for(let i = 0, len = eles.length; i < len; i++){
            this.items[this.count] = eles[i]; 
            // Use the current value of the counter (a natural number from 0 to infinity) as the subscript key to store the actual data corresponding to the subscript
            The reason we use this.count instead of I in this.items is because I starts at 0 again when the next for loop starts
            
            this.count++; // Every time a data is pushed, the counter increases by 1}}size(){ // Returns the number of elements in the stack, similar to the length property of an array
        return this.count;
    }
    
    isEmpty(){ // Check whether the stack is empty
        return !this.count;
    }
    
    pop(){ // Remove the element currently at the top of the stack, and return the removed element
        if(this.isEmpty){ // Delete the content
           return undefined; // If the stack itself is empty, return undefined
        }
        this.count--; 
        // The index starts at 0 and the counter starts at 1, so the counter decrement by 1 gives the key at the top of the stack
        let result = this.items[this.count]; // Use a variable to hold the value that needs to be returned to the top of the stack
        delete this.items[this.count]; // Delete the top value of the stack
        return result;
    }
    
    peek(){ // Returns the element at the top of the stack without modifying the stack itself
        if(this.isEmpty()){ // Delete the content
           return undefined; // If the stack itself is empty, return undefined
        }
        return this.items[this.count - 1]; // Returns the current element at the top of the stack
    }
    
    clear(){
        while(!this.isEmpty()){ // Empty the stack only when it is not empty
            this.pop() // Try to implement other functions in the same way as you have already implemented them}}toString(){ // Output all contents of the stack as a string
        if(this.isEmpty()){ // Check whether it is null
           return ""; // If the stack itself is empty, return ""
        }
        let resultString = ""; // Define a result string, default is empty string
        for(let i = 0; i < this.count; i++){
            resultString = `${resultString}.The ${this.itmes[i]}`; // String concatenation is done for each loop
        }
        return resultString.slice(1); 
        // Because the first concatenation is empty string and element concatenation, we need to remove the comma left after the first concatenation
    }
    
    forEach(cb){ // Implement the forEach interface
        for(let i = 0; i < this.count; i++){
            cb(i, this.items[i], this); }} [Symbol.iterator](){ // Manually add the iterator interface to the stack
        let self = this;
        let index = 0;
        return {
            next(){
                if(index < self.count){ // If the index of the currently traversed element is less than this.count, the traversal is not complete
                    return {
                    	value: self.items[index++],
                    	done: false}}else{ // Otherwise, the traversal is complete
                    return {
                    	value: undefined.done: true
                	}
                }
            }
        }
    }
}

// Convert from decimal to binary
function decimalToBinary(decNumber){
    let remStack = new Stack(); // Define a stack to store the remainder
    let number = decNumber; // Stores the passed decimal argument
    let rem; / / remainder
    let binaryString = ""; // Store the converted binary data string
    
    while(number > 0) {// As long as the number is greater than 0, divide by 2 for remainder
        rem = Math.floor(number % 2); // Take the remainder first
        remStack.push(rem); // add the remainder to the stack
        number = Math.floor(number / 2); // After each remainder, divide the original decimal number by 2 to get the new decimal number
    }
    
    while(! remStack.isEmpty){// As long as the stack storing the remainder is not empty
        binaryString += remStack.pop().toString(); // Take the remainder and convert it to a string format
    }
    
    return binaryString; // Finally return
}

decimalToBinary(10); // Execute this function
Copy the code

Hanoi:

Let’s take a look at the specific moving steps:

Different states: State 1: When the first post has only one slider, move the first slider directly to the third post

State 2: When the first post has more than one slider, all the sliders except the bottom one are moved to the second post, which becomes state 1.

Then, the slider on the second post is regarded as a new move. At this time, the slider on the post is in two states, that is, either state 1 or state 2.

If it is in state 1, move the only slider of the first pillar directly to the third pillar; If it’s state 2, when there’s more than one slider on the first post, move all the sliders except the bottom one to the second post, and it becomes state 1, and so on.

The code is as follows:

// Use recursive methods
function hanoi(plates, A, B, C, moves = []){ // Number of sliders, A column, B column, C column, storage step result array
    if(plates <= 0) {// There is no slider on the column
        return moves; // Return the result array directly
    }
    if(plates === 1) {// State 1, with only one slider
        moves.push([A,"挪到",C]); // Move the slider from column A to column C and store this step into the result array moves
        
    }else{ // If state 2 has more than one slider, consider it a new move
        hanoi(plates - 1, A, C, B, moves); // recursive call
        / / remove the bottom one slider, because the slider to move to B pillar, so the destination has changed, the incoming parameters also want to change for A, C, B,
        // Add the array moves from the previous stored steps to the move, which then returns to state 1 after the move
        
        moves.push([A,"挪到",C]); 
        // Since this is state 1 again, move the slider from column A to column C and store this step in the result array moves
        
        // The slider from pillar B should be moved to pillar C. The slider from pillar B should be moved to pillar C
        hanoi(plates - 1, B, A, C, moves); // recursive call
    }
    return moves; // Finally returns the result array
}

console.log(hanoi(3."The first Pillar"."The second pillar"."The Third Pillar"))
Copy the code

This is the first time to send an article, if there are mistakes, I hope you can help point out.