数据结构与算法

栈结构

特性：首限的线性结构 / 先进后出

接口

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

export default IStack;

实现

数组

import IStack from "./IStack";

class ArrayStack<T = any> implements IStack<T> {
  private data: T[] = [];

  push(value: T) {
    this.data.push(value);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  get size() {
    return this.data.length;
  }

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

const stack = new ArrayStack<string>();

stack.push("aaa");
stack.push("bbb");
stack.push("ccc");

console.log(stack.peek());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

console.log(stack.size);
console.log(stack.isEmpty());

链表

import IStack from "./IStack";

class ListNode<T> {
  public next: ListNode<T> | null;

  constructor(public value: T) {
    this.next = null;
  }
}

class LinkedListStack<T> implements IStack<T> {
  // head -> 栈顶
  private head: ListNode<T> | null = null;
  private stackSize: number = 0;

  push(value: T): void {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;

    this.stackSize++;
  }

  pop(): T | undefined {
    if (!this.head) return;

    const value = this.head.value;
    this.head = this.head.next;
    this.stackSize--;

    return value;
  }

  peek(): T | undefined {
    return this.head?.value;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }

  get size() {
    return this.stackSize;
  }
}

const stack = new LinkedListStack<number>();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.peek());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.size);
console.log(stack.isEmpty());

算法题

有效的括号

// 20. 有效的括号

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false;

  const stack: string[] = [];
  const bracketMap: Record<string, string> = {
    "(": ")",
    "[": "]",
    "{": "}",
  };
  const leftBracket = Object.keys(bracketMap);

  for (let char of s) {
    if (leftBracket.includes(char)) {
      stack.push(bracketMap[char]);
    } else {
      if (stack.pop() !== char) return false;
    }
  }

  return !stack.length;
}

console.log(isValid("()[]{}"));
console.log(isValid("(]"));
console.log(isValid("([])"));

二进制转换

function binary(n: number): string {
  const stack = [];

  let value = n;

  while (value > 0) {
    const remainder = value % 2;
    stack.push(remainder);
    value = Math.floor(value / 2);
  }

  let str = "";

  while (stack.length) {
    str += stack.pop();
  }

  return str;
}

console.log(binary(100));

/*
  不断的 / 2 取余数
  10 / 2 = 0
  5 / 2 = 1
  2 / 2 = 0
  1 / 0 = 1
  0

  [1,0,1,0]
*/