首頁 >web前端 >js教程 >如何用JS實作有getMin功能的棧

如何用JS實作有getMin功能的棧

不言原創: 2018-07-17 17:08:562048瀏覽

這篇文章主要介紹如何用JS實作有getMin功能的棧，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

前言：

　　已經確定工作了～下週一正式入職，按理說應該是可以好好浪蕩一周的，但是內心總是不安，總覺得自己這個水平真的太菜了，還是趁著現在有自己的時間，趕緊多看看書，多學習學習吧orz所以把之前校招買的書，又翻出來看，都是很經典的書，但是因為自己找到工作之後就放縱了，幾乎都放在書架上長灰，現在拿出來，一是希望自己能夠養成一個學習的好習慣，即使在工作忙的時候，依然要擠出一點時間學習新的知識，不能得過且過，二是希望記錄一下正在努力時的自己，也算是跟想要偷懶時的自己說，“餵，懶鬼，快點學習，不然你就真的對不起曾經努力的自己和以後懊悔的自己了”，嗯呢，閒話又說多了，接下來就正式開始咯～

正文：

　　【題目】實現一個特殊的棧，在實現棧的基本功能的基礎上，再實作返回堆疊中最小元素的操作。

　　【要求】1. pop、push、getMin操作的時間複雜度都為O(1)

　　　　　　2.設計的堆疊類型可以使用現成的堆疊結構

　　【思路】定義一個stackData和一個stackMin，stackData用於存放實際數據，stackMin用於存放stackData中的最小值。重寫pop和push方法，實作stackData和stackMin的資料同步。

　　【實作】實現的方式有兩種，詳見程式碼。

         // 方法一 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();    //抛出异常

後話：

　　這個是計畫寫成一個系列，主要參考的就是左大神的《程式設計師代碼面試指南－IT名企演算法與資料結構題目最優解》，左大神在書裡是用JAVA實現的，基本上看得懂，但是因為我是用JS的，總覺得差點意思，反正也是學習，乾脆就自己實現JS的寫法，並且分享出來，也算是讓我繼續堅持的一個動力，當然，因為本人是菜鳥小白，肯定或多或少會出現一些問題，希望各位大牛們在嘲笑之餘能夠請不吝賜教～康桑阿米達～阿尼嘎多～Thx～謝謝～

如何用JS實作有getMin功能的棧

相關文章