[Typescript] 배열 사용하지 않고 Stack 구현하기

스택이란

스택은 쌓는다는 의미로 데이터를 순서대로 쌓아올린 모습을 생각하면 된다.

흔히 LIFO (Last In First Out)라고 표현하며 말 그대로 제일 마지막에 입력한 데이터가 제일 먼저 꺼내진다.

 

자바스크립트의 Array

자바스크립트의 내장 자료구조 중 하나인 배열을 이용하면 스택을 매우 쉽게 구현할 수 있다.

const arr: string[] = [];

arr.push("a");
arr.push("b");
arr.push("c");
arr.push("d");

console.log(arr.pop());  // d
console.log(arr.pop());  // c
console.log(arr.pop());  // b
console.log(arr.pop());  // a

 

Array 메서드 중 push (배열의 끝에 데이터를 입력), 그리고 pop (배열의 마지막 원소를 리턴) 을 이용하면 아주 간단하게 스택을 흉내낼 수 있다.

 

Array를 사용하지 않고 구현

Array를 사용하지 않고도 쉽게 구현가능하다. 바로 연결리스트를 이용하는 것이다.

연결리스트는 데이터와 다음 순서 데이터의 위치 정보까지 가지고 있는 자료구조이다.

이 개념을 잘 이용하면 아주 쉽게 구현가능하다.

보통의 연결리스트는 다음 순서의 위치정보를 가지고 있는데, 구현하다보니 나는 이전 데이터의 순서를 기억하는 꼴이 되어버렸다. 어쨌든 순서대로 연결된 연결리스트이니 큰 차이는 없다.

 

일단 총 코드는 다음과 같다.

interface StackNode {
  prevNode: StackNode | null;
  value: string;
}
class Stack {
  private top: StackNode | null = null;
  private _size: number = 0;

  push(value: string) {
    const pushedNode: StackNode = { value, prevNode: this.top };
    this.top = pushedNode;
    this._size++;
  }
  pop(): string | null {
    if (this.top === null) {
      console.log("this stack is empty!");
      return null;
    }
    const topNode = this.top;
    this.top = topNode.prevNode;
    this._size--;
    console.log("popped : ", topNode.value);
    return topNode.value;
  }
  size(): number {
    console.log("current size is ", this._size);
    return this._size;
  }
  printStack() {
    let current = this.top;

    while (current !== null) {
      console.log(current.value);
      current = current.prevNode;
    }
  }
  peek(): string | null {
    if (this.top === null) {
      console.log("this stack is empty!");
      return null;
    }
    console.log("peek is ", this.top.value);
    return this.top.value;
  }
}

let stack = new Stack();
stack.size(); //current size is 0
stack.pop(); // this stack is empty

stack.push("first floor!");
stack.push("second floor!");
stack.push("third floor!");
stack.printStack();
/*
third floor!
second floor!
first floor!
*/

stack.size(); //current size is  3
stack.pop(); //popped : third floor!
stack.pop(); //popped : second floor!
stack.pop(); //popped : first floor!
stack.pop(); //this stack is empty
stack.size(); //current size is  0

 

내가 구현한 메서드들은 다섯가지 이다.

1. 스택에 쌓인 데이터의 수를 셀 수 있는 size함수

2. 마지막에 입력한 데이터를 뽑아올 pop함수

3. 데이터를 입력할 push함수

4. 현재 스택 상황을 볼 printStack함수

5. 제일 마지막에 쌓인 데이터를 확인 할 peek함수

 

 

1. 먼저 interface를 이용해서 스택에 입력될 데이터 인터페이스를 정의했다.

interface StackNode {
  prevNode: StackNode | null;
  value: string;
}

이전 노드의 정보를 가지고 있을 prevNode, 그리고 현재 데이터를 입력받을 value 등 두 키값을 정의했다.

첫 번째 노드의 경우 이전 노드가 없으므로 null 값을 허용했다.

 

