Data structure of JS version 1 (Stack)

Due to the front end to fit more quickly, and development at ordinary times when most of the writing is the business logic and interaction, often lead to us by some backend researchers’ contempt ‘, this is undoubtedly front-end developer is not fair for us, the front-end technology update iterative soon, and knowledge point trivial, want to learn the front-end is need certain continuous learning ability and creativity and curiosity, learn Getting a good front end is not an easy task.

We all know that programming = algorithm + data structure

Whether at the front end or the back end, as a developer to master these basic knowledge determines the development of your future technical path of the upper limit, algorithms and data structures for programmers is self-evident.

Putting aside some prejudices, we can’t deny that:

1. There are many front-end students who do not have a deep understanding of data structure, and even some definitions of data structure types are not clear.
2. There are limited data structures implemented with JS on the web.

In view of this actual situation, I will introduce the most common data structures in six blogs, and combine the classic original problems in LeetCode with JS methods to solve the actual problems, including:

• The stack
• The queue
• The list
• matrix
• Binary tree
• The heap

If you’re a front-end developer who wants to lay a solid foundation for data structures and can’t find the right resources online, xiaodi’s blog will definitely help you.

The stack (stack)

The definition of the stack

As the simplest kind of data structure, I think you all know something about stack. Let’s take a look at the definition of ‘stack’ on Baidu Encyclopedia

And when you get this drink,

var arr = [2.7.1]
arr.push(8) 
arr.push(2)
arr.pop()
arr.pop()
arr.pop()Copy the code

The code is as follows:

export default (arr) => {  
    // Create an empty stack to save the result
        let result = []  
    // Data from the previous round
        let pre1  
    // Last wheel data
        let pre2  
    // Iterate over the array passed in to process the score
    arr.forEach(item= > {    
        switch (item) {      
            case 'C':        
                if (result.length) {          
                    result.pop()        
                }        
                break      
            case 'D':        
                pre1 = result.pop()        
                result.push(pre1, pre1 * 2)       
                break      
            case '+':       
                pre1 = result.pop()       
                pre2 = result.pop()      
                result.push(pre2, pre1, pre2 + pre1)      
                break     
            default:
                // *1 converts item to number
                result.push(item * 1)}})// Use reduce to sum
     return result.reduce((prev, cur) = >  prev + cur )}Copy the code

Example number two: Maximum rectangle

More comments are written in the code, and I will send out the source code for your reference

export default arr => {
  // Use to store the two-dimensional array after processing
  let changeArr = []
  // The incoming two-dimensional array is iterated over the index position of successive 1s for each item
  arr.forEach((item, i) = > {
    // Index of each item
    let itemArr = []    
    let str = item.join(' ')    
    let reg = /1{2,}/g
    // The matching result of consecutive 1
    let execRes = reg.exec(str)
    // If not null, the match continues
    while (execRes) {
      // push the start and end positions of group j1 matched by item I
      itemArr.push([execRes.index, execRes.index + execRes[0].length - 1])      
      execRes = reg.exec(str)    
    }
    // Push the matching result of item I in
    changeArr.push(itemArr)  
  })
  // Save the area
  let area = []  
  // take the intersection function
  let find = (arr, n = 1) = > {    
      // Shallow-copy arR arrays prevent the function from being changed each time it is executed due to references
      let copyArr = [].concat(arr)    
      // The last item in the array
      let last = copyArr.pop()    
      // The penultimate item of the array
      let next = copyArr.pop()
      // Each of the last and penultimate terms
      let lastItem, nextItem
      // Get the intersection array
      let recuArr = []
      // as a temporary variable for each intersection fetched
      let item = []
      // The number of rows traversed
      n++
      // set the intersection of each interval of each adjacent term
      for (let i = 0; i < last.length; i++) {      
          lastItem = last[i]      
          for (let j = 0; j < next.length; j++) {        
            nextItem = next[j]        
            // start fetching the intersection
            // If there is an intersection
            if(! (Math.max(... lastItem) <=Math.min(... nextItem) ||Math.max(... nextItem) <=Math.min(... lastItem))) { item = [Math.max(lastItem[0], nextItem[0]), Math.min(lastItem[1], nextItem[1])]          
                recuArr.push(item)
            // Find the area of the intersection and push the area
            area.push((item[1] - item[0] + 1) * n)        
            }      
         }    
      }    
      // If there is no intersection in all cases, return false
      if (recuArr.length === 0) {
         return false
      } else {
         // If there is an intersection, continue recursively
         if (copyArr.length > 0) {
           copyArr.push(recuArr)
           find(copyArr, n)
         }
      }
    }
    // Decrement the array all the way, looking for an intersection for each row as the first row
    while (changeArr.length > 1) {
        find(changeArr)
        changeArr.pop()
    }
    // Returns the maximum value of the rectangular array that holds the area
    return area.length === 0 ? 0 : Math.max(... area) }Copy the code

reference

1. Baidu encyclopedia
2. “Js Data Structure and Algorithm” by Teacher Yin Guohui, head of video architecture front end of Toutiao
3. leetCode

conclusion

As a relatively simple data structure, stack in JS is very common, is also easier to understand, we can use JS native array API can be implemented.

In the next article, I’ll show you how to use queues.