Data structures and algorithms in JavaScript (1): stack_javascript skills

Preface

Data Structures and Algorithms JavaScript is a book that explains it in a relatively simple way. The advantage is that it uses JavaScript language to describe commonly used data structures. Many examples in the book come from common interview questions, which can be regarded as keeping pace with the times. , I watched it as an amateur and recorded it by the way

git code download: https://github.com/JsAaron/data_structure.git

Stack structure

Special list, the elements in the stack can only be accessed through one end of the list, the top of the stack

Last-in-first-out (LIFO, last-in-first-out) data structure

Javascript provides operable methods, push and pop, but pop will remove the data in the stack

An implementation class that implements a stack

The underlying data structure uses arrays

Because pop deletes the data in the stack, you need to implement a search method peek

Implement a cleaning method clear

Find the total number of elements in the stack length

Check if there is still element empty

Copy code The code is as follows:

function Stack(){
This.dataStore = []
This.top = 0;
This.push = push
This.pop = pop
This.peek = peek
This.length = length;
}

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

function peek(element){
Return this.dataStore[this.top-1];
}

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

function clear(){
This.top = 0
}

function length(){
Return this.top
}

Palindrome

A palindrome refers to a word, array, or phrase that is the same from front to back 12321.abcba

The simplest idea of ​​a palindrome is that if the element is reversed and equal to the original element, it means that it is a palindrome

You can use this stack class to operate here

Copy code The code is as follows:

function isPalindrome(word) {
var s = new Stack()
for (var i = 0; i < word.length; i ) {
s.push(word[i])
}
var rword = "";
while (s.length() > 0) {
         rword = s.pop();
}
If (word == rword) {
        return true;
} else {
         return false;
}
}

isPalindrome("aarra") //false
isPalindrome("aaraa") //true

Look at this isPalindrome function. It actually calls the Stack class, and then pushes the word element passed in to each decomposed unit into the stack. According to the principle of the stack, the principle of last in, first out , use the pop method to disassemble this element, and finally compare the before and after assembly. If they are equal, it is a palindrome

Recursion

Use recursion to implement a factorial algorithm

5! = 5 * 4 * 3 * 2 * 1 = 120

Use recursion

Copy code The code is as follows:

function factorial(n) {
If (n === 0) {
Return 1;
} else {
          return n * factorial(n - 1);
}
}

Use stack operations

Copy code The code is as follows:

function fact(n) {
var s = new Stack()
while (n > 1) {
              //[5,4,3,2]
s.push(n--);
}
var product = 1;
while (s.length() > 0) {
Product *= s.pop();
}
Return product;
}

fact(5) //120

Push n = 5 decrementally onto the stack through while, and then through a loop or according to the last-in-first-out principle of the stack, take out the frontmost one and stack it with the product through the pop method