[javascript] Stack 구현하기

저번 학기 자료구조는 c언어로 활용하여 수업을 했었는데, c언어는 아주 기초적인 부분 말고는 대부분의 함수가 구현되어 있지않아 힘들게 요구하는 함수들을 정의해야만 했었지만 자바스크립트는 대부분의 기능을 지원해주기 때문에 쉽게 자료구조를 만들 수 있었다. 

 

Stack 이란

stack은  lifo(Last In First Out)의 형태를 취하는 자료구조로써 맨 먼저 들어온 것이 가장 나중에 나가고 가장 최근에 들어온것이 가장 먼저 나간다. 흔히들 접시를 쌓아놓은 구조로 설명하는데 접시를 쌓아 놓고 맨 아래에 있는 접시를 꺼내기위해서는 맨 아래 접시위에 있는 것들은 모두 치워야지 가능하다. 이처럼 스택 또한 데이터를 수직으로 쌓아 놓고 원하는 데이터 위에 아무것도 없어야지만 해당 데이터를 뺄 수 있다.

 

  

스택

 

Stack의 멤버변수

c언어로 만들때는 구조체(struct)를 이용했지만 자바스크립트에서는 구조체가 없어 class로 새로운 객체를 만들어 사용하려 한다. 

 

size // 해당 스택의 max_size

 

top // 해당 스택의 데이터 높이

 

array // 데이터를 담을 배열 

 

constructor(size){
        this.size = size;
        this.top = 0;
        this.array = [];
    }

 

// size를 생성자 인자로 받아온다. 

 

Stack의 기능들

stack을 구현하려면 총 3가지의 기능을 정의 해야 한다. 

 

pop() // 스택에서 가장 최근에 들어온 데이터를 방출하고 그 데이터를 return 하는 함수, stack의 top이 0인데 pop인 경우 에러를 호출

 

push()// 스택의 마지막에 데이터를 입력 하는 함수 ,  size보다 높다면 에러를 호출 

 

peek()// 스택의 마지막 데이터를 return 하는 함수

 

이렇게 있어야 한다. 그러나 javascript는 이미 배열에 대하여 이 기능들을 모두 내부함수로써 가지고 있기에 이 방법들을 직접 구현하며 만들어야 한다. 

 

    pop(){
        let temp = this.array[this.top];
        this.top--;
        return temp;
    }

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

 

조금 더 방어적으로 

해당 클래스는 변수에 할당한후 변수.array.push() 로 사용해 프로퍼티에 직접 영향을 미칠 수 있는 큰 단점이 있다. 실제 스택에서는 그런 것이 용납이 안되니 캡슐화를 통해서 멤버변수를 setting 하지 못하게 막았다. 

 

function Stack(max_size){
    
    const size = max_size;
    let top = 0;
    let array = [];
    
    return{
        pop(){
             if(top==0){
                console.log("stack is empty");
            }else{
                let temp = array[top];
                top--;
                return temp;
            }
        },
    
        push(item){
            if(size > top){
                top++;
                return array[top] = item;
            }else{
                console.log(new Error("stack is full"));
            }
        },
        peek(){
            return array[top];
        }
    }
  
}

var a = Stack(5);

 

결과 

var a = Stack(5);

a.push(1);
a.push(2);
a.push(3);
a.push(4);
a.push(5);
console.log(a.pop()); // 5
console.log(a.peek()); // 4