数据结构（二）栈
栈是什么？
- 一个后进先出的数据结构
-
JavaScript中没有栈，但可以用Array实现栈的所有功能
栈的应用场景
- 需要后进先出的场景
- 比如： 十进制转二进制，判断字符串的括号是否有效、函数的调用栈
场景一、 十进制转二进制
- 后出来的余数要先出来
-
把余数依次入栈，然后再出栈，就可以实现余数倒序输出
场景二、 有效的括号
- 越靠后的左括号，对应的右括号越靠前
- 左括号入栈，右括号出栈，最后栈空了就是合法的。
场景三、 函数调用堆栈
- 最后调用的函数，最先执行完成
- JS解释器使用栈来控制函数的调用顺序
LeetCode #20题
20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
解题思路：
- 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前。
- 满足后进先出，考虑用栈的思路
步骤：
- 新建一个栈
- 扫描字符串。遇到左括号入栈，遇到和栈顶括号类型匹配的右括号出栈，类型不匹配直接判定为不合法
- 最后栈控了合法，不空就不合法
时间复杂度 O(n)
空间复杂度 O(n)
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if(s.length %2 === 1) { return false }
const stack = [];
for(let i = 0; i<s.length; i+=1){
const c = s[i];
if(c === '(' || c === '{' || c === '['){
stack.push(c);
}else{
const top = stack[stack.length-1];
if(
(top === '(' && c === ')') ||
(top === '{' && c === '}') ||
(top === '[' && c === ']')
){
stack.pop();
}else{
return false;
}
}
}
return stack.length === 0;
};总结
- 栈是一个后进先出的数据结构
- JavaScript中没有栈，但是可以用array实现栈的所有功能
- 栈的常用操作：
push、pop、stack[length-1]
用ES6的class，封装一个stack类，包括push、pop、peek方法
```JavaScript
// 使用es6的class来封装一个stack类
class farkStack{ // 定义一个名字为Stack的类
constructor(){
this.dataStore = []
}
push(item){
this.dataStore.push(item);
}
pop(){
return this.dataStore.pop();
}
peek(){ // 探出
return this.dataStore[this.dataStore.length - 1];
}
size(){
return this.dataStore.length;
}
clear(){
this.dataStroe = []
}
}
```用栈这个数据结构，将100这个十进制数字转为2进制
```JavaScript
function switchBinary(decNum){
let stack = new farkStack();
while(decNum > 0){
stack.push(decNum % 2);
decNum = Math.floor(decNum/2)
}
let binaryStr = ''
while(stack.size() !== 0) {
binaryStr += stack.pop()
}
return binaryStr;
}
switchBinary(125)
```