How to use JS to implement a stack with getMin function

This article mainly introduces how to use JS to implement a stack with getMin function. It has a certain reference value. Now I share it with everyone. Friends in need can refer to it

Preface ：

I have confirmed my job ~ I will officially join the job next Monday. Logically speaking, I should be able to spend a good week wandering around, but I am always uneasy inside. I always feel that I am really too good at this level. It’s better to read more books and study more while you have your own time now. So I read the books I bought from the previous school recruitment. They are all very classic books, but after I found a job, I indulged in them. Almost all of them have been gathering dust on the bookshelves. Now I take them out. Firstly, I hope that I can develop a good habit of studying. Even when I am busy at work, I still have to squeeze out some time to learn new knowledge. I can’t just muddle through. Secondly, I hope that Recording yourself when you are working hard can also be said to yourself when you want to be lazy, "Hey, lazy guy, hurry up and study, otherwise you will really feel sorry for yourself who worked hard and will regret it in the future." Well, Enough chatter, let’s start in earnest~

Text:

[Title] Implement a special stack, in the implementation Based on the basic functions of the stack, the operation of returning the smallest element in the stack is implemented.

【Requirements】1. The time complexity of pop, push and getMin operations is O(1)

　　　 　　2. The designed stack type can use the existing stack structure

[Idea] Define a stackData and a stackMin. stackData is used to store actual data, and stackMin is used to store the minimum value in stackData. Rewrite the pop and push methods to achieve data synchronization between stackData and stackMin.

[Implementation] There are two ways to implement it, see the code for details.

         // 方法一 1 class MyStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push() {
        let args = arguments[0];
        if (typeof args === 'number') {
            //将新数据压入stackData栈中
            this.stackData.push(args);
            //判断是否将新数据压入stackMin栈中
            if (this.stackMin.length > 0) {
                //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
                let top = this.getMin();
                if (args <= top) {
                    this.stackMin.push(args);
                }
            } else {
                //stackMin栈空，则压入
                this.stackMin.push(args);
            }
        }
    }
    pop() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let p = this.stackData.pop();
        let top = this.getMin();
        if (p === top) {
            this.stackMin.pop();
        }
        return p;
    }
    getMin() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let len = this.stackMin.length;
        return this.stackMin[len - 1];
    }
}
let s = new MyStack();
s.push(4);
s.push(2);
s.push(1);
console.log(s.getMin());
s.pop();
console.log(s.getMin());
s.pop();
s.pop();
s.pop();    //抛出异常

          //方法二 1 class MyStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push() {
        let args = arguments[0];
        if (typeof args === 'number') {
            //将新数据压入stackData栈中
            this.stackData.push(args);
            //判断是否将新数据压入stackMin栈中
            if (this.stackMin.length > 0) {
                //stackMin栈不空，需要判断当前数据是否小于等于stackMin的栈顶元素
                let top = this.getMin();
                if (args <= top) {
                    this.stackMin.push(args);
                } else {
                    this.stackMin.push(top);
                }
            } else {
                //stackMin栈空，则压入
                this.stackMin.push(args);
            }
        }
    }
    pop() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let p = this.stackData.pop();
        this.stackMin.pop();
        return p;
    }
    getMin() {
        if (this.stackMin.length === 0) {
            throw new Error(&#39;Stack is empty!&#39;);
        }
        let len = this.stackMin.length;
        return this.stackMin[len - 1];
    }
}
let s = new MyStack();
s.push(4);
s.push(2);
s.push(1);
console.log(s.getMin());
s.pop();
console.log(s.getMin());
s.pop();
s.pop();
// s.pop();    //抛出异常

Afterword:

This is planned to be written as a series, and the main reference is Zuo Dashen's " Programmer's Code Interview Guide - Optimal Solutions to Algorithm and Data Structure Questions from Famous IT Companies. In the book, Zuo Dashen uses JAVA to implement it, so I can basically understand it. However, because I use JS, I always find it a bit confusing, anyway. It’s also learning. I might as well implement JS writing by myself and share it, which is a motivation for me to continue to persevere. Of course, because I am a novice, there will definitely be some problems more or less. I hope all the experts can help me. If you can laugh at me, please give me some advice~Kangsang Amida~Anigado~Thx~Thank you~

Related recommendations:

What is the method of transferring functions in js

Understanding of actual parameters, formal parameters and closures of js functions

The above is the detailed content of How to use JS to implement a stack with getMin function. For more information, please follow other related articles on the PHP Chinese website!