常見面試演算法題JS實現-設計一個有getMin功能的棧

前言：

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

正文：

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

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

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

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

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

 // 方法一
 1 class MyStack {
 2     constructor() {
 3         this.stackData = [];
 4         this.stackMin = [];
 5     }
 6     push() {
 7         let args = arguments[0];
 8         if (typeof args === 'number') {
 9             //將新數據壓入stackData棧中
10             this.stackData.push(args);
11             //判斷是否將新數據壓入stackMin棧中
12             if (this.stackMin.length > 0) {
13                 //stackMin棧不空，需要判斷當前數據是否小於等於stackMin的棧頂元素
14                 let top = this.getMin();
15                 if (args <= top) {
16                     this.stackMin.push(args);
17                 }
18             } else {
19                 //stackMin棧空，則壓入
20                 this.stackMin.push(args);
21             }
22         }
23     }
24     pop() {
25         if (this.stackMin.length === 0) {
26             throw new Error('Stack is empty!');
27         }
28         let p = this.stackData.pop();
29         let top = this.getMin();
30         if (p === top) {
31             this.stackMin.pop();
32         }
33         return p;
34     }
35     getMin() {
36         if (this.stackMin.length === 0) {
37             throw new Error('Stack is empty!');
38         }
39         let len = this.stackMin.length;
40         return this.stackMin[len - 1];
41     }
42 }
43 
44 let s = new MyStack();
45 s.push(4);
46 s.push(2);
47 s.push(1);
48 console.log(s.getMin());
49 s.pop();
50 console.log(s.getMin());
51 s.pop();
52 s.pop();
53 s.pop();    //拋出異常

 //方法二
 1 class MyStack {
 2     constructor() {
 3         this.stackData = [];
 4         this.stackMin = [];
 5     }
 6     push() {
 7         let args = arguments[0];
 8         if (typeof args === 'number') {
 9             //將新數據壓入stackData棧中
10             this.stackData.push(args);
11             //判斷是否將新數據壓入stackMin棧中
12             if (this.stackMin.length > 0) {
13                 //stackMin棧不空，需要判斷當前數據是否小於等於stackMin的棧頂元素
14                 let top = this.getMin();
15                 if (args <= top) {
16                     this.stackMin.push(args);
17                 } else {
18                     this.stackMin.push(top);
19                 }
20             } else {
21                 //stackMin棧空，則壓入
22                 this.stackMin.push(args);
23             }
24         }
25     }
26     pop() {
27         if (this.stackMin.length === 0) {
28             throw new Error('Stack is empty!');
29         }
30         let p = this.stackData.pop();
31         this.stackMin.pop();
32         return p;
33     }
34     getMin() {
35         if (this.stackMin.length === 0) {
36             throw new Error('Stack is empty!');
37         }
38         let len = this.stackMin.length;
39         return this.stackMin[len - 1];
40     }
41 }
42 
43 let s = new MyStack();
44 s.push(4);
45 s.push(2);
46 s.push(1);
47 console.log(s.getMin());
48 s.pop();
49 console.log(s.getMin());
50 s.pop();
51 s.pop();
52 // s.pop();    //拋出異常

後話：

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