[자료구조] Deque with JS 리팩토링

[자료구조] Deque 구현

 

기존에 구현했던 Deque을 좀 더 최적화해 보겠습니다.

 

문제 1. isEmpty()에서 !this.#deque[this.#front] 조건이 JS에서 falsy일 때

size 변수를 추가해 isEmpty()나 size()를 단순화

 

문제 2. 메서드명 일관성 pushBack(), popFront()

pushFront(), pushBack(), popFront(), popBack(), peekFront(), peekBack()으로 통일

 

애매한 문제 3. 전위, 후위 연산자는 명시적인가?

명시적이지 못하다는 평이 있습니다만 개발자라면 다들 자주 사용한다고 생각하기에 넘어갑니다.

 

문제 4. 메모리 누수

해당 부분을 수정하기 위해선 #deque의 크기를 고정하고 사용하면 됩니다. 원형 큐를 만들 때 사용했던 방식과 비슷한 방식입니다.

+알파

배열을 사용해 크기를 고정했을 때 제공되는 크기가 부족하면 늘려야 하는 경우가 생기는데 이때 기존 덱의 요소들을 복사할 일이 있습니다. 이때 const newDeque = this.#deque.concat(new Array(this.#capacity));로 하면 안 되는가?

 

위 방식으로 크기를 늘릴 경우 덱의 요소들의 위치가 변경될 수 있기 때문에 안된다.

[a,b,c,d,,,,] → [a,b,c,d,,,,,,,,,,,,] (o)

[c,d,,,,,a,b] → [c,d,,,,,a,b,,,,,,,,] (x) ... 안 되는 경우가 생김

for문을 사용해서 복사하는 것이 안전하다.

class Deque {
  #deque = {};
  #head = 0;
  #tail = -1; // tail을 -1로부터 시작해 찝찝했던 계산 해결
  #size = 0; // 덱의 크기를 변수로 따로 작성

  isEmpty() { return this.#size === 0; }
  get size() { return this.#size; }
  pushFront(x) {
    this.#deque[--this.#head] = x;
    this.#size++;
  }
  pushBack(x) {
    this.#deque[++this.#tail] = x;
    this.#size++;
  }
  popFront() {
    if (this.isEmpty()) return null;
    const data = this.#deque[this.#head];

    delete this.#deque[this.#head++];
    this.#size--;

    return data;
  }
  popBack() {
    if (this.isEmpty()) return null;
    const data = this.#deque[this.#tail];

    delete this.#deque[this.#tail--];
    this.#size--;

    return data;
  }
  peekFront() { return this.isEmpty() ? null : this.#deque[this.#head]; }
  peekBack() { return this.isEmpty() ? null : this.#deque[this.#tail]; }
  print() {
    const list = [];
    for (let i = this.#head; i <= this.#rear; i++) {
      list.push(this.#deque[i]);
    }
    console.log(this.isEmpty() ? "empty" : list.join(" "));
  }
}

▲Deque 구현 코드

// 테스트 코드
const deque = new Deque();

deque.pushFront(1); deque.print() // 1
deque.pushFront(2); deque.print() // 2 1
deque.pushBack(3); deque.print() // 2 1 3
deque.peekFront(); // 2
deque.peekBack(); // 3
deque.popBack(); deque.print() // 2 1
deque.popFront(); deque.print() // 1

 

위에서 주석에 달린 찝찝한 계산이라는 것은 아래 기존 코드를 보면 isEmpty()와 size()를 구하는데 계산이 필요했던 것을 의미합니다.

isEmpty() {
  return this.#front === this.#rear && !this.#deque[this.#front];
}
size() {
  if (this.isEmpty()) return 0;
  else if (this.#front === this.#rear) return 1;
  return this.#rear - this.#front + 1;
}