栈

  • 一个后进先出的数据结构
  • push(入栈),pop(出栈)，js没有栈的概念但是可以用Array实现栈的所有功能
  1. const stack = [];
  2. stack.push(1);
  3. stack.push(2);
  4. const item1 = stack.pop();
  5. const item2 = stack.pop();

什么场景下使用栈

需要后进先出的场景

  • 十二进制转二进制
  • 判断字符串的括号是否有效，函数调用堆栈

十进制转二进制

数据结构-栈 - 图1

数据结构-栈 - 图2

20.有效的括号 — leetCode

  2.  function isValid(s){
  3.     let stack = [];
  4.     let stackTop;
  5.     if(s.length%2 === 1){
  6.       return false
  7.     }
  8.     for(let i = 0;i++;i<s.length){
  9.       if(s[i] === '[' || s[i] === '{' || s[i] === '('){
  10.         stack.push(s[i])
  11.       }else{
  12.         stackTop = s[s.length-1];
  13.         if(s[i] === ']' && stackTop === '[' || s[i] === '}' && stackTop === '{' || s[i] === ')' && stackTop === '('){
  14.           stack.pop()
  15.         }else{
  16.            return false
  17.         }
  18.       }
  19.     }
  20.       return stack.length === 0
  21.   }
  22.   let arrs = ['[','{','}',']'];
  23.   let res = isValid(arrs);
  24.   console.log(res)

有效的括号