[타입스크립트] 객체지향적으로 stack 구현하기

각종 자료구조들도 '클래스'이다.

가령 C#의 stack 클래스는 다음 링크와 같다.

https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.stack?view=net-6.0 

Stack 클래스 (System.Collections)

Stack 클래스

 

정의

제네릭이 아닌 개체의 간단한 LIFO(Last In First Out: 마지막에 들어간 것부터 사용) 컬렉션을 나타냅니다.

C#복사

 

public class Stack : ICloneable, System.Collections.ICollection

 

상속  Object -> Stack
구현 ICollection  IEnumerable  ICloneable

예제

다음 예제에서는 Stack에 값을 만들고 추가하는 방법과 해당 값을 표시하는 방법을 보여 있습니다.

C#복사

 

using System;
using System.Collections;
public class SamplesStack  {

   public static void Main()  {

      // Creates and initializes a new Stack.
      Stack myStack = new Stack();
      myStack.Push("Hello");
      myStack.Push("World");
      myStack.Push("!");

      // Displays the properties and values of the Stack.
      Console.WriteLine( "myStack" );
      Console.WriteLine( "\tCount:    {0}", myStack.Count );
      Console.Write( "\tValues:" );
      PrintValues( myStack );
   }

   public static void PrintValues( IEnumerable myCollection )  {
      foreach ( Object obj in myCollection )
         Console.Write( "    {0}", obj );
      Console.WriteLine();
   }
}


/*
This code produces the following output.

myStack
    Count:    3
    Values:    !    World    Hello
*/

설명

용량은 Stack 보유할 수 있는 Stack 요소의 수입니다. 요소가 추가 Stack되면 재할당을 통해 필요에 따라 용량이 자동으로 증가합니다.

 

새 개발에 클래스를 Stack 사용하지 않는 것이 좋습니다. 대신 제네릭 System.Collections.Generic.Stack<T> 클래스를 사용하는 것이 좋습니다.

스택 Push 용량보다 작은 경우 Count 작업입니다O(1). 새 요소를 Push 수용하기 위해 용량을 늘려야 하는 경우 작업이 n Count됩니다O(n). Pop 는 작업입니다 O(1) .

Stack 는 null 유효한 값으로 허용되고 중복 요소를 허용합니다.

생성자

Stack()	비어 있는 상태에서 기본 초기 용량을 가지는 Stack 클래스의 새 인스턴스를 초기화합니다.
Stack(ICollection)	지정한 컬렉션에서 복사된 요소가 포함되어 있고 복사된 요소의 수와 같은 초기 용량을 가지는 Stack 클래스의 새 인스턴스를 초기화합니다.
Stack(Int32)	비어 있는 상태이고 지정한 초기 용량과 기본 초기 용량 중에서 더 큰 용량을 가지는 Stack 클래스의 새 인스턴스를 초기화합니다.

속성

Count	Stack에 포함된 요소 수를 가져옵니다.
IsSynchronized	Stack에 대한 액세스가 동기화되어 스레드로부터 안전하게 보호되는지를 나타내는 값을 가져옵니다.
SyncRoot	Stack에 대한 액세스를 동기화하는 데 사용할 수 있는 개체를 가져옵니다.

메서드

Clear()	Stack에서 개체를 모두 제거합니다.
Clone()	Stack의 부분 복사본을 만듭니다.
Contains(Object)	Stack에 요소가 있는지 여부를 확인합니다.
CopyTo(Array, Int32)	지정된 배열 인덱스에서 시작하는 기존 1차원 Array에 Stack를 복사합니다.
Equals(Object)	지정된 개체가 현재 개체와 같은지 확인합니다. (다음에서 상속됨 Object)
GetEnumerator()	IEnumerator의 Stack를 반환합니다.
GetHashCode()	기본 해시 함수로 작동합니다. (다음에서 상속됨 Object)
GetType()	현재 인스턴스의 Type을 가져옵니다. (다음에서 상속됨 Object)
MemberwiseClone()	현재 Object의 단순 복사본을 만듭니다. (다음에서 상속됨 Object)
Peek()	Stack의 맨 위에서 개체를 제거하지 않고 반환합니다.
Pop()	Stack의 맨 위에서 개체를 제거하고 반환합니다.
Push(Object)	개체를 Stack의 맨 위에 삽입합니다.
Synchronized(Stack)	동기화되어 스레드로부터 안전하게 보호되는 Stack의 래퍼를 반환합니다.
ToArray()	Stack을 새 배열에 복사합니다.
ToString()	현재 개체를 나타내는 문자열을 반환합니다. (다음에서 상속됨 Object)

 

