JavaScript로 Stack 자료 구조 구현하기

JavaScript로 Stack 자료 구조 구현하기

 

Stack 이란?

Stack은 언제나 목록의 끝에서만 작업이 일어나는 자료구조를 말합니다.

그래서 마치 접시 쌓기와 비슷하기도 합니다.

접시를 쌓으면 제일 위에서만 쌓이고,

접시를 뺄 때도 제일 위에서만 뺄 수 있습니다.

이를 LIFO (Last In Firsh Out)라고도 합니다.

가장 나중에 들어온 것이 가장 먼저 나간다는 의미입니다.

 

Stack에서 자료가 들어오는 것은 Push라고 하고,

꺼내는 것을 Pop이라고 합니다.

 

만약 S를 스택이라고 하고, x를 데이터요소라고 한다면 다음과 같은 연산이 가능합니다.

 

S.top() : 스택의 가장 윗 데이터 반환. 만약 스택이 비어 있으면 연산 정의 불가

S.pop() : 스택의 가장 윗 데이터 삭제. 만약 스택이 비어 있으면 연산 정의 불가

S.push() : 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성 데이터 x를 넣는다.

S.empty() : 스택이 비었다면 1을 반환하고 그렇지 않으면 0을 반환한다.

 

이 중에서 top, pop, push 매소드만 구현해보았다.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  
 // 해당 stack은 모든 연산이 top에서만 일어난다.
 // 새로 추가될 때, top을 늘려주고
 // 제거될 때, top을 줄여준다면, top으로 크기를 정의할 수 있을 것이다.
  size() {
    return this.top;
  }


// 객체로 이루어진 storage에서 키와 값으로 element를 저장하고,
// top을 1 늘려준다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }


// 객체로 이루어진 storage에서 키를 삭제하는데,
// 삭제하기 전에 temp로 보관해준 다음,
// return 해준다. 그런데 여기서 인덱스에 -1 인 이유는,
// top 은 말그대로 길이이기 때문에 인덱스가 -1인 것이다.
  pop() {
    let temp;
    if (this.top > 0) {
      temp = this.storage[this.top - 1];
      delete this.storage[this.top - 1];
      this.top -= 1;
    }
    return temp;
  }
}

---

다양한 자료와 글을 참고하여 배우고 있는 개발 뉴비의 블로그입니다. 
수정 보완할 것이 있다면 부담없이 댓글 남겨주세요 :)

 

JavaScript로 Stack 자료 구조 구현하기