Detailed explanation of JavaScript data structure and algorithm stack_javascript skills

In the previous article the blog introduced the following list. The list is the simplest structure, but if you want to deal with some more complex structures, the list is too simple, so we need some kind of and Lists are similar to but more complex data structures - stacks. The stack is an efficient data structure because data can only be added or deleted at the top of the stack, so this operation is fast and easy to implement.

1: Operations on the stack.

The stack is a special kind of list. The elements in the stack can only be accessed through one end of the list, which is the top of the stack. For example, when washing dishes in a restaurant, you can only wash the top plate first. After the plate is washed, it can only be screwed to the top of the pile of plates. The stack is a data structure called "last in, first out" (LIFO).

Since the stack has the last-in-first-out characteristic, any element that is not at the top of the stack cannot be accessed. In order to get the element at the bottom of the stack, the element above must be removed first. The two main operations we can perform on the stack are pushing an element onto the stack and popping an element off the stack. We can use the push() method to push into the stack, and the pop() method to pop out of the stack. Although the pop() method can access the element on the top of the stack, after calling this method, the element on the top of the stack is permanently deleted from the stack. Another commonly used method is peek(), which only returns the top element of the stack without deleting it.

The actual diagram of pushing and popping onto the stack is as follows:

push(), pop() and peek() are the three main methods of the stack, but the stack has other methods and properties. As follows:

clear(): Clear all elements in the stack.

length(): Record the number of elements in the stack.

2: The implementation of the stack is as follows:

We can start by implementing the methods of the stack class; as follows:

Copy code The code is as follows:

function Stack() {
This.dataStore = [];
This.top = 0;
}

As above: dataStore saves all elements in the stack. The variable top records the position of the top of the stack and is initialized to 0. It means that the starting position of the array corresponding to the top of the stack is 0, if an element is pushed onto the stack. The variable value will change accordingly.

We also have the following methods: push(), pop(), peek(), clear(), length();

1. Push() method; when pushing a new element into the stack, it needs to be saved in the position corresponding to the variable top in the array, and then the top value is increased by 1 to point to the next position in the array. The following code:

Copy code The code is as follows:

function push(element) {
This.dataStore[this.top] = element;
}

2. The pop() method is the opposite of the push() method---it returns the top element of the stack and decrements the top value by 1. The following code:

Copy code The code is as follows:

function pop(){
         return this.dataStore[--this.top];
}

3. The peek() method returns the element at the top-1 position of the array, which is the top element of the stack;

Copy code The code is as follows:

Function peek(){
          return this.dataStore[this.top - 1];
}

4. length() method Sometimes we need to know how many elements there are in the stack. We can return the number of elements in the stack by returning the value of the variable top, as shown in the following code:

Copy code The code is as follows:

Function length(){
           return this.top;
}

5. clear(); Sometimes we want to clear the stack, we set the variable top value to 0; the following code:

Copy code The code is as follows:

function clear() {

this.top = 0;

}

All codes below:

Copy code The code is as follows:

function Stack() {
This.dataStore = [];
This.top = 0;
}

Stack.prototype = {
 
//Push a new element into the stack
Push: function(element) {
This.dataStore[this.top] = element;
},
// Access the top element of the stack, the top element of the stack is permanently deleted
pop: function(){
          return this.dataStore[--this.top];
},
// Return the element at the top-1 position in the array, that is, the top element of the stack
peek: function(){
          return this.dataStore[this.top - 1];
},
//How many elements are stored in the stack
length: function(){
         return this.top;
},
//Clear the stack
; clear: function(){
This.top = 0;
}
};

The demo example is as follows:

var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c

var popped = stack.pop();
console.log(popped); // c

console.log(stack.peek()); // b

stack.push("d");

console.log(stack.peek()); // d

stack.clear();

console.log(stack.length()); // 0

console.log(stack.peek()); // undefined

Below we can implement a recursive definition of the factorial function; such as 5! The factorial of 5! = 5 * 4 * 3 * 2 * 1;

The following code:

Copy code The code is as follows:

function fact(n) {
var s = new Stack();
; while(n > 1) {
s.push(n--);
}
var product = 1;
While(s.length() > 0) {
Product *= s.pop();
}
Return product;
}
console.log(fact(5));

The meaning of the above code is: first pass the number 5 into the function, use a while loop, and push the function push() using the stack into the stack before decrementing it by 1 each time until the variable n is less than 1. Then define a variable product; use the length() method of the stack to determine whether it is greater than 0 and execute product* = s.pop() each time; the pop() method returns the top element of the stack and deletes the element from the stack. So each time it is executed, one element is deleted until s.length() <= 0. So product = 5*4*3*2*1 . and other operations.