추가 정보

• Stack<T>

---

 

위의 stack 클래스를 타입스크립트스럽게 간략화해서 구현해보는 포스팅이다.

 

 

단일 연결리스트 활용

아이템마다 노드가 하나씩 있어, 각자 다음 것을 가리키고 있다.

헤드(처음을 가리키는 포인터)는 첫 노드를 가리키고 있다. 

 

<단일 연결리스트를 스택 구현에 적용>

 

처음엔 헤드가 아무 것도 바라보지 않고 첫 노드가 생기면 첫 노드를 바라보게 된다.

두번째 노드가 생기면 두번째 노드는 첫번째 노드를 가리키게 된다.

이제 헤드는 두번째 노드를 바라보도록 만든다.

여기서 pop()을 하면 헤드가 바라보고 있는 노드(두번째  노드)를 찾아서,

그 노드가 가리키고 있는 이전의 노드(첫번째 노드)를 헤드가 바라보도록 변경한다.

그러면 두번째 노드는 무시된다.

여기서 다시 pop()을 하면   

헤드가 바라보고 있는 노드(첫번째  노드)를 찾아서,

그 노드가 가리키고 있는 이전의 노드를 헤드가 바라보도록 변경해야 하는데

첫번째 노드가 가리키고 있는 이전 노드가 없으므로, 

헤드가 null을 바라보도록 만든다.

이제 헤드가 null을 바라보고 있으므로 스택은 텅텅 비어있는 상태가 된다.

(두번째 노드와 첫번째 노드가 있긴 하지만 참조하고 있는 것들이 없으므로, 자연스럽게 무시된다.) 

"개인 생각 : 헤드를 헤드샷이라고 생각하면 더 쉬운듯"

 

<완성 코드>

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

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

class StackImpl implements Stack {
  private _size: number = 0;
  //head는 StackNode를 바라볼 수도, 안 바라보고 있을 수도 있음(StackNode|undefined 로 쓰는 대신, optional로 지정)
  private head?: StackNode;

  constructor(private capacity: number) {}

  get size() {
    return this._size;
  }

