栈

数组是一种线性结构，并且可以在数组的任意位置插入和删除数据

但是有时候，为了实现某些功能，必须对这种任意性加以限制
栈和队列就是比较常见的受限的线性结构

站结构的实现

基于数组实现

export default class ArrayStack<T> {
  private data: T[] = [];
  // 入栈
  push(element: T) {
    this.data.push(element);
  }
  // 出栈
  pop(): T | undefined {
    return this.data.pop();
  }
  // 栈顶元素
  peek(): T | undefined {
    return this.data[this.data.length - 1];
  }
  // 是否为空
  isEmpty(): Boolean {
    return this.data.length === 0;
  }
  // 栈元素个数
  size(): number {
    return this.data.length;
  }
}

const stack = new ArrayStack<string>();
stack.push("22");
stack.push("vv");
stack.push("abc");
// //[ '22', 'vv', 'abc' ]
// console.log(stack);
// //abc
// console.log(stack.pop());
// //false
// console.log(stack.isEmpty());
// //vv
// console.log(stack.pop());
// //22
// console.log(stack.pop());
// //true
// console.log(stack.isEmpty());
// //0
// console.log(stack.size());
// export default new ArrayStack<number>();

基于链表实现

面试题 1 - 十进制转二进制

import Stack from "./stack重构";
/**
 * 思路
 * 1、十进制数每次被除，余数入栈
 * 2、十进制 = 0终止
 * 3、栈不为空时，依次出栈拼接
 * 4、返回结果
 */
function decimalToBinary(decimal: number): string {
  const stack = new Stack();
  // 余数
  let remainder: number;
  let binary = "";
  // 不确定循环次数while
  // 确定for
  while (decimal > 0) {
    remainder = decimal % 2;
    stack.push(remainder);
    decimal = Math.floor(decimal / 2);
  }
  while (!stack.isEmpty()) {
    binary += stack.pop();
  }
  return binary;
}
//100011
console.log("---", decimalToBinary(35));

面试题 2 - 有效括号

import Stack from "./stack重构";
/**
 * 思路
 * 1、遇到( { [ 入栈对应的闭合符号
 * 2、遇到闭合的符号，出栈且判断是否等于前一位对应的闭合的符号
 * 3、基数长度的isEmpty不为空返回false
 */
/**
 *
 * @param s
 * @returns
 */
function isValid(s: string): Boolean {
  const stack = new Stack<string>();
  const l = s.length;
  for (let i = 0; i < l; i++) {
    const val = s[i];
    switch (val) {
      case "(":
        stack.push(")");
        break;
      case "{":
        stack.push("}");
        break;
      case "[":
        stack.push("]");
        break;
      default:
        if (stack.pop() !== val) return false;
        break;
    }
  }
  return stack.isEmpty();
}
//true true false false true
console.log(isValid("()"));
console.log(isValid("(){}"));
console.log(isValid("(){]"));
console.log(isValid("(})"));
console.log(isValid("({[]})"));

不足

上面用数组实现了栈，还可以用链表来实现栈，比如

class LinkedStack {
    push() {}
    pop() {}
    peek() {}
    isEmpty() {}
    size() {}
  }

但是每次去实现栈都要记住对应的几个方法，这是个不足之处。

可是使用接口来完善

TS 中类可以继承类、类也可以实现接口

interface iStack<T> {
  push: (element: T) => void;
  pop: () => T | undefined;
  peek: () => T | undefined;
  isEmpty: () => Boolean;
  size: () => number;
}

这样就可以在定义类去实现这个接口

class LinkedStack<T> implements IStack<T>{
  push: (element: T) => void;
  pop: () => T | undefined;
  peek: () => T | undefined;
  isEmpty: () => Boolean;
  size: () => number;
}