The front end and stack of data structures and algorithms

preface

Data structures and algorithms are one of the biggest challenges in the front-end, or in the technology world at large, in terms of technology advancement and salary growth. However, any problem, when you are going to carefully look and carefully to implement a, it is not as difficult as you think. I am also a rookie on the way, this blog is my study notes, the content of which I will be based on “Data structure and Algorithm JavasCript description”, will learn from some of the concepts. I can’t figure out the definition of the concept out of thin air, but the implementation code inside can be implemented in their own way, because I see that most of the content is achieved by ES5, the author prefers to use ES6 to achieve.

Introduction to the stack (what is a stack)

A stack is a special kind of list in which the elements are accessible through one end of the list, called the top of the stack.

The characteristics of the stack

A stack is a last-in, first-out data structure. Since the stack is last-in, first-out, any element that is not at the top of the stack cannot be accessed. To get to the bottom of the stack, you have to remove the top element.

Stacks in real life

A stack of dishes when washing dishes. You can only take dishes from the top, and when they’re clean, you can only stack them on top of the same pile.

The operation of the stack

The two main operations on the stack are pushing an element onto the stack and pushing an element off the stack.

The realization of the stack

1. Implementation approach

Push method is used for pushing and POP method is used for pushing. You need a peek method to preview the top of the stack element that only returns the top of the stack without removing it. The pop method can access the top element, but when it is called, the top element is permanently removed from the stack. Using the top variable to hold the position at the top of the stack, we need to use the length method to get the number of elements in the entire stack. Finally, a clear method is required to clear all elements in the stack.

2. Self-implementation requires a special requirement to be satisfied (this point is self-added)

The following design principles should be met: 1. Open and closed principle: open to expansion and closed to modification; 2. 2. Single responsibility principle: Implementation class should have single responsibility; In fact, there are three other design principles, because js syntax limits the use of the other three design principles, so for the moment to satisfy these two design principles. 3. Implementation

