【数据结构与算法】栈相关算法题（长期更新）

TS 实现栈

interface IStack<T> {
  push(e: T): void;
  pop(): T | undefined;
  peek(): T;
  isEmpyt(): boolean;
  size(): number;
}

// implements: 实现接口, 一个类可以实现多个接口
class ArrayStack<T> implements IStack<T> {
  private data: T[] = []; // private: 私有属性，只能在类内部访问

  // push 方法：将一个元素压入到栈中
  push(e: T) {
    this.data.push(e);
  }

  // pop 方法：从栈中取出一个元素
  pop(): T | undefined {
    return this.data.pop();
  }

  // peek 方法：查看栈顶元素
  peek(): T {
    return this.data[this.data.length - 1];
  }

  // isEmpyt 方法：判断栈是否为空
  isEmpyt(): boolean {
    return this.data.length === 0;
  }

  // size 方法：返回栈中元素的个数
  size(): number {
    return this.data.length;
  }
}

// 测试样例
const s1 = new ArrayStack<string>();
s1.push('1');
s1.push('2');
s1.push('3');

console.log(s1.peek());
console.log(s1.pop());
console.log(s1.peek());
console.log(s1.size());
console.log(s1.isEmpyt());
const res = s1.pop();
res?.split('');

export { ArrayStack };

十进制转二进制

import { ArrayStack } from './01-Stack';

// 十进制转二进制: 除2取余法 先取余入栈最后再出栈
// 比如 35 转二进制
// 35 % 2 = 1
// 17 % 2 = 1
// 8 % 2 = 0
// 4 % 2 = 0
// 2 % 2 = 0
// 1 % 2 = 1
// 最后结果则为：101011
function decimalToBinary(decNumber: number): string {
  const stack = new ArrayStack<number>();
  let number = decNumber;
  // whlle：如果不确定循环条件使用 while
  // for: 如果确定循环次数使用 for
  while (number > 0) {
    const result = number % 2; // 余数
    stack.push(result); // 入栈
    number = Math.floor(number / 2); // 商
  }

  let binaryString = '';
  // 依次出栈结果则为二进制
  while (!stack.isEmpyt()) {
    binaryString += stack.pop();
  }
  return binaryString;
}

console.log(decimalToBinary(35)); // 101011
console.log(decimalToBinary(100));
export {};

Leetcode 20.有效的括号

20. 有效的括号