스택 ( 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. 후위표기법 계산

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

구현

스택을 링크드 리스트리스트로 구현해보자. (참고 : zeroCho님 블로그)

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

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는 데이터의 개수이다.

이제 원소를 삽입하는 push, 제거하는 pop을 구현해 보자.

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

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

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

마찬가지로 pop을 구현해 보자.

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

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

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

아래는 현재 top을 리턴해주는 메소드이다.

top() {
    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;
        }

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

스택 크기 정해서 stack overflow 방지하는 코드도 만들어보고 싶은데,

크기 설정에 대한 개념이 안잡혀 있어서 할 수가 없다. sombody help me..


'자료구조, 알고리즘 > JS 자료구조' 카테고리의 다른 글

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

+ Recent posts