class Stack { constructor() { this.arr = []; this.top = 0; } // push(item) {this.arr[this.top++] = item; } pop() {return this.arr[--this.top]; } // preview stack top peek() {return this.arr[this.top-1]; } // stack number of elements length() {return this.top; } // clear stack clear() {this.top = 0; }}Copy the code

4. Data structure validation

const S = new Stack(); console.log(S.length()); //0 s.ush ("王二"); Supachai panitchpakdi ush (" * * "); Supachai panitchpakdi ush (" li si "); console.log(S.length()); // 3 console.log(S.peek()); / / li si's op (); console.log(S.length()); // 2 console.log(S.peek()); / / zhang SAN S.c Lear (); console.log(S.length()); // 0 console.log(S.peek()); // undefinedCopy the code

To sum up: The fifo data structure is basically enough to access the top of the stack. The single responsibility principle in the design pattern applies both to methods in this class and to the class as a whole. Each function in the class does only one thing.

The deficiency lies in: did not satisfy the open and closed principle

5. Open and closed principle verification:

const S = new Stack(); S.length = function() { return this.top - 10; } console.log(S.length); ƒ () {return this.top-10; } // This print shows that the original length method has been modified, so it does not meet the open and closed principleCopy the code

6. To be modified according to the open and closed principle:

Const S = function () {return new Stack(); }; S.length = function() { return this.top - 10; } console.log(S().length); ƒ length() {return this.top; } // open to extensions. A = 10; console.log(S.a); // 10 // It can be seen that the original length method has not been modified, then the modification is closedCopy the code

7. Problems with this writing:

In general, we only pay attention to whether its data structure meets the characteristics of first-in, first-out, and do not pay attention to the internal values. But because I wanted to see what each method was doing, I got the exact value of the arR once, and what I didn’t expect was the exact value of the ARR and the way I wrote it, even if I went out of the stack, the element would still be in there, and the reason is because I only changed the top value, the array didn’t change anything. I’ll just show you the printout

class Stack { constructor() { this.arr = []; this.top = 0; } // push(item) {this.arr[this.top++] = item; } pop() {return this.arr[--this.top]; } // preview stack top peek() {return this.arr[this.top-1]; } // stack number of elements length() {return this.top; } // clear stack clear() {this.top = 0; } getStack() {return this.arr; } } const S = new Stack(); console.log(S.length()); Supachai panitchpakdi ush (" two "); Supachai panitchpakdi ush (" * * "); Supachai panitchpakdi ush (" li si "); console.log(S.length()); console.log(S.peek()); S.pop(); console.log(S.length()); console.log(S.peek()); S.clear(); console.log(S.length()); console.log(S.peek()); console.log(S.getStack()); // [" wang 2 ", "Zhang 3 "," Li 4 "]Copy the code

8. Rewriting of methods:

class Stack { constructor() { this.arr = []; } push(item) { this.arr.push(item); } pop() { return this.arr.pop(); } peek() { return this.arr[this.arr.length - 1]; } length() { return this.arr.length; } clear() { this.arr = []; } getStack() { return this.arr; } } const S = new Stack(); console.log(S.length()); // 0 s.ush ("王二"); Supachai panitchpakdi ush (" * * "); Supachai panitchpakdi ush (" li si "); console.log(S.length()); //3 console.log(S.peek()); / / li si's op (); console.log(S.length()); // 2 console.log(S.peek()); S.clear(); console.log(S.length()); / / zhang SAN console. The log (supachai panitchpakdi eek ()); // 0 console.log(S.getStack()); / / []Copy the code

Note: Normally we don’t care about all the elements on the stack, but the latter approach is more rigorous. And the second one comes from thinking about the problems with the first one, from any video or book.

9. Why use pop to remove elements instead of DELETE?

class Stack { constructor() { this.arr = []; } push(item) { this.arr.push(item); } del() { delete this.arr[this.arr.length-1]; } peek() { return this.arr[this.arr.length - 1]; } length() { return this.arr.length; } clear() { this.arr = []; } getStack() { return this.arr; } } const S = new Stack(); Supachai panitchpakdi ush (" * * "); S.del(); console.log(S.getStack()); //[empty]Copy the code

1. Delete deletes the value of the current array location, but leaves an empty space, the length of the array unchanged, that is, the empty space, similar to a placeholder.
2. This method also needs to return the deleted value, and the delete won’t do the trick either

Application scenarios (what problems can the stack solve)?

1. Base conversion of numbers:

Concept supplement: in general, a number is removed to the base to be converted, and the remaining numbers are output in reverse order and the corresponding representation of the base in time. Here is a schematic diagram:

Using the idea of stack to solve the problem, divide the number and the base, the rest of the number in turn into the stack first, and then the elements in the stack out of the stack in turn, you can get the correct result. Solutions are as follows:

Function mulBase(num, base) {do {s.ush (num % base); function mulBase(num, base) {do {s.ush (num % base); num = Math.floor(num / base); } while(num > 0); let str = ''; while (S.length() > 0) { str += S.pop(); } return +str; } console.log(mulBase(6, 2)); / / 110Copy the code

The space is O(n), the time is O(n).

2. factorial

What is factorial?

10! = 10*9*8*7*6*5*4*3*2*1 // This is the factorial of 10Copy the code

Do it recursively

function fn(n) { if(n === 0) { return 1; } else { return n * fn(n - 1); } } console.log(fn(3)); / / 6 = > 3 * 2 * 1Copy the code

Implementation in ES6:

function fn(n) { let num = n; for(let i = n - 1; i > 0; i--) { num *= i; } return num; } console.log(fn(3)); / / 6 = > 3 * 2 * 1Copy the code

Note: Due to the precision limitation of js numerical calculation, the factorial of 70 and above cannot be calculated, but es6 has large integers to solve this problem, there is no restriction on the number of digits. By the way, check out my NUGGETS ES6 blog for details. I won’t go into details here.

Use a stack to implement:

function fn(n) { const S = new Stack(); for(let i = 1; i <= n; i++) { S.push(i); } let num = 1; let len = S.length(); for(let i = 0; i < len; i++) { num *= S.pop(); } return num; } console.log(fn(3)); / / 6 = > 3 * 2 * 1Copy the code

The space is O(n), the time is O(n).

3. Palindrome:

Palindrome definition: a string of text that looks exactly the same whether read from left to right or right to left.

Use stack solution idea: the text in turn into the stack, and then pop up the stack, after the stack of the text string up just the opposite with the original text!

Const STR = "Fan can fan "; function isPalindrome(str) { const S = new Stack(); for(let i = 0; i < str.length; i++) { S.push(str[i]); } let newStr = ''; let len = S.length(); for(let i = 0; i < len; i++) { newStr += S.pop(); } return newStr == str; } console.log(isPalindrome(str)); // true;Copy the code

The space complexity is O(n), and the time complexity is O(n) 4. Parenthesis matching check idea: If the left parenthesis is added to the stack, the close parenthesis of the left parenthesis should match the top parenthesis of the stack. If the left parenthesis matches, the stack is ejected.

function isMatching(str) { const S = new Stack(); for(let i = 0; i < str.length; i++) { const c = str[i]; If (c = = '(' | | c = =' [' | | c = = '{') {supachai panitchpakdi ush (c);} / / here to use violence to enumerate the if ((c = =') '&& supachai panitchpakdi eek () = =' (') | | (c = = '] '&& S.peek() == '[') || (c == '}' && S.peek() == '{') ) { S.pop(); } } return S.length() == 0; } console.log(isMatching('{[]}'));Copy the code

The space is O(n), the time is O(n).

The last function to be called is executed first.

Time space complexity:

1. Time complexity:

Used to qualitatively describe the running time of the algorithm

Representation method:

A function, denoted by big O, such as O(1), O(n), O(logN)…

O(1): The command is executed only once

let i = 1;
i +=1 ;
Copy the code

O(n) : a section of code executed n times

for(let i = 0; i < n; i++) {
    console.log(i);
}
Copy the code

O(1) + O(n) = O(n): order and add, take the faster growth trend

let i = 1;
i +=1 ;
for(let j = 0; j < n; j++) {
    console.log(j);
}
Copy the code

O(n) * O(n) = O(n^2): nested multiplication, normal multiplication

for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { console.log(j); }}Copy the code

O(logN):

let i = 1;
while(i < n) {
    console.log(i);
    i *= 2;
}
Copy the code

2. Space complexity:

A measure of the amount of storage temporarily occupied by an algorithm while it is running.

Representation method:

A function, denoted by big O, such as O(1), O(n), O(n ^2)…

O(1): The memory footprint of a single variable is always 1

let i = 1;
i +=1 ;
Copy the code

O(n): Pushes n values in the array, occupying n memory units

const arr = [];
for(let i = 0; i < n; i++) {
    arr.push(i);
}
Copy the code

O(n^2): a two-dimensional array that stores n^2 variables

const arr = []; for(let i = 0; i < n; i++) { arr.push([]); for(let j = 0; j < n; j++) { arr[i].push(j); }}Copy the code

Reference:

“JavasCript Descriptions of Data Structures and Algorithms” by Macmillan

Postscript:

Time complexity and space complexity this section of the video, but my judgment may not be particularly accurate, if there is a mistake, I hope you big guy criticism and correction. I’m just a chicken on the way to study, not a big man.