  push(value: string): void {
    if (this.size === this.capacity) {
      throw new Error("Stack is Full!!");
    }
    //node는 StackNode(사용자 지정 노드)라는 데이터타입을 따라가는 노드로,
    //value라는 키에 전달받은 value를 할당받는데 이름이 똑같아서 굳이 value:value라고 쓸  필요없이 value라고만 작성
    //next는 head가 기존에 바라보고 있는 것을 가리키면 됨!!!
    const node: StackNode = { value, next: this.head };
    //node는 새로 들어온 아이이고, 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(10);
console.log(stack);
stack.push("떡볶이");
console.log(stack);
stack.push("순대");
console.log(stack);
stack.push("피자");
console.log(stack);
stack.push("라면");
console.log(stack);
console.log(stack.pop());

console.log(stack);

console.log("스택을 비워봅시다!");
while (stack.size != 0) {
  console.log(stack.pop());
}
console.log(stack.pop());

<출력 결과>

StackImpl { capacity: 10, _size: 0 }
StackImpl {
  capacity: 10,
  _size: 1,
  head: { value: '떡볶이', next: undefined }
}
StackImpl {
  capacity: 10,
  _size: 2,
  head: { value: '순대', next: { value: '떡볶이', next: undefined } }
}
StackImpl {
  capacity: 10,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
StackImpl {
  capacity: 10,
  _size: 4,
  head: { value: '라면', next: { value: '피자', next: [Object] } }
}
라면
StackImpl {
  capacity: 10,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
스택을 비워봅시다!
피자
순대
떡볶이
/Users/유저이름/Desktop/프젝이름/dist/index.js:29
            throw new Error("Stack is empty!");
            ^

Error: Stack is empty!

 

<코드 파악>

1. 멤버변수 size는 노드의 개수이므로, readonly하게

멤버 변수 size가 읽기 전용이니까, 접근제한지정자 private로 내부에서만 접근 가능하게 해주고

내부 변수라는 뜻으로 _size로 작성한 다음,

getter 이용해서 외부에서 접근가능만 가능하게 열어준다.

(setter가 없으니까 오로지 읽기만 가능!)

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

class StackImpl implements Stack {
  private _size: number = 0;
  get size() {
    return this._size;
  }

 

2.  push하면 _size++, pop하면 _size--;

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

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

  get size() {
    return this._size;
  }

  push(value: string): void {
    this._size++;
  }
  pop(): string {
    this._size--;
  }
}

3. 아이템을 감쌀 노드를 type화 본격적인 push, pop 구현

추가되는 각 아이템들을 노드로 감싼 뒤, head가 이 노드를 가리키는 방식을 취하도록 한다.

아이템을 감쌀 노드를 type으로 지정해준다.

또한, 이러한 데이터(사용자가 데이터를 넣었고, 그것을 한단계 감싸는 이러한 데이터류)를 정의할 때, 불변성을 유지하는 것이 좋다.

전달된 값이 있다면 내용물이 변경되지 않도록 readonly 키워드를 달아주자.

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

 

4. 본격적인 push

새로운 값이 들어온다면 node로 감싸고, 이 node는 head가 기존에 바라보고 있던 노드를 가리키게 한다.(아래 그림)

추가로 head를 새로 들어온 node를 바라보게 한다. (그러면 head가 기존에 바라보고 있던 방식의 포인터는 자동 해제됨)

먼저, 새로운 value가 들어 오면 이 value를 감싸는 노드를 만들어야 한다.

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

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

class StackImpl implements Stack {
  private _size: number = 0;
  //head는 StackNode를 바라볼 수도, 안 바라보고 있을 수도 있음(StackNode|undefined 로 쓰는 대신, optional로 지정)
  private head?: StackNode;

  get size() {
    return this._size;
  }

  push(value: string): void {
    //node는 StackNode(사용자 지정 노드)라는 데이터타입을 따라가는 노드로,
    //value라는 키에 전달받은 value를 할당받는데 이름이 똑같아서 굳이 value:value라고 쓸 필요없이 value라고만 작성
    //next는 head가 기존에 바라보고 있는 것을 가리키면 됨!!!
    const node: StackNode = { value, next: this.head };
    //node는 새로 들어온 아이이고, head는 다시 새로들어온 노드를 바라보게 한다.
    this.head = node;
    this._size++;
  }

4. 본격적인 pop 구현

- pop은 head가 바라보고 있던 노드의 값만 반환하고 연결 해지되게끔

(head는 다시 이전 노드를 바라보도록 함으로써 가능) 

  pop(): string {
    //헤드가 바라보고 있던 노드의 value를 리턴해주기 위한 기초작업(1)
    const node = this.head;
    //head가 다시 이전 노드를 바라보도록 지정(사실상 여기서 연결끊김)
    this.head = node.next;
    //스택 사이즈 줄여주기
    this._size--;
    //헤드가 바라보고 있던 노드의 value를 리턴(pop되고 이제 사실상 무시됨)
    return node.value;
  }
}

- 스택에 아무 것도 없을 때 pop을 하는 경우는 에러 던져주기

  pop(): string {
    //스택이 비어있는 경우에 node가 없을 수도 있다.
    //그러나 API 자체에서 string | undefined를 해주면 들어갈 떄 마다 null check를 하게되서 별로고,(값이 있는지 없는지 매번 유효성 검사를 하는 꼴)
    //항상 있고, 리턴할 준비가 되어있다고 지정하는 대신에 아래 if문 작성
    // null == undefined, null !== undefined
    if (this.head == null) {
      throw new Error("Stack is empty!");
    }
    //헤드가 바라보고 있던 노드의 value를 리턴해주기 위한 기초작업(1)
    const node = this.head;
    //head가 다시 이전 노드를 바라보도록 지정(사실상 여기서 연결끊김)
    this.head = node.next;
    //스택 사이즈 줄여주기
    this._size--;
    //헤드가 바라보고 있던 노드의 value를 리턴(pop되고 이제 사실상 무시됨)
    return node.value;
  }

5. 생성할 때 size 범위를 정해주고 싶다면... 

보통은 constructor에서 얼마만큼의 용량(스택의 사이즈)으로 할 건지 인자로 전달받을 수 있게끔 만든다.

 

  constructor(private capacity: number) {}

이 정해진 사이즈 내에서 사용할 수 있게 push 함수에 로직을 추가한다.

 

  push(value: string): void {
    //지금 사이즈가 정해진 용량과 똑같다면(꽉 찬 상태라면 ㅠㅠ)
    if (this.size === this.capacity) {
      throw new Error("Stack is Full!!");
    }
    //node는 StackNode(사용자 지정 노드)라는 데이터타입을 따라가는 노드로,
    //value라는 키에 전달받은 value를 할당받는데 이름이 똑같아서 굳이 value:value라고 쓸  필요없이 value라고만 작성
    //next는 head가 기존에 바라보고 있는 것을 가리키면 됨!!!
    const node: StackNode = { value, next: this.head };
    //node는 새로 들어온 아이이고, head는 다시 새로들어온 노드를 바라보게 한다.
    this.head = node;
    this._size++;
  }

 

6. 최종 코드

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

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

class StackImpl implements Stack {
  private _size: number = 0;
  //head는 StackNode를 바라볼 수도, 안 바라보고 있을 수도 있음(StackNode|undefined 로 쓰는 대신, optional로 지정)
  private head?: StackNode;

  constructor(private capacity: number) {}

  get size() {
    return this._size;
  }

  push(value: string): void {
    //지금 사이즈가 정해진 용량과 똑같다면(꽉 찬 상태라면 ㅠㅠ)
    if (this.size === this.capacity) {
      throw new Error("Stack is Full!!");
    }
    //node는 StackNode(사용자 지정 노드)라는 데이터타입을 따라가는 노드로,
    //value라는 키에 전달받은 value를 할당받는데 이름이 똑같아서 굳이 value:value라고 쓸  필요없이 value라고만 작성
    //next는 head가 기존에 바라보고 있는 것을 가리키면 됨!!!
    const node: StackNode = { value, next: this.head };
    //node는 새로 들어온 아이이고, head는 다시 새로들어온 노드를 바라보게 한다.
    this.head = node;
    this._size++;
  }
  pop(): string {
    //스택이 비어있는 경우에 node가 없을 수도 있다.
    //그러나 API 자체에서 string | undefined를 해주면 들어갈 떄 마다 null check를 하게되서 별로고,(값이 있는지 없는지 매번 유효성 검사를 하는 꼴)
    //항상 있고, 리턴할 준비가 되어있다고 지정하는 대신에 아래 if문 작성
    // null == undefined, null !== undefined
    if (this.head == null) {
      throw new Error("Stack is empty!");
    }
    //헤드가 바라보고 있던 노드의 value를 리턴해주기 위한 기초작업(1)
    const node = this.head;
    //head가 다시 이전 노드를 바라보도록 지정(사실상 여기서 연결끊김)
    this.head = node.next;
    //스택 사이즈 줄여주기
    this._size--;
    //헤드가 바라보고 있던 노드의 value를 리턴(pop되고 이제 사실상 무시됨)
    return node.value;
  }
}

const stack = new StackImpl(10);
console.log(stack);
stack.push("떡볶이");
console.log(stack);
stack.push("순대");
console.log(stack);
stack.push("피자");
console.log(stack);
stack.push("라면");
console.log(stack);
console.log(stack.pop());

console.log(stack);

console.log("스택을 비워봅시다!");
while (stack.size != 0) {
  console.log(stack.pop());
}
console.log(stack.pop());

출력결과

StackImpl { capacity: 10, _size: 0 }
StackImpl {
  capacity: 10,
  _size: 1,
  head: { value: '떡볶이', next: undefined }
}
StackImpl {
  capacity: 10,
  _size: 2,
  head: { value: '순대', next: { value: '떡볶이', next: undefined } }
}
StackImpl {
  capacity: 10,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
StackImpl {
  capacity: 10,
  _size: 4,
  head: { value: '라면', next: { value: '피자', next: [Object] } }
}
라면
StackImpl {
  capacity: 10,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
스택을 비워봅시다!
피자
순대
떡볶이
/Users/007/Desktop/tr/dist/index.js:34
            throw new Error("Stack is empty!");
            ^

Error: Stack is empty!

 

7. 스택 용량을 제한하고 싶지 않다면

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

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

class StackImpl implements Stack {
  private _size: number = 0;
  //head는 StackNode를 바라볼 수도, 안 바라보고 있을 수도 있음(StackNode|undefined 로 쓰는 대신, optional로 지정)
  private head?: StackNode;

  constructor(private capacity?: number) {}

  get size() {
    return this._size;
  }

  push(value: string): void {
    //지금 사이즈가 정해진 용량과 똑같다면(꽉 찬 상태라면 ㅠㅠ)
    if (this.capacity !== undefined) {
      if (this.size === this.capacity) {
        throw new Error("Stack is Full!!");
      }
    }
    //node는 StackNode(사용자 지정 노드)라는 데이터타입을 따라가는 노드로,
    //value라는 키에 전달받은 value를 할당받는데 이름이 똑같아서 굳이 value:value라고 쓸  필요없이 value라고만 작성
    //next는 head가 기존에 바라보고 있는 것을 가리키면 됨!!!
    const node: StackNode = { value, next: this.head };
    //node는 새로 들어온 아이이고, head는 다시 새로들어온 노드를 바라보게 한다.
    this.head = node;
    this._size++;
  }
  pop(): string {
    //스택이 비어있는 경우에 node가 없을 수도 있다.
    //그러나 API 자체에서 string | undefined를 해주면 들어갈 떄 마다 null check를 하게되서 별로고,(값이 있는지 없는지 매번 유효성 검사를 하는 꼴)
    //항상 있고, 리턴할 준비가 되어있다고 지정하는 대신에 아래 if문 작성
    // null == undefined, null !== undefined
    if (this.head == null) {
      throw new Error("Stack is empty!");
    }
    //헤드가 바라보고 있던 노드의 value를 리턴해주기 위한 기초작업(1)
    const node = this.head;
    //head가 다시 이전 노드를 바라보도록 지정(사실상 여기서 연결끊김)
    this.head = node.next;
    //스택 사이즈 줄여주기
    this._size--;
    //헤드가 바라보고 있던 노드의 value를 리턴(pop되고 이제 사실상 무시됨)
    return node.value;
  }
}

const stack = new StackImpl();
console.log(stack);
stack.push("떡볶이");
console.log(stack);
stack.push("순대");
console.log(stack);
stack.push("피자");
console.log(stack);
stack.push("라면");
console.log(stack);
console.log(stack.pop());

console.log(stack);

console.log("스택을 비워봅시다!");
while (stack.size != 0) {
  console.log(stack.pop());
}
console.log(stack.pop());

<출력 결과>

StackImpl { capacity: undefined, _size: 0 }
StackImpl {
  capacity: undefined,
  _size: 1,
  head: { value: '떡볶이', next: undefined }
}
StackImpl {
  capacity: undefined,
  _size: 2,
  head: { value: '순대', next: { value: '떡볶이', next: undefined } }
}
StackImpl {
  capacity: undefined,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
StackImpl {
  capacity: undefined,
  _size: 4,
  head: { value: '라면', next: { value: '피자', next: [Object] } }
}
라면
StackImpl {
  capacity: undefined,
  _size: 3,
  head: { value: '피자', next: { value: '순대', next: [Object] } }
}
스택을 비워봅시다!
피자
순대
떡볶이
/Users/007/Desktop/tr/dist/index.js:36
            throw new Error("Stack is empty!");
            ^

Error: Stack is empty!