TypeScript로 STACK QUE 구현해보기

공부한 내용으로 Stack과 Que를 만들어봤다. 코드부터 바로 봐보자

interface Stack<A> {
  readonly size: number;
  push(value: A): void;
  pop(): A;
}

type StackNode<A> = {
  readonly value: A;
  readonly next?: StackNode<A>;
};

class StackImpl<A> implements Stack<A> {
  private _size: number = 0;
  private head?: StackNode<A>;

  constructor(private capacity: number) {}
  get size() {
    return this._size;
  }
  push(value:A) {
    if (this.size === this.capacity) {
      throw new Error('Stack is full!');
    }
    const node = { value, next: this.head };
    this.head = node;
    this._size++;
  }
  pop(): A {
    if (this.head == null) { //null과 undefined모두를 거를 수 있도록 ===대신 ==를 사용한다.
      throw new Error('Stack is empty!');
    }
    const node = this.head;
    this.head = node.next;
    this._size--;
    return node.value;
  }
}

먼저 stack이라는 인터페이스부터 만들어주었다.

읽기 전용으로 size를 가지고 있고 push와 pop이라는 함수를 가지고 있어야함을 의미한다.

 

그리고 스택에 쌓일 노드에 관한  type도 정의해주었는데

현재 값인 value와 있을 수도 있고 없을 수도 있는 next값을 지정해주었다.

 

클래스를 살펴보자

StackImpl이라는 클래스는 위에서 지정한 stack 인터페이스를 규격으로 한다.

내부값으로 stack의 사이즈와 stack이 가리키는 head 값이 옵션으로 지정되어있다.

constructor에서 생성한 스택의 저장용량인 capacity를 number type으로 받는다.

 

push함수를 보자

사이즈와 생성할 때 만든 capacity가 같으면 Error를 던진다.

사이즈가 여유가 있다면 node오브젝트를 생성하는데 push에서 받아온 값을 value로 받고 next 값을 클래스 내 head가 가리키는 값으로 받는다. 이러면 노드와 노드가 순서대로 이어질 수 있다.

그리고 헤드는 방금 생성한 node값을 할당해주고 사이즈를 +1해준다.

 

POP함수를 보자

pop함수는 stack에 맨 마지막에 들어온 값을 반환한다.

반환할 node를 현재 head가 가진 값으로 할당해준다.

그리고 head는 node안에 있는 next를 할당받는다.

사이즈를 -1 해주고 위 과정에서 언급한 반환할 node의 value를 return해준다.

 

 

알고리즘에서 자주 사용하는 Stack을 TypeScript로 구현해보았는데

알고리즘이해도 되고 타입스크립트도 공부할 수 있어서 좋았다.