stack-栈

// 栈： 先入后出
class Stack {
  constructor() {
    this.items = {};
    this.length = 0;
  }

  //入栈
  push(node) {
    this.items[this.length] = node;
    this.length++;
  }

  //出栈
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    this.length--;
    const node = this.items[this.length];
    delete this.items[this.length];
    return node;
  }

  isEmpty() {
    return this.length === 0;
  }

  //获取栈尾元素
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.length - 1];
  }

  clear() {
    this.items = {};
    this.length = 0;
  }

  size() {
    return this.length;
  }
}

const s = new Stack();
s.push("node-1");
s.push("node-2");

console.log(s.pop()); //node-2
console.log(s.pop()); //node-1

实战: 十进制转二进制

//实战1：十进制转二进制
//11 / 2 = 5;余 1
//5 / 2 = 2;余 1
//2 / 2 = 1;余 0
//1 / 2 = 0;余 1
//将余数反向连接：1011
function getResult(number) {
  const stack = new Stack();

  const get = (current) => {
    const next = Math.floor(current / 2);
    const yu = current % 2;
    stack.push(yu);
    if (next <= 0) return;
    get(next);
  };

  get(number);

  let result = "";
  while (!stack.isEmpty()) {
    result += stack.pop();
  }
  return result;
}

console.log(getResult(11)); //1011
console.log(getResult(20)); //10100

实战: 有效的括号 LeetCode - 20题

//实战2：有效的括号 LeetCode - 20题
//输入：s = "()"
//输出：true
//输入：s = "()[]{}"
//输出：true
//输入：s = "{[]}"
//输出：true
//输入：s = "([(]"
//输出：false
function kuo(string) {
  // const stack = new Stack();
  // let index = 0;
  // while(index < string.length){
  //   const current = string[index];
  //   const top = stack.peek();//获取将要出栈的元素
  //   if((top === '(') && current === ')' || (top === '[' && current === ']') || (top === '{' && current === '}')){
  //     stack.pop()
  //   }else{
  //     stack.push(current);
  //   }
  //   index++
  // }

  // return stack.isEmpty();

  // 使用数组模拟
  const stack = [];
  let index = 0;
  while (index < string.length) {
    const current = string[index];
    const top = stack[stack.length - 1];
    if (
      (top === "(" && current === ")") ||
      (top === "[" && current === "]") ||
      (top === "{" && current === "}")
    ) {
      stack.pop();
    } else {
      stack.push(current);
    }
    index++;
  }
  return stack.length === 0;
}
console.log(kuo("()")); //true
console.log(kuo("()[]{}")); //true
console.log(kuo("{[]}")); //true
console.log(kuo("([(]")); //false