栈是什么？

• 一个后进先出的数据结构
• JavaScript中没有栈，但可以用Array实现栈的所有功能

栈的应用场景

• 需要后进先出的场景
• 比如： 十进制转二进制，判断字符串的括号是否有效、函数的调用栈

场景一、 十进制转二进制

• 后出来的余数要先出来
• 把余数依次入栈，然后再出栈，就可以实现余数倒序输出

场景二、 有效的括号

• 越靠后的左括号，对应的右括号越靠前
• 左括号入栈，右括号出栈，最后栈空了就是合法的。

场景三、 函数调用堆栈

• 最后调用的函数，最先执行完成
• JS解释器使用栈来控制函数的调用顺序

LeetCode #20题

20 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

解题思路：

1. 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前。
2. 满足后进先出，考虑用栈的思路

步骤：

1. 新建一个栈
2. 扫描字符串。遇到左括号入栈，遇到和栈顶括号类型匹配的右括号出栈，类型不匹配直接判定为不合法
3. 最后栈控了合法，不空就不合法

时间复杂度 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方法

// 使用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进制

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)