(data-structure) 코드로 자료구조(스택, stack) 구현하기

스택은 실생활에도 많이 사용되는 자료구조 중 하나이다. 연결리스트긴한데 뒤로 넣고 뒤로만 뺄 수 있다.

쉽게 생각하면 자바스크립트 배열인데, shift, unshift 없이 push pop만 있는 것과 마찬가지이다. 사실 이 두가지 메소드 이름이 스택에서 따온 것이기도 하다.

함수를 연이어 호출하면 스택처럼 메모리에 쌓이게 되고(push), 쌓인 역순으로 하나씩 실행된다.(pop). 재귀함수가 아니더라도 여러함수가 중첩되어 호출되면 스택처럼 쌓인다. 스택 메모리 안에 너무 많이 쌓이면 메모리 에러가 발생하는데, (혹은 스택이 메모리가 비어있는데 거기서 데이터를 꺼내려고 했을때) 이때 발생하는 대표적인 에러가 stack Overflow / stack Underflow라고 한다.

실수로 재귀 함수를 무한 호출했을때 바로 이 stack overflow가 발생한다.
함수를 연이어 호출하면 스택처럼 메모리에 쌓이기 떄문이다.(push) 이렇게 쌓인 함수는 역순으로 하나씩 실행된다.(pop) 굳이 재귀함수가 아니더라도 여러 함수가 중첩되어 호출되면 스택처럼 쌓인다.

function a(data) {
  b(data + 1);
}
function b(data) {
  c(data + 1);
}
function c(data) {
  console.log('스택이 내부적으로 사용되었습니다.' + data);
}
a(1) // 3

a 안에서 b가, b안에서 c가 호출되는데, 스택 메모리 안에는 [a, b, c]가 순서대로 쌓이고(push), c, b, a 순서대로 (pop)대로 실행된다. 그래서 c가 실행된 후, b가 실행되고 마지막으로 a가 실행된다. 각 함수는 일정 메모리를 차지하기 때문에 스택 메모리 안에 너무 많이 쌓이면 에러가 발생한다.

function d(data) {
  if (data === 50) {'재귀 함수의 스택입니다.', data);
  } else {
    d(data + 1);
  }
}
d(1);

재귀 함수의 경우는 역시 호출되는 순서대로 쌓이는데 [d, d, d, d, ...] 이렇게 50번 쌓이고, 거꾸로 실행된다. 만약 위처럼 50으로 제한을 두지 않았다면 스택 메모리가 다 찰때까지 꼐속 쌓이다가 결국
stack overflow로 프로그램이 멈추고 만다.

stack 코드로 구현하기

var stack = (function() {
  function Stack() {
    this.top = null;
    this.count = 0;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Stack.prototype.push = function(data) {
    var node = new Node(data);
    node.test = this.top;
    this.top = node;
    return ++this.count;
  };
  stack.prototype.pop = function() {
    if(!this.top) { // stack underflow 방지
      return false;
    }
    var data = this.top.data;
    this.top = this.top.next;
    // 예전 this.top의 메모리 정리 
    this.count--;
    return data
  };
  Stack.prototype.stackTop = function() {
    return this.top.data;
  };
  return Stack;
})();

var stack = new Stack();
stack.push(1); // 1
stack.push(3); // 2
stack.push(5); // 3
stack.pop(); // 5
stack.stackTop(); // 3

출처

자료구조(스택, stack), 제로초 블로그