Stack

자바스크립트로 간단하게 구현해 보는 Stack의 데이터 구조

Stack은 후입선출(LIFO)의 원칙을 따르며, 새로운 항목의 추가 또는 제거는 스택의 끝 부분(상단)에서 발생한다. 또한 LIFO의 원칙을 따르기 때문에 요소(Element)의 추가 또는 제거 등에 사용할 수 있는 기능을 제한해야 한다.

배열 기반의 Stack class

자바스크립트에서 Stack 클래스를 생성하기 위해서 가장 쉽게 고려할 수 있는 것은 배열을 사용해서 스택의 요소(Element)를 저장할 수 있는 데이터 구조를 만드는 것이다.

  • push(el): 스택의 맨 위에 새 요소를 추가한다.

  • pop(): 스택의 맨 위에 요소를 제거하며, 제거된 요소를 반환한다.

  • peek(): 스택의 최상위 요소를 반환하지만, 스택은 수정되지 않는다.

  • isEmpty(): 스택의 크기가 0보다 큰 경우 false, 그렇지 않을 경우 true를 반환한다.

  • clear(): 스택의 모든 요소를 제거한다.

  • size(): 스택에 포함된 요소의 수를 반환한다.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

사실 위처럼 만들어도 스택의 구조이긴 하나 조금 아쉬운 점이 있다. 바로 배열로 작업하는 대부분의 메서드의 시간 복잡도가 O(n)이기 때문이다. 즉 찾고 있는 요소를 찾을 때까지 배열을 반복해야 하고, 최악의 시나리오에서는 배열의 모든 위치를 반복해야하기 때문이다.

또한 배열의 크기를 n이라고 했을때 배열에 많은 요소가 있을 수록 모든 배열을 반복하는데 시간이 오래걸리며, 배열은 정렬된 요소의 집합이기 때문에 요소를 순서대로 유지하려면 더 많은 메모리 공간이 필요하기 때문이다.

위와 같은 문제점을 해결하기 위해 배열이 아닌 객체 기반으로 스택을 다시 만들어 보자.

객체 기반의 Stack class

자바스크립트의 객체(object)를 이용한다면 위 방법과 동일하게 LIFO 원칙을 준수하면서, 순서대로 동일하게 유지하지만, 더 나은 구조를 만들 수 있다.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

배열 기반의 스택과 비교하여 O(1)의 시간 복잡도를 갖게 된다.

스택의 내부 요소를 숨기자.

내가 만든 스택의 경우 내부 요소들이 모두 노출되어 있다. items나 count 값에 누구든지 마음대로 접근할 수 있다.

const log = console.log;

const stack = new Stack();
stack.push(8);
stack.push(12);

log(Object.getOwnPropertyNames(stack)); // ['count', 'items']
log(Object.keys(stack)); // ['count', 'items']
log(stack.items); // {0: 8, 1: 12}

그리고 노출된 것뿐만 아니라 당연히 접근하여 값을 변경할 수도 있다.

stack.count = 1000;
log(stack.count); // 1000

이를 개선하기 위해 private 수정자를 이용해 보자. 이 속성을 사용하기 위해서는 속성이나 메서드 앞에 해쉬(#)를 붙여 주면 된다. 물론 타입스크립트의 private 키워드를 통해서도 비슷한 private 효과를 구현할 수 있지만, 다른점은 타입스크립트의 private 키워드를 통한 제어는 컴파일 시간 동안에만 유효하다는 것이다. 바벨을 통해 자바스크립트로 변환해 보면, 해당 코드는 이전과 동일하게 public된 것을 알 수 있다.

const log = console.log;

class Stack {
  #count = 0;
  #items = {};

  push(element) {
    this.#items[this.#count] = element;
    this.#count++;
  }

  pop() {
    if (this.isEmpty()) {
      return;
    }
    this.#count--;
    const result = this.#items[this.#count];
    delete this.#items[this.#count];
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return;
    }
    return this.#items[this.#count - 1];
  }

  isEmpty() {
    return this.#count === 0;
  }

  size() {
    return this.#count;
  }

  clear() {
    this.#count = 0;
    this.#items = {};
  }
}

const stack = new Stack();
stack.push(8);
stack.push(12);

log(Object.getOwnPropertyNames(stack)); // []
log(Object.keys(stack)); // []
log(stack.size()); // 2

// log(stack.#items); // Error: Uncaught SyntaxError: Private field '#count' must be declared in an enclosing class
// log(stack.#count); // Error: Uncaught SyntaxError: Private field '#count' must be declared in an enclosing class
// stack.#count = 1000; // Error: Uncaught SyntaxError: Private field '#count' must be declared in an enclosing class

스택을 이용하여 어떤 문제를 해결할 수 있을까?

"역추적"에 유용하게 사용될 수 있다. 브라우저 히스토리나 스택 오버 플로우 예외 등을 예로 들 수 있다. 이번에는 스택을 통해 십진수를 이진수로 변환해 보자.

참고

  • Math.ceil(): 올림

  • Math.floor(): 내림

  • Math.round(): 반올림

function decimalToBinary(decimal) {
  const stack = new Stack();
  let num = decimal;
  let remainder;
  let binaryString = '';

  while (num > 0) {
    remainder = Math.floor(num % 2);
    stack.push(remainder);
    num = Math.floor(num / 2);
  }

  while (!stack.isEmpty()) {
    binaryString += stack.pop().toString();
  }
  return binaryString;
}

log(decimalToBinary(5)); // 101
log(decimalToBinary(10)); // 1010
log(decimalToBinary(50)); // 110010
log(decimalToBinary(121)); // 1111001
Previous반복 프로토콜Next호이스팅

Last updated