In the previous blog, I introduced the following list. List is the simplest structure, but if you want to deal with some more complex structures, the list looks too simple, so we need some data structure similar to the list but more complex - the stack. 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 very fast and easy to implement.
1: Operation on the stack.
A stack is a special list. The elements in the stack can only be accessed through one end of the list, and this end is the top of the stack. For example, when washing dishes in a restaurant, you can only wash the top plate first. After washing the dishes, you can only snail the top of the stack of dishes. The stack is called a "late-in-first-out" (LIFO) data structure.
Since the stack has the characteristics of back-in, first-out, no element that is not at the top of the stack cannot be accessed. In order to obtain elements with low stack, the above element must be removed first. The two main operations we can do with the stack are to push an element onto the stack and pop an element onto the stack. When entering the stack, we can use the method push() method, and when we put it on, we can use the pop() method. Although the pop() method can access the elements at the top of the stack, after calling the method, the elements at the top of the stack are permanently deleted from the stack. Another method we use is peek(), which returns only the top element of the stack without deleting it.
The actual column diagrams of stack entry and stack exit are 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.
Two: The implementation of the stack is as follows:
We can start by implementing the stack class method first; as follows:
The code copy 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 at the top of the stack and is initialized to 0. It means that the starting position of the corresponding array on the top of the stack is 0, if any element is pushed into the stack. The value of this variable 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 array corresponding to the variable top, and then the top value is increased by 1, so that it points to the next position in the array. The following code:
The code copy is as follows:
function push(element) {
this.dataStore[this.top++] = element;
}
2. The pop() method is opposite to the push() method -- it returns the top element and deducts the top value by 1. The following code:
The code copy 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, that is, the top-1 element of the stack;
The code copy 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 variable top value, as shown in the following code:
The code copy is as follows:
function length(){
return this.top;
}
5. clear(); Sometimes we want to clear the stack, and we set the top value of the variable to 0; the following code:
The code copy is as follows:
function clear() {
this.top = 0;
}
All codes below:
The code copy is as follows:
function Stack() {
this.dataStore = [];
this.top = 0;
}
Stack.prototype = {
// Press 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];
},
// Returns the element at 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;
}
};
Examples of demos are 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 a factorial function; for example, 5! Factorial 5! = 5 * 4 * 3 * 2 * 1;
The following code:
The code copy 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 above code means: first pass the number 5 into the function, use a while loop, and before decrementing 1 each time, push() of the function you use to the stack until the variable n is less than 1. Then define a variable product; determine whether it is greater than 0 by the length() method of the stack, and each time the product* = s.pop() method is executed, the pop() method returns the top element of the stack and deletes the element from the stack. So each time you execute, delete an element until s.length() <= 0. So product = 5*4*3*2*1. etc.