这个题目实现的主要方法是：遍历字符串，先排除错误情况，然后将 ( 入栈保存，将 ) 入栈匹配前一个元素是否是 ( ，如果是，则 pop() 前一个元素 (，如果不是，则 push() 这个 ) 入栈，最终查看栈是否为空，若是则检验成功，否则失败。
方法1：使用前面定义的 Stack 类
这里使用前面题目中定义的 Stack 类。
/** * 检验圆括号顺序的有效性 * @param {String} str */ function validParentheses (str){ if(!str || str.length === 0 || str[0] === ')') return false let stack = new Stack() str.split('').forEach(char => { let status = stack.peek() === '(' && char === ')' status ? stack.pop() : stack.push(char) }) return stack.isEmpty() }
方法2：出入栈操作
/** * 检验圆括号顺序的有效性 * @param {String} str */ function validParentheses (str){ if(!str || str.length === 0 || str[0] === ')') return false let arr = [] for(let i = 0; i < str.length ; i++){ str[i] === '(' ? arr.push(str[i]) : arr.pop() } return arr.length === 0 }
五、改造题二，添加一个 min 函数来获得栈中最小元素
步骤
数据栈
辅助栈
最小值
1.push 3
3
0
3
2.push 4
3, 4
0, 0
3
3.push 2
3, 4, 2
0, 0, 2
2
4.push 1
3, 4, 2 ,1
0, 0, 2, 3
1
5.pop
3, 4, 2
0, 0, 2
2
6.pop
3, 4
0, 0
3
7.push
3, 4 ,0
0, 0, 2
0
使用示例如下：
let stack = new Stack(); stack.push(3); console.log('After push 3, Min item is', stack.min()); stack.push(4); console.log('After push 4, Min item is', stack.min()); stack.push(2); console.log('After push 2, Min item is', stack.min()); stack.push(1); console.log('After push 1, Min item is', stack.min()); stack.pop(); console.log('After pop, Min item is', stack.min()); stack.pop(); console.log('After pop, Min item is', stack.min()); stack.push(0); console.log('After push 0, Min item is', stack.min());
提示：利用辅助栈（Web 端可利用数组），每次对栈 push/pop 元素时，也同时更新辅助栈（存储最小元素的位置）
方法1：小操作
class Stack { constructor() { this.items = []; this.minIndexStack = []; } push(element) { this.items.push(element); let minLen = this.minIndexStack.length; let minItemIndex = this.minIndexStack[minLen - 1]; if(minLen === 0 || this.items[minItemIndex] > item) { this.minIndexStack.push(this.items.length - 1); } else { this.minIndexStack.push(minItemIndex); } } pop() { this.minIndexStack.pop(); return this.items.pop(); } min() { let len = this.minIndexStack.length; return (len > 0 && this.items[this.minIndexStack[len - 1]]) || 0; } peek() { return this.items[this.items.length - 1]; } // 省略其它方法 }
方法2：与方法1中push实现的差异
class Stack { constructor (){ this.items = [] // 数据栈 this.arr = [] // 辅助栈 } push( element ){ this.items.push(element) let min = Math.min(...this.items) this.arr.push( min === element ? this.size() - 1 : 0) } pop(){ this.arr.pop() return this.items.pop() } peek(){ return this.items[this.items.length - 1] } isEmpty(){ return this.items.length === 1 } clear(){ this.items = [] } size(){ return this.items.length } min (){ let last = this.arr[this.arr.length - 1] return this.items[last] } }
以上所述是小编给大家介绍的数据结构与算法（Stack）详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持！
您可能感兴趣的文章: