[자료구조] Stack

Stack이란?

이번 포스팅에서는 자료구종 중에서 스택(Stack)에 대해 정리하겠습니다. 스택은 Last In First Out 구조을 가진 선형 자료구조 입니다. 가장 나중에 들어온 요소가 먼저 나가는 구조입니다.

예시 들자면, 상자에 물건을 차곡차곡 넣었다가 가장 위에 있는 물건을 꺼내 쓴다고 생각할 수 있습니다.

스택에 새로운 요소를 넣는 것을 Push, 꺼내는 것을 Pop이라고 부릅니다. 그리고 가장 위에 있는 요소는 top이라고 부릅니다.

자바스크립트 엔진의 스택 메모리가 바로 스택 자료 구조를 가지고 있습니다. 여러가지 함수가 실행되면 함수가 실행되는 순서대로 매개변수, 지역변수, 반환주소값들이 스택 메모리에 PUSH되어 저장되었다가 마지막 함수 실행이 최종적으로 종료되면 마지막에 호출된 함수부터 차례대로 스택 메모리에서 나가게 됩니다.

Stack 특징

1. LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고 있습니다.

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

Stack 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺍니다. 한꺼번에 여러 개를 넣거나 뺄 수 없습니다.

3. 하나의 입출력 방향을 가지고 있습니다.

Stack 자료구조는 데이터의 입출력 방향이 같습니다. 만약, 입출력 방향이 여러 개라면 Stack 자료구조라고 볼 수 없습니다.

스택은 배열을 활용하거나 클래스로 구현할 수 있습니다. 자바스크립트에서는 배열의 길이가 동적으로 증가하기 때문에 손 쉽게 구현
이 가능합니다.

배열 활용

Array 객체의 내장 메소드 push, pop을 사용하면 스택 구현이 가능합니다. 하지만 데이터가 굉장히 많은 경우에 배열을 사용해서 스택은 구현할 경우 인덱스 지정으로 인한 속도 저하가 있을 수 있습니다.

const stack = [];

stack.push(1)  // [1]
stack.push(2)  // [1,2]
stack.push(3)  // [1,2,3]

stack.pop() // [1, 2]
stack.pop() // [1]

클래스를 활용한 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    return this.top + 1;
  }

  push(el) {
    this.top += 1;
    this.storage[this.top] = el;
  }

  pop() {
    if (this.top < 0) {
      return;
    }

    let result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;

    return result;
  }
}

const stack = new Stack();