이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌11 - Algorithm - 2년 전 등록 / 5달 전 수정

자료구조(스택, stack)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 스택에 대해 알아보겠습니다!

스택은 실생활에도 많이 사용되는 자료구조 중 하나입니다. 연결 리스트인데 뒤로 넣고 뒤로만 뺄 수 있습니다. 앞으로는 넣지도, 빼지도 못합니다. 쉽게 생각하면 자바스크립트 배열인데 shift, unshift 없이 pushpop만 있다고 생각하시면 됩니다. 사실 push와 pop이라는 메소드 이름이 스택에서 나온 겁니다. 또 한 가지의 메소드는 stackTop으로 스택의 마지막 요소를 알려주는 겁니다. 스택의 마지막 요소를 top이라고 부르기도 합니다.

실생활에서는 부엌에 있는 위아래로 쌓여진 접시들을 생각하면 편할 것 같습니다. 새로운 접시는 제일 위에 올리고, 접시를 사용할 때도 제일 위에서부터 꺼내죠? 프로그래밍 상에서도 스택이 자주 사용됩니다. 여러분은 stack overflowstack underflow라는 것을 들어보셨나요? stack overflow는 유명한 해외 프로그래밍 질의응답 커뮤니티이기도 하죠. 각각 주어진 스택 메모리보다 데이터를 더 넣었거나, 스택이 메모리가 비어있는데 거기서 데이터를 꺼내려고 했을 때 발생하는 대표적인 에러입니다. 실수로 재귀 함수를 무한 호출했을 때 stack overflow가 발생하죠.

잠깐, 재귀 함수를 호출하는 것과 stack overflow가 무슨 상관일까요? 바로 함수를 연이어 호출하면 스택처럼 메모리에 쌓이기(push) 때문입니다. 쌓인 역순으로 하나씩 실행됩니다(pop). 굳이 재귀 함수가 아니더라도 여러 함수가 중첩되어 호출되면 스택처럼 쌓입니다. 다만 재귀 함수를 사용했을 경우 stack overflow 에러가 자주 발생합니다.

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) {
    console.log('재귀 함수의 스택입니다', data);
  } else {
    d(data + 1);
  }
}
d(1);

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

스택을 직접 객체를 사용해서 만들어봅시다.

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.next = 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

다음 시간에는 에 대해 알아보겠습니다.

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

1개의 댓글이 있습니다.
5달 전
안녕하세요 연재해주시는 글 너무 잘 보고 있습니다.
한가지 궁금한점이
"a 안에서 b가, b 안에서 c가 호출되는데요. 스택 메모리 안에는 [c, b, a]이렇게 호출된 순서대로 쌓이고(push), a, b, c 순서(pop)대로 실행됩니다. 그래서 a가 실행된 후, b가 실행되고 마지막으로 c가 실행됩니다. "
중간에 위와 같이 설명이 있는데 pop할때는 c->b->a 순서로 실행되는게 스택이 아닌가해서요 (first in last out)
구현은 그렇게 되어 있는데 설명에는 이렇게 되어 있어서 댓글적어봅니다.
5달 전
수정했습니다 감사합니다