(Algorithm) 자료구조(스택, stack)

강좌11 - Algorithm - 8년 전 등록 / 일 년 전 수정

자료구조(스택, stack)

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

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

실생활에서는 부엌에 있는 위아래로 쌓여진 접시들을 생각하면 편할 것 같습니다. 새로운 접시는 제일 위에 올리고, 접시를 사용할 때도 제일 위에서부터 꺼내죠? 프로그래밍 상에서도 스택이 자주 사용됩니다. 여러분은 stack overflow나 stack 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로 프로그램이 멈추고 맙니다.

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

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

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

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

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

시간 복잡도와 공간 복잡도는 항상 계산해두는 것이 좋습니다. 새로운 값을 넣는데 O(1), 값을 빼는데 O(1), 제일 위에 값을 확인하는데 O(1)입니다. 공간 복잡도는 O(n)입니다.

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

조회수:

익명

5년 전

객체 선언 시 왜 즉시 호출을 해주는건가요?

ZeroCho

비공개 변수를 만드는 것입니다. 클래스와 비슷한 역할을 합니다.

클래스로 만들어도 되지 않나요? 왜 변수로 만드셨는지 궁금합니다.

es5 기준으로 작성한 코드라서요

아 그렇군요!! 감사합니다!!

6년 전

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

수정했습니다 감사합니다

ZeroCho Blog

게시글

자료구조(스택, stack)

댓글