前言：
现在看官们对“js的栈”都比较讲究，各位老铁们都需要知道一些“js的栈”的相关文章。那么小编同时在网摘上收集了一些对于“js的栈””的相关文章，希望咱们能喜欢，同学们一起来学习一下吧！#头条创作挑战赛#
要求如下，用JavaScript实现一个栈，要求push、pop、getMin和getMax的时间复杂度都是O(1)。
方法一
使用两个辅助栈来分别记录最大值和最小值。
首先，创建一个class minMaxStack，除了定义数据栈之外，再定义两个辅助栈minStack、 maxStack，用于记录当前栈的最小值和最大值。当数据栈中添加元素时，如果新元素小于等于minStack的顶部元素，就把新元素加入到minStack中；如果新元素大于等于maxStack的顶部元素，就把新元素加入到maxStack中。当数据栈弹出元素时，如果弹出的元素和minStack或maxStack顶部元素相同，就把相应的辅助栈顶部元素也弹出。获取栈中最小值或最大值时，分别返回minStack或maxStack的顶部元素即可，时间复杂度均为 O(1)。
代码如下：
class MinMaxStack { constructor() { this.stack = []; // 数据栈 this.minStack = []; // 辅助栈,记录最小值 this.maxStack = []; // 辅助栈，记录最大值 } push(val) { this.stack.push(val); if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) { this.minStack.push(val); } if (this.maxStack.length === 0 || val >= this.maxStack[this.maxStack.length - 1]) { this.maxStack.push(val); } } pop() { const val = this.stack.pop(); if (val === this.minStack[this.minStack.length - 1]) { this.minStack.pop(); } if (val === this.maxStack[this.maxStack.length - 1]) { this.maxStack.pop(); } return val; } getMin() { return this.minStack[this.minStack.length - 1]; } getMax() { return this.maxStack[this.maxStack.length - 1]; }}下面我们使用测试代码测试一下：
// 创建一个新的 MinMaxStack 实例const myStack = new MinMaxStack();// 依次向栈中添加元素 6、3、2、5、8、9myStack.push(6);myStack.push(3);myStack.push(2);myStack.push(5);myStack.push(8);myStack.push(9);// 分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 9// 使用 `pop` 方法将栈顶元素 9 弹出myStack.pop();// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 8// 再次使用 `pop` 方法将栈顶元素 8 弹出myStack.pop();// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 6// 使用 `push` 方法将元素 7 添加到栈中myStack.push(7);// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 7方法2
使用一个辅助栈来记录最大值和最小值
跟方法一不同，这次只需要创建一个辅助栈 minAndMaxStack， minMaxStack的每个元素都是一个对象，包含当前栈中的最小值和最大值。当数据栈中添加元素时，首先创建一个新的对象 curMinMax，将当前元素的值同时赋给 min 和 max 属性。然后，如果辅助栈 minAndMaxStack 不为空，就获取上一个元素 prevMinMax 的最小值和最大值，分别与当前元素的值比较，更新 curMinMax 的 min 和 max 属性。最后将 curMinMax 加入到辅助栈 minAndMaxStack 中，同时将元素值加入到数据栈 stack 中。
当数据栈弹出元素时，辅助栈 minAndMaxStack 也要弹出顶部元素。获取栈中最小值和最大值时，分别返回辅助栈 minAndMaxStack 的顶部元素的 min 和 max 属性即可，时间复杂度均为 O(1)。
代码如下：
class MinMaxStack { constructor() { this.stack = []; this.minAndMaxStack = []; } push(val) { this.stack.push(val); let curMinMax = { min: val, max: val } if (this.minAndMaxStack.length) { let preMinMax = this.minAndMaxStack[this.minAndMaxStack.length -1]; if (curMinMax.min >= preMinMax.min) { curMinMax.min = preMinMax.min; } if (curMinMax.max <= preMinMax.max) { curMinMax.max = preMinMax.max } } this.minAndMaxStack.push(curMinMax); } pop() { this.stack.pop(); this.minAndMaxStack.pop(); } getMin() { return this.minAndMaxStack[this.minAndMaxStack.length - 1].min; } getMax() { return this.minAndMaxStack[this.minAndMaxStack.length - 1].max; }}测试代码和结果如下所示：
// 创建一个新的 MinMaxStack 实例const myStack = new MinMaxStack();// 依次向栈中添加元素 6、3、2、5、8、9myStack.push(6);myStack.push(3);myStack.push(2);myStack.push(5);myStack.push(8);myStack.push(9);// 分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 9// 使用 `pop` 方法将栈顶元素 9 弹出myStack.pop();// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 8// 再次使用 `pop` 方法将栈顶元素 8 弹出myStack.pop();// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 6// 使用 `push` 方法将元素 7 添加到栈中myStack.push(7);// 再次分别调用 `getMin` 和 `getMax` 方法，获取栈中的最小值和最大值console.log(myStack.getMin()); // 输出 2console.log(myStack.getMax()); // 输出 7