2. Stack 클래스를 정의하고 메서드들을 만들어 쉽게 사용할 수 있게 했다.

Stack 내부에는 top과 _size가 private로 정의되어있다.

top은 제일 마지막에 입력된 데이터를 의미하며, _size는 현재 스택 내부의 데이터 수 이다. ( 언더바를 붙인 이유는 사용할 메서드 size와 이름이 같기 때문이다. )

private로 정의한 이유는 굳이 직접 볼 이유가 없고 내부에서 사용하기 때문이다.

 

3. push 메서드

push(value: string) {
    const pushedNode: StackNode = { value, prevNode: this.top };
    this.top = pushedNode;
    this._size++;
  }

push메서드는 입력받은 데이터를 위에서 정의했던 StackNode 인터페이스 구조로 가공 후 top에 할당하고 size를 +1 하는 함수이다.

 

4. pop 메서드

pop(): string | null {
    if (this.top === null) {
      console.log("this stack is empty!");
      return null;
    }
    const topNode = this.top;
    this.top = topNode.prevNode;
    this._size--;
    console.log("popped : ", topNode.value);
    return topNode.value;
  }

pop메서드는 Stack 클래스의 top에 할당된 데이터의 value를 리턴한다.

하지만 만약 스택이 쌓여있지 않을 수 있으므로 null 타입이 리턴될 수도 있게 하였다.

그 뒤에 size를 -1 해서 갯수를 맞춘다.

 

5. printStack 메서드

 printStack() {
    let current = this.top;

    while (current !== null) {
      console.log(current.value);
      current = current.prevNode;
    }
  }

 

printStack은 top에서 부터 이전 노드를 찾아가면서 prevNode가 null일 때 까지 console에 위에 쌓인 순서대로 찍어준다.

 

6. size와 peek는 아주 간단하니 설명을 생략한다..

 

이렇게 아주 간단하게 stack 자료구조를 구현해봤다.

 

하지만 타입을 위 코드처럼 지정하면 string만 입력받을 수 있는 형태가 된다.

 

만약 number가 쌓이는 구조, 특정 데이터 타입이 쌓이는 구조를 구현하고 싶다면 제네릭을 이용하면 된다.

 

제네릭 사용

{
  interface StackNode<T> {
    prevNode: StackNode<T> | null;
    value: T;
  }
  class Stack<T> {
    private top: StackNode<T> | null = null;
    private _size: number = 0;

    push(value: T) {
      const pushedNode: StackNode<T> = { value, prevNode: this.top };
      this.top = pushedNode;
      this._size++;
    }
    pop(): T | null {
      if (this.top === null) {
        console.log("this stack is empty!");
        return null;
      }
      const topNode = this.top;
      this.top = topNode.prevNode;
      this._size--;
      console.log("popped : ", topNode.value);
      return topNode.value;
    }
    size(): number {
      console.log("current size is ", this._size);
      return this._size;
    }
    printStack() {
      let current = this.top;

      while (current !== null) {
        console.log(current.value);
        current = current.prevNode;
      }
    }
    peek(): T | null {
      if (this.top === null) {
        console.log("this stack is empty!");
        return null;
      }
      console.log("peek is ", this.top.value);
      return this.top.value;
    }
  }

  let stack = new Stack<string | number | object>();
  stack.size(); //current size is 0
  stack.pop(); // this stack is empty

  stack.push(1);
  stack.push("second floor!");
  stack.push({ objet: "object" });
  stack.printStack();
  /*
second floor!
1
current size is  3
*/

  stack.size(); //current size is  3
  stack.pop(); //popped : { objet: 'object' }
  stack.pop(); //popped : second floor!
  stack.pop(); //popped : 1
  stack.pop(); //this stack is empty
  stack.size(); //current size is  0
}

 

제네릭을 입력받는 부분에서 string | number | object 가 올 수 있도록 지정했기 때문에 위 예시코드처럼 여러가지 자료구조가 들어갈 수 있게 되었다.