2. 스택 ( Stack, JavaScript 구현 )

스택 ( Stack )

스택은 보통 큐와 비교해서 알아보는데 우선 스택에 대해 알아보자.

stack 이란?

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다.

그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

쉽게 한쪽이 막힌 통이라고 생각하면 된다.

개발자라면 한번쯤 들어가봤을 사이트 stack overflow에서 그 스택이 이 스택이다.

의미는 스택이 꽉차있는데 push로 삽입하려 하는 것을 stack overflow,

스택이 비어있는데 pop으로 제거하려 하는 것을 stack underflow 라 부르며,

스택을 만들 때는 위의 두가지를 예외처리 해줘야 한다.

 

구조

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

자료를 넣는 것을 ‘밀어넣는다’ 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다.

이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

자바스크립트에서는 이미 배열 메소드에 push, pop메소드가 있어 스택처럼 사용할 수 있지만, 직접 구현해 보면서 이해를 도와보자.

 

언제 사용하는가?

1. 브라우저 방문 기록(뒤로가기)
2. 실행 취소(undo)
3. 역순 문자열 만들기
4. 수식의 괄호 검사
5. 후위표기법 계산

위와 같은 경우가 있고, 추가로 다른분이 쓴 글을 덧붙임.
큐와 스택의 실제 사용 에

 

구현

스택을 링크드 리스트리스트로 구현해보자.

우선 스택을 정의해주면 다음과 같다.

const Stack = (() => {
    class Stack {
        constructor() {
            this.top = null;
            this.count = 0;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Stack;
})()

Stack클래스에 top은 가장 위의 노드, count는 노드의 개수이다.

1. push()

push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    return ++this.count;
}

푸시로 새로운 값을 넣어주면 현재 top을 다음으로 밀고, top에 새로운 값을 넣어준다.

리턴 값은 현재 스택의 크기를 반환해주는데, 콘솔창에서 자바스크립트로 push를 해보면 스택 크기가 리턴되는 것을 알 수 있다.

2. pop()

pop() {
    if ( !this.top ) {
        return false;
    }
    const data = this.top.data;
    this.top = this.top.next;
    this.count--;
    return data;
}

if문은 스택이 비었을 때 pop을 못하도록 하는 것, 즉 stack underflow방지를 위해 넣은 코드.

pop을 실행시 현재 탑의 데이터를 data에 담고, top을 현재 탑의 next로 바꿔주고 크기를 1줄인 뒤에 data를 리턴해준다.

3. peek()

peek() {
    return this.top.data;
}

최상단 노드의 데이터를 리턴

 

전체 코드

const Stack = (() => {
    class Stack {
        constructor() {
            this.top = null;
            this.count = 0;
        }

        push(value) {
            const node = new Node(value);
            node.next = this.top;
            this.top = node;
            return ++this.count;
        }

        pop() {
            if ( !this.top ) {
                return false;
            }
            const data = this.top.data;
            this.top = this.top.next;
            this.count--;
            return data;
        }

        peek() {
            return this.top.data;
        }
    }

    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Stack;
})()