타입스크립트 자료구조 구현 - 스택

자바스크립트나 타입스크립트에서는 배열을 이용하여 쉽게 스택을 구현할 수 있습니다. 이번 포스트에서는 배열을 이용하지 않고 직접 스택을 구현해보겠습니다.

📄 stack.ts

{
  interface Stack {
    readonly size: number;
    pop(): string;
    push(value: string): void;
  }

  type StackNode = {
    readonly value: string;
    readonly next?: StackNode;
  };

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

    get size() {
      return this._size;
    }

    push(value: string) {
      const node: StackNode = {
        value,
        next: this.head,
      };
      this.head = node;
      this._size++;
    }

    pop(): string {
      if (this.head == null) {
        throw new Error('Stack is empty!');
      }
      const node = this.head;
      this.head = node.next;
      this._size--;
      return node.value;
    }
  }

  const stack = new StackImpl();
  stack.push('apple');
  stack.push('banana');
  console.log(stack);
  console.log(stack.pop());
}

위의 스택 코드를 하나하나 뜯어서 살펴봅시다.
우선 클래스를 만들기 전에 interface와 type을 지정해주었습니다.
interface는 코드 생성자와 사용자간의 계약서입니다.

interface Stack {
    readonly size: number;
    pop(): string;
    push(value: string): void;
  }

Stack이라는 interface를 통해, 코드 생성자는 무조건 해당 interface를 도입한 클래스 내에 size, pop(), push()를 만들어주어야 합니다.
그리고 약속한대로 코드 사용자는 interface에 지정해준 public/readonly 데이터나 메소드를 클래스 밖에서 사용할 수 있습니다.

• size: 스택의 크기로, 스택의 길이를 알 수 있습니다.
• pop(): 스택의 가장 마지막 노드를 제거하고 노드의 값(value)을 리턴합니다.
• push(): 스택의 가장 마지막에 새로운 노드를 추가합니다.

위에서 말한 노드를 만들기 위해서 StackNode의 타입을 지정해주겠습니다.

type StackNode = {
    readonly value: string;
    readonly next?: StackNode;
  };

StackNode라는 타입을 지정받은 경우, 위와 같은 데이터를 포함해야 합니다.

• value: 노드의 값을 의미합니다.
• next: 해당 노드의 다음 노드가 무엇인지를 가리킵니다.

다음으로는 클래스를 살펴봅시다.

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

    get size() {
      return this._size;
    }

    push(value: string) {
      const node: StackNode = {
        value,
        next: this.head,
      };
      this.head = node;
      this._size++;
    }

    pop(): string {
      if (this.head == null) {
        throw new Error('Stack is empty!');
      }
      const node = this.head;
      this.head = node.next;
      this._size--;
      return node.value;
    }
  }

클래스 내부에서 우선 _size를 0으로 초기화해줍니다. 그리고 외부에서 _size에 접근하지 못하도록 private으로 지정한 뒤, 게터함수(get())를 사용합니다.
게터함수를 사용하면, 외부에서 size 정보를 요청했을 때, _size를 리턴하여 private한 _size 정보를 가져올 수 있습니다. 이 때, readonly를 사용하면 클래스 내부에서조차 값을 변경할 수 없기 때문에 private과 get()을 사용합니다.

push() 에서는 value를 인자로 받아서 StackNode 타입의 node를 생성합니다. node 내부에는 인자로 받은 value를 value에 저장하고 next로 현재 헤드(this.head)를 가리킵니다. 첫 번째로 push하는 경우에는 헤드에 아무 것도 없기 때문에 null 인 this.head가 저장됩니다.
그 후 생성된 node를 this.head에 저장합니다. 이 과정은 다음 노드가 들어왔을 경우 this.head에 저장된 노드를 다음노드가 가리키기 위해 저장하는 것입니다.

pop() 에서는 우선 스택이 비어있는 상태인지 확인합니다. this.head가 null인 상태라면, 스택이 비었다는 에러를 내보냅니다. 스택에 노드가 있다면(비어있는 상태가 아니라면), 기존의 헤드를 새로운 노드에다가 저장한 뒤, 기존 헤드는 node의 next에 저장합니다. 가장 위에 있는 아이템을 무시하는 방법입니다.

실제로 인스턴스를 생성하여 콘솔에 출력해보면 잘 동작하는 것을 확인할 수 있습니다.