Double ended queue

Drum pass flower game

Double ended queue check for palindromes

1. fo remove the elements at the head and tail of the queue at the same time. When the two elements are the same, it is the palindrome number, otherwise it is not

extend

1. When the browser tag is opened, a queue will be created. js is a single threaded language, so there is an event loop.

Linked list

Unidirectional linked list

1. The linked list should declare next, that is, the position pointed by the rear pointer, and then use index to record the position of the current variable, and length to record the length of the current linked list

Bidirectional linked list

1. A prev pointer is added to the head of the bidirectional linked list to point to the previous Node element. When changing the position or deleting, the previous pointer should also be operated

Ordered linked list

1. The corresponding element can be inserted into the corresponding linked list position through comparison.

Application scenario of linked list

1. When a large number of mobile elements are needed, including adding, deleting, modifying and querying elements, it is best to use the linked list.

aggregate

1. A data structure that stores unique elements. The concept of set in Mathematics: a set is a set of different objects.
2. Sets have intersection, union and complement. Equal operation

Self implementation of collection class

/*
 * @Author: Zhao Penglong
 * @Date: 2021-08-01 16:47:34
 * @LastEditors: Zhao Penglong
 * @LastEditTime: 2021-08-01 17:03:53
 * @Description: To test the set file
 */
/**
 * @description: Here, the collection is represented in the form of an object 
 * @param {*}
 * @return {*}
 * @author: Zhao Penglong
 */
class mySet {
    constructor() {
        this.items = {};
    }
    /**
     * @description: Determine whether the element exists in the collection 
     * @param {*} element  Incoming element
     * @return {*}
     * @author: Zhao Penglong
     */
    has(element) {
        // return element in items;
        return Object.prototype.hasOwnProperty.call(this.items, element);
    }
    /**
     * @description: Add the element. If the element does not exist, add the element
     * @param {*} element Elements to be added
     * @return {*}
     * @author: Zhao Penglong
     */    
    add(element){
        if(!this.has(element)){
            this.items[element] = element;
            return true;
        }else {
            return false;
        }
    }
    /**
     * @description: Delete this element. If it exists, delete it
     * @param {*} element
     * @return {*}
     * @author: Zhao Penglong
     */    
    delete(element){
        if(this.has(element)){
            delete this.items[element];
            return true;
        }
        return false;
    }
    /**
     * @description: Empty this object 
     * @param {*}
     * @return {*}
     * @author: Zhao Penglong
     */    
    clear(){
        this.items = {};
    }
    /**
     * @description: Returns the length of that data element
     * @param {*}
     * @return {*}
     * @author: Zhao Penglong
     */    
    sizeLegacy(){
        let count = 0;
        for(let key in this.items){
            if(this.items.hasOwnProperty(key)){
                count++;
            }
        }
        return count;
    }
    /**
     * @description: Returns the data of the element 
     * @param {*}
     * @return {*}
     * @author: Zhao Penglong
     */    
    values(){
        return Object.values(this.items);
    }
}
let set = new mySet();
set.add(1);
console.log(set.values());
console.log(set.has(1));
console.log(set.sizeLegacy());

set.add(2)
console.log(set.values());
console.log(set.has(2));
console.log(set.sizeLegacy());

set.delete(1);
console.log(set.values());

set.delete(2)
console.log(set.values());

Operation set

1. An important application scenario of set operation is database query. Intersection, union and complement in query are realized through set.
2. A function is called a pure function when it does not modify the current Set class or the parameter value passed in as a parameter.
3. Simple implementation of intersection operation new set ([... Seta]. Filter (x = > setb. Has (x)));
4. Difference set operation new set ([... Seta]. Filter (x = > setb. Has (x));

Concept of multiple sets

1. Sets are not allowed to have duplicate elements, but there is a concept called multiple sets in mathematics, which allows us to insert elements that have been added before. Multiple sets (or bags) are very useful in calculating the number of occurrences of elements in a set. It has also been widely used in database systems.

Dictionaries and hash tables