JS を使用して getMin 関数でスタックを実装する方法-jsチュートリアル-php.cn

JS を使用して getMin 関数でスタックを実装する方法

不言

リリース： 2018-07-17 17:08:56

オリジナル

2064 人が閲覧しました

この記事では、JS を使用して getMin 関数を使用してスタックを実装する方法を主に紹介します。これには、必要な友達がそれを参照できるようにします。確定しました〜論理的に言えば、良い一週間を過ごせるはずですが、このレベルでは本当にうまくいかないといつも感じています。自分の時間ができたので、以前学校で買った本を取り出して読みました。しかし、就職してからは、ほとんど自分自身に夢中になりました。それらはすべて本棚に放置され、埃をかぶっていました。まず、私が勉強する良い習慣を身につけることができることを願っています。第二に、一生懸命働いているときの自分を記録したいと思っています。これは、怠け者よ、早く勉強しなさい、と自分に言い聞かせることにもなります。そうしないと、頑張った自分が本当に情けなくなり、将来後悔することになるよ」さて、噂話が多すぎましたが、これから正式にスタートします〜

postulate: 特別な条件を実装するstack は、スタックの基本機能の実現に基づいて、スタック内の最小の要素を返す操作を実装します。 【要件】1.pop、push、getMin操作の時間計算量はO(1)

2.設計されたスタックタイプは既製のスタック構造を使用できます

【アイデア】stackDataとstackMinを定義する、stackData 実際のデータを格納するために使用され、stackMin は stackData の最小値を格納するために使用されます。 stackData と stackMin 間のデータ同期を実現するために、pop メソッドと Push メソッドを書き換えます。 【実装】実装方法は2通りあり、詳細はコードを参照してください。

         // 方法一 1 class MyStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push() {
        let args = arguments[0];
        if (typeof args === &#39;number&#39;) {
            //将新数据压入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 === &#39;number&#39;) {
            //将新数据压入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();    //抛出异常

ログイン後にコピー

あとがき:

主な参考文献はZuo Dashen氏の『プログラマーコード面接ガイド - 有名IT企業からのアルゴリズムとデータ構造の質問への最適解』です。本ではZuo先生がJAVAを使って実装しているので、大体は理解できますが、JSを使っているのでいつも少し退屈に感じます、とにかくまだ勉強中なので書くだけです。 JS のメソッドを自分で見つけて共有することで、継続できるようになります。もちろん、私は初心者なので、多かれ少なかれ問題があることは間違いありません。すべての専門家が私に与えてくれることを願っています。笑いながらアドバイス ~ 康尚阿弥陀 ~ アニガド ~ Thx ~ありがとう~