[TypeScript] Stack 구현하기

어제 문제풀이 참고

https://nogotit.tistory.com/entry/Grind75-TypeScript-Java-2-Valid-Parentheses

[Grind75 / TypeScript, Java] #2 Valid Parentheses

 

점심 먹고 너무 졸려서 

어제 문제 풀 때 썼던 stack을 제너릭 포함해서 더 나은 구조(양방향 링크드리스트)로 짜 보았다

코드도 확실히 더 간결해짐 

 

class Node<T> {
  // 제너릭 써서 구현해보기
  prev: Node<T> | null;
  val: T | undefined;
  next: Node<T> | null;

  constructor(val?: T) {
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class Stack<T> {
  btm: Node<T>; // 바닥
  curr: Node<T>; // 가장 위에 있는 요소

  constructor() {
    this.btm = new Node<T>();
    this.curr = this.btm;
  }

  push = (node: Node<T>): void => {
    this.curr.next = node; // 가장 위에 있는 요소의 다음 요소가 push한 요소 (연결)
    node.prev = this.curr; // push한 요소의 이전 요소는 지금의 curr
    this.curr = node; // 가장 위에 있는 요소를 push한 요소로 변경

    console.log('add =============');
    console.log(this.toArray());
  };

  peek = (): T => {
    // curr 요소의 값을 보여준다.
    if (this.curr.val) return this.curr.val;
    else throw new Error('StackUnderflow Error');
  };

  isEmpty = (): boolean => {
    // curr 값이 undefined(false)인 경우는 btm밖에 없다.
    return Boolean(!this.curr.val);
  };

  pop = (): T | undefined => {
    // 현재 가장 위에 있는 요소를 삭제한다.
    if (!this.isEmpty()) {
      if (this.curr.prev) this.curr = this.curr.prev; // 현재 커서의 이전 노드를 커서로 지정
      this.curr.next = null; // 현재 커서의 다음 노드 링크를 없앰

      console.log('pop =============');
      console.log(this.toArray());

      if (this.curr.val) return this.curr.val;
    } else throw new Error('StackUnderflow Error');
  };

  size = (): number => {
    let curr: Node<T> = this.btm;
    let size = 0;
    while (curr.next) {
      size++;
      curr = curr.next;
    } // 마지막 요소는 세지 않고, btm을 포함함 (결과는 같음)
    return size;
  };

  toArray = (): T[] => {
    let curr: Node<T> = this.btm;
    const arr: T[] = [];
    while (curr.next) {
      if (curr.val) arr.push(curr.val);
      curr = curr.next;
    }

    if (curr.val) arr.push(curr.val); // 마지막 요소까지 추가

    return arr;
  };
}

 

테스트는 다음 코드처럼 진행하면 됨

 

  // s가 임의 문자열이라고 가정

 

  const chars: Stack<string> = new Stack(); // 제너릭을 포함해 생성한다.

  for (let i = 0; i < s.length; i++) {

    chars.push(new Node<string>(s[i])); // 여기는 제너릭 없어도 됨 

  }

  console.log(chars.size());

  console.log(chars.isEmpty());

  chars.pop();

  chars.pop();

  chars.pop();

  chars.pop();

  chars.pop();

  chars.pop();

 

  console.log(chars.isEmpty());

 

 

실행 결과