[JavaScript] Stack(스택)

  자바스크립트에서는 배열 메서드가 정의가 되어 있어 딱히 구현한 필요는 없지만 c언어 같은 로우레벨의 언어에서는 함수들을 정의해줘야 스택의 개념을 쓸 수 있다. 비록 자바스크립트이지만 자료구조의 이해를 위해 해당 개념을 직접 구현해 보려고한다.

 

Stack의 개념

  스택은 LIFO(Last In First Out)의 특징을 가지고 있다. 즉, 아래 그림과 같이 맨 마지막으로 들어갈 f가 제일 처음 꺼내어 진다는 이야기이다. 스택의 최대 단점으로는 제일 먼저 들어간 데이터를 꺼낼 때 모든 데이터를 연산해야한다는 것이다. 데이터 a를 빼내고 싶다면 f, e, d, c, b를 차례대로 꺼낸 후 a를 꺼내고 다시 b, c, d, e, f 순으로 집어 넣어야 한다.

Stack

 

Stack 구현

1. stack이라는 class만들어서 생성자 뼈대 만들기

class stack{
  constructor(size) {
    this.size = size;
    this.indexTop = -1;
    this.array = [];
  }
}

indexTop을 -1로 만들어 준건 array의 갯수가 인덱스번호로 매겨져 -1을 해줘야 하기 때문이다.

 

2. stack에 필요한 메서드 만들기

pop() {
    if(this.indexTop === 0) {
      console.log("Stack is empty");
    }else {
      this.array[this.indexTop] = undefined;
      this.indexTop--;
      return this.array[this.indexTop];
    }
  }

push(item) {
    if(this.size > this.indexTop) {
      this.indexTop++;
      return this.array[this.indexTop] = item;
    }else {
      console.log(new Error("Stack is full"));
    }
  }

peek() {
    return this.array[this.indexTop];
  }
}

기본적으로 pop()과 push() peek() 메서드를 만들었다.

 

3. 전체 코드

class stack{
  constructor(size) {
    this.size = size;
    this.indexTop = -1;
    this.array = [];
  }

  pop() {
    if(this.indexTop === 0) {
      console.log("Stack is empty");
    }else {
      this.array[this.indexTop] = undefined;
      this.indexTop--;
      return this.array[this.indexTop];
    }
  }

  push(item) {
    if(this.size > this.indexTop) {
      this.indexTop++;
      return this.array[this.indexTop] = item;
    }else {
      console.log(new Error("Stack is full"));
    }
  }

  peek() {
    return this.array[this.indexTop];
  }
}

let arr = new stack(2);
arr.push('hi');
arr.push('hello');

console.log(arr);  // stack { size: 2, indexTop: 1, array: [ 'hi', 'hello' ] }

나의 코드의 단점은 pop()을 했을 때 배열의 실제 개수를 줄이지 못하고 undefined로 만든다는 것이다. 또한 arr[index]로 조회가 불가능하다.