[자바스크립트] Stack 스택 클래스

Stack 클래스 구현

스택이란?

스택은 모든 요소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조 입니다. 삽입이 일어날 경우 스택의 아래쪽에 하나하나 쌓이게 되고 데이터를 꺼내기 위해서는 나중에 삽입된 데이터부터 꺼내야 아래의 데이터에 접근할 수 있는 구조입니다.

자바스크립트로 다음과 같은 기능을 가지는 스택을 구현해 보겠습니다.

변수	설명
dataStore	스택 요소를 저장할 배열
top	스택 최상위 index를 저장할 변수

함수	설명
push(element)	스택에 요소를 저장
pop()	스택에서 요소를 꺼냄
peek()	스택의 최상위 요소를 반환
clear()	스택을 초기화
length()	스택의 길이를 반환

스택 구현 코드입니다.

function Stack() {
    this.dataStore = []; // 스택 요소를 저장하는 배열
    this.top = 0; // 스택의 최상단 index 를 저장하는 변수
    this.push = push; // 스택에 요소를 추가하는 함수
    this.pop = pop; // 스택에서 요소를 꺼내오는 함수
    this.peek = peek; // 스택의 요소를 반환하는 함수
    this.clear = clear; // 스택을 초기화 하는 함수
    this.length = length; // 스택의 길이를 반환하는 함수
}
 
// 스택에 요소를 추가하는 함수
function push(element) {
    this.dataStore[this.top++] = element;
}
 
// 스택에서 요소를 꺼내오는 함수
function pop() {
    return this.dataStore[--this.top];
}
 
// 스택의 요소를 반환하는 함수
function peek() {
    return this.dataStore[this.top -1];
}
 
// 스택을 초기화 하는 함수
// dataStore 배열의 내용은 그대로 이지만
// top이 0을 바라봄으로 인해 
// pop, push 등의 동작에서는
// 남아있는 dataStore의 값을 신경쓰지 않아도 된다.
function clear() {
    this.top = 0;
}
 
// 스택의 길이를 반환하는 함수
function length() {
    return this.top;
}

스택 사용 예제

스택을 활용해서 팩토리얼을 다르게 구현할 수도 있습니다.

// 일반적인 팩토리얼 구현 함수
function factorial(n) {
    if(n < 2) {
        return 1;
    }else {
        return n*factorial(n-1);
    }
}
 
// 스택을 이용한 팩토리얼 구현 함수
function factorial2(n) {
    var stack = new Stack();
    while(n > 1) {
        stack.push(n--);
    }
 
    var result = 1;
    while(stack.length() > 0) {
        result *= stack.pop();
    }
    return result;
}

자바스크립트 자료구조와 알고리즘 국내도서 저자 : 마이클 맥밀런(Michael McMillan) / 우정은역 출판 : 한빛미디어 2014.08.30 상세보기