An ordered stack of js data structures

Stack is a relatively common data structure, although there is no native stack in JS, but the implementation is not complicated, mainly is the implementation of push, POP, top several functions. The ordered stack I’m talking about here is a stack where the elements are arranged in a certain order. The main application scenarios are: find the smallest K number in the array and so on.

Class implementation of ordered stack

class Stack{
    /** * constructor, s is used to store data, count is used to record stack size */
    constructor(){
        this.s = [];
        this.count = 0;
    }

    /** * add data * to the stack@param Num needs to be stored on the stack */
    push(num) {
        // If the data is empty, no operation is performed
        if(! num)return;
        // Find the subscript of the number greater than num in the stack
        const index = this.s.findIndex((value, index) = > value > num);
        // If num is not found, all elements in the stack will be smaller than num
        if(index === -1) this.s.push(num);
        else{
            // Otherwise, insert the first element position that will be greater than num
            this.s.splice(index, 0, num);
        }
        // Stack size increases by 1
        ++this.count;
    }

    /** ** stack pops elements, array sorted from smallest to largest, directly pops the largest element */
    pop(){
        this.s.pop();
        --this.count;
    }

    /** * returns the top element *@returns The largest element in the array */
    top() {
        if(this.count >= 1) return this.s[this.count-1];
        return undefined; }}function kMin(arr, k){
    const st = new Stack();
    arr.forEach(item= > {
        // If the number of elements in the stack is less than k, add data directly to the stack
        if(st.count < k){
            st.push(item);
        }else{
            // Otherwise, if the element is smaller than the top of the stack, pop the top of the stack and add data to the stack
            if(item < st.top()){ st.pop(); st.push(item); }}})return st.s;
}

kMin([7.4.5.8.10.30].2)
Copy the code

Now functional programming is more popular, and here is the implementation of functional. Obviously, the implementation of the functional formula is more concise and clear. Exposed variables and functions are returned.

function fStack(){
    const arr = [];

    const count = () = > {
        return arr.length;
    }

    const push = (num) = > {
        // If the data is empty, no operation is performed
        if(! num)return;
        // Find the subscript of the number greater than num in the stack
        const index = arr.findIndex((value, index) = > value > num);
        // If num is not found, all elements in the stack will be smaller than num
        if(index === -1) arr.push(num);
        else{
            // Otherwise, insert the first element position that will be greater than num
            arr.splice(index, 0, num); }}const pop = () = > {
        arr.pop();
    }

    const top = () = > {
        if(count >= 1) return arr[count-1];
        return undefined;
    }

    return {
        arr,
        count,
        push,
        pop,
        top
    }
}

function kMin(arr, k){
    const st = new fStack();
    arr.forEach(item= > {
        // If the number of elements in the stack is less than k, add data directly to the stack
        if(st.count() < k){
            st.push(item);
        }else{
            // Otherwise, if the element is smaller than the top of the stack, pop the top of the stack and add data to the stack
            if(item < st.top()){ st.pop(); st.push(item); }}})return st.arr;
}

const res = kMin([7.4.5.8.10.30].2)
Copy the code