preface

Use javascript to learn about data structures

Stack data structure

A stack is an ordered collection that follows the lifO principle. New elements added or to be removed are stored in the same segment of the stack, called the top, and the other end is called the bottom. Compare the process of stacking books and getting books.

Stack-demo complete code

Use objects to simulate stacks

The following code declares a Stack class where items store all the elements in the Stack and count counts the number of current elements. And add a push on the prototype, pop, peek, isEmpty, string these methods. These methods are implemented when simulating queues and linked lists.

// Stack class Stack{constructor(){
    this.items = {}
    this.count = 0
  }
  push(element){
    this.items[this.count] = element 
    this.count++
  }
  pop() {if(this.isEmpty())return undefined
    let remove = this.items[this.count-1] 
    delete this.items[this.count-1]
    this.count--
    returnRemove} // returns the top element of the stackpeek() {if(this.isEmpty())return undefined
    return this.items[this.count-1]
  }
  isEmpty() {return this.count === 0  
  }
  string() {let list = []
    for(leti=0; i<this.count; i++){ list.push(this.items[i]) }return list.join()
  }
  clear(){
    this.items = {}
    this.count = 0
  }
  size() {return this.count 
  }
}
Copy the code

Decimal to binary

Use the Stack class to implement the decimal to binary function. The following code emulates the concept of pushing in-memory data and fetching the most recent data via POP.

const stack = new Stack()
letNumber = 32 // Put all data on the stackwhile(number>0){
   stack.push(number%2)
   number = parseInt(number / 2)
}
let arr = []
while(! Stack.isempty ()){// Fetch the data at the top of the stack each time arr.push(stack.pop())}let result = arr.join(' ')
console.log('result',result); / / 100000Copy the code

Queue data structure

A queue is an ordered set of items that follow a first-in, first-out principle. Queues add new elements at the tail and remove elements from the top. It’s first come, first served.

Queue-demo complete code

Use objects to simulate queues

Queue is very similar to Stack except for the rule of adding and removing element points, and the following code keeps track of all items in the Queue and the maximum number of items. Since queue removal elements are first in first out, lowestCount is required to record the current minimum sequence number. Note how many entries in the current queue are computed by count-lowestCount.

class Queue {
  constructor(){this.items = {} this.count = 0 this.lowestCount = 0} // Enqueue (element){this.items[this.count] = element this.count++ }toString() {let arr = []
    for(leti=this.lowestCount; i<this.count; i++){ arr.push(this.items[i]) }return arr.join()
  }
  isEmpty() {returnThis.size ()=== 0} // First in first out queuedequeue() {if(this.isEmpty())return 
    let count = this.lowestCount
    let last = this.items[count]
    delete this.items[count]
    this.lowestCount++
    return last 
  }
}
Copy the code

deque

Is a special queue that allows us to add and remove elements from both the front end and the back end

Double – ended queue Demo complete code

  constructor(){
    this.count = 0
    this.items = {}
    this.lowestCount = 0
  }
  addBack(element){
    this.items[this.count] = element
    this.count++
  }
  addFront(element){
    if(this.isEmpty()){
      this.addBack(element)
    }else{
      this.items[this.lowestCount - 1] = element
      this.lowestCount-- 
    }
  }
  reMoveFront() {if(this.isEmpty())return 
    let remove = this.items[this.lowestCount]
    this.lowestCount++
    return remove
  }
  reMoveAfter() {if(this.isEmpty())return 
    let count = this.count -1
    let remove = this.items[count]
    this.count--
    return remove
  }
Copy the code

Implement palindrome checker using a double-endian queue

Palindromes are characters like Madam and Racecar that can be read forward and backward

A double-ended queue determines whether the current string is a palindrome

    let deque = new Deque()
    let str = '1madam1'// Add all of the string to the queuefor(let item of str){
      deque.addBack(item)
    }
    let isTrue = true
    while(deque.size()>1) {isTrue = deque.removeAfter () === reMoveFront()} console.log(isTrue);Copy the code

Linked list data structures

The data structure of a linked list is as follows. Each element has two attributes, value and Next. The next element can be specified by next.

The list

Subitems: Since the subitems need value and next attributes, a Node class is used to implement a subclass. Maintenance can also extend the Node class.

LinkedList: head is used to record the current first item and all subsequent values can be iterated to retrieve the next value to retrieve all values in the LinkedList.

LinkedList Demo complete code

Class Node {constructor(element){this.value = element this.next = undefined}} class LinkedList {constructor(){
    this.head = undefined
    this.count = 0
  }
  push(element){
    let node = new Node(element)
    if(this.isEmpty()){
      this.head = node
    }else{// Take the last bitlet current = this.getElementAt(this.count-1)
      current.next = node 
    }
    this.count++
  }
  removeAt(index){
    if(index>=0&&index<this.count){
      letCurrent // If the current item is greater than 0, the previous item existsif(index>0){// Get the previous childletGetElementAt (index-1) current = this.getelementat (index-1) current = nextelseCurrent = this.head this.head = current. Next} this.count-- // Returns the value of the deleted itemreturn current.value
    }
    return1}isEmpty() {return this.count === 0
  }
  getElementAt(index){
    if(index>=0&&index<this.count){
      let current = this.head
      while (index>0) {
        current = current.next
        index--
      }
      return current 
    }
    return-1} // find the indexOf the current value indexOf(element){let current = this.head
    for(leti=0; i<this.count; i++){if(element === current.value){
        return i
      }
      current = current.next 
    }
    return -1
  }
  insert(element,index){
    let node = new Node(element)
    if(index>=0&&index<=this.count){
      if(index===0){
        let current = this.head
        node.next = current
        this.head = node 
      }else{
        let pre = this.getElementAt(index-1)
        let current = pre.next 
        pre.next = node
        node.next = current
      }
      this.count++
    }
  }
  toString() {let arr = []
    let current = this.head
    for(leti=0; i<this.count; i++){ arr.push(current.value) current = current.next }return arr.join()
  }
}
Copy the code

The last

Now that I have a basic understanding of stack-queue-linked lists, I’m going to try to do some interesting algorithms with these data structures, and then I’m going to move on to binary tree algorithms.