[Typescript] 단일 연결 리스트 Stack 구조 만들기

[ String 타입만 받는 Stack ]

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

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

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

    constructor(private capacity: number) {}
    
    get size() { return this._size; }

    push(value: string) {
        if (this.capacity === this.size) { throw new Error(`This Stack is Full!`); } 
        const node: StackNode = { value, next: this.head };
        this.head = node;
        this._size++;
    }

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


const stack = new Stack_Impl(10);

for(let i = 1; i < 10; i++) {
    stack.push(`Stack ${i}`);
}

while (stack.size !== 0) {
  console.log(stack.pop());
}

stack.pop();

/*
[결과]

Stack 9
Stack 8
Stack 7
Stack 6
Stack 5
Stack 4
Stack 3
Stack 2
Stack 1

C:\Users\...\stack.ts:33
            throw new Error ('This Stack is Empty!');
                  ^
Error: This Stack is Empty!
*/

[문제]

• 기본적으로 내장된 Array, push, pop를 사용하지 않고 단일 연결 리스트 구성의 Stack을 구현하여라.

[생각한 것 들]

1. Stack 구조 만드는데 필요한 변수나 매서드들을 생각한 후 interface 생성.
2. 배열 대신 사용할 스택 노드 타입 생성.
3. constructor로 생성시 Stack의 크기(capacity)를 받아와 push와 pop의 Error 조건으로 사용.
4. Stack Class 내부적으로 사용할 _size(node의 개수 파악 용도)와 head(노드의 value와 다음 node를 가리킴) 변수.

[의문점]

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

• pop 매서드의 Error조건을 만들시, 조건을 this.head === null 로 하면 node 타입이 optional로 파악되어 undefined가 될 가능성이 있어 오류가 발생함.
• 그러나 조건이 this.head == null 일시, 타입이 StackNode로 고정됨.

조건이 this.head === null 일때..  

• '=='는 동등 연산자이고 '==='는 일치 연산자 이다.
• '=='는 값만 비교하지만, '==='는 값과 타입을 같이 비교한다.
• 만약 '===' 을 쓰려고 한다면 null 대신 undefined를 사용하면 된다.

  ---

+ 제네릭을 이용한 모든 타입을 받는 Stack

interface Stack<T> {
    readonly size: number;
    push(value: T): void;
    pop(): T;
  }
  
  type StackNode<T> = {
    readonly value: T;
    readonly next?: StackNode<T>;
  };
  
  class StackImpl<T> implements Stack<T> {
    private _size: number = 0;
    private head?: StackNode<T>;
  
    constructor(private capacity: number) {}
    get size() {
      return this._size;
    }
    push(value: T) {
      if (this.size === this.capacity) {
        throw new Error('Stack is full!');
      }
      const node = { value, next: this.head };
      this.head = node;
      this._size++;
    }
    pop(): T {
      if (this.head == null) {
        throw new Error('Stack is empty!');
      }
      const node = this.head;
      this.head = node.next;
      this._size--;
      return node.value;
    }
  }