스택/큐

WooBuntu·2020년 8월 24일
0


- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

스택

  • 스택은 '후입선출'의 자료구조이다.

  • 스택의 예시

    • 콜스택(호출된 함수들의 자료 구조)

    • 실행취소(ctrl + z)

    • 브라우저의 history 객체

  • 스택의 경우 굳이 자료구조를 따로 만들지 않아도 자바스크립트의 내장 배열로도 충분히 구현이 된다.

  • push, pop조합과 unshift, shift조합으로 구현할 수 있는데, shift와 unshift가 인덱스의 재정렬 때문에 n의 시간 복잡도를 갖는 것을 고려하면, 전자의 조합을 사용하는 게 타당하다

단일 연결 리스트를 활용하여 스택 자료 구조 만들기

  • 자바스크립트 내장 배열로 스택을 구현할 때는 push와 pop을 활용하는 게 더 타당하다고 했지만, 지난 포스팅에서 살펴 봤듯이 단일 연결 리스트에서 pop은 n의 시간 복잡도를 갖는다.

  • 이중 연결 리스트를 활용하면 이 문제를 해결할 수 있지만, 알다시피 이중 연결 리스트는 메모리를 두 배로 사용한다는 단점이 있다.

  • 그렇기에 단일 연결 리스트의 shift와 unshift의 조합으로 스택을 구현하는 게 최선이라고 판단된다.

const Node = {
  init: function (val) {
    this.val = val;
    this.next = null;
  },
};

const Stack = {
  init: function () {
    this.first = null;
    this.last = null;
    this.size = 0;
  },
  push: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.last) {
      // last가 없다는 것은 push한 노드가 first이자 last이 되어야 한다는 것
      this.first = newNode;
      this.last = newNode;
    } else {
      newNode.next = this.last;
      this.last = newNode;
    }
    this.size++;
    return this;
  },
  pop: function () {
    if (!this.last) {
      // last가 없다는 것은 더 이상 pop할 노드가 없다는 것
      return;
    }

    const oldLast = this.last;
    if (this.size == 1) {
      this.first = null;
      this.last = null;
    } else {
      this.last = oldLast.next;
      oldLast.next = null;
    }
    this.size--;
    return oldLast;
  },
};

const stack = Object.create(Stack);
stack.init();
  • 다만, 주의할 것은 여기서 first와 last의 방향은 단일 연결 리스트의 head와 tail의 방향과는 반대라는 것이다.

  • last in first out(후입선출)의 개념에 혼동을 주지 않기 위해 이렇게 하는 게 맞다고 판단했다.

  • 큐는 '선입선출'의 자료구조이다.

  • 큐의 예시

    • 백그라운드 작업

    • 자료 업로딩

    • 프린트

  • 큐 역시 스택과 마찬가지로 자바스크립트 내장 배열로 구현할 수 있으며, shift와 push조합 또는 unshift와 pop조합을 사용하면 된다.

  • 다만, stack과는 달리 어느 조합을 사용하더라도 인덱스의 재정렬을 피할 수 없기 때문에 자료 구조를 직접 구현하는 편이 바람직하다.

단일 연결 리스트를 활용하여 큐 자료 구조 만들기

const Node = {
  init: function (val) {
    this.val = val;
    this.next = null;
  },
};

const Queue = {
  init: function () {
    this.first = null;
    this.last = null;
    this.size = 0;
  },
  enqueue: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.last) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.size++;
    return this;
  },
  dequeue: function () {
    if (!this.last) {
      return;
    }
    const oldFirst = this.first;
    if (this.size == 1) {
      this.first = null;
      this.last = null;
    } else {
      this.first = oldFirst.next;
      oldFirst.next = null;
    }
    this.size--;
    return oldFirst;
  },
};

const queue = Object.create(Queue);
queue.init();

  • 결국 스택과 큐는 삽입과 삭제를 상수 시간에 하기 위해 활용하는 자료 구조이다.

0개의 댓글