[자료구조] Deque with JS

최적화는 생각나지 않고, 문제를 풀며 덱을 구현해 본 코드입니다.

 

최적화는 더 조사해 보고 다른 글로 올리겠습니다.

 

Deque 구현 아이디어

• 앞, 뒤로 모두 추가 제거 및 조회 가능
• Queue의 구현에서 앞에서 추가, 뒤에서 제거 두 가지 추가 구현하면 될까?
• front와 rear는 각각 현재 요소의 위치를 가리킨다. 만약 두 값이 같은데 실질적인 요소가 없는 경우 비었다고 판단
  → 이 경우로 인해서 size(), pop(), popFront()의 조건문이 추가됨(여기가 의문이 든다)
• print()를 통해 디버깅

class Deque {
  #deque = {};
  #front = 0;
  #rear = 0;

  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;
  }
  push(x) {
    if (this.isEmpty()) {
      this.#deque[this.#front] = x;
    } else {
      this.#deque[--this.#front] = x;
    }
  }
  pushBack(x) {
    if (this.isEmpty()) {
      this.#deque[this.#rear] = x;
    } else {
      this.#deque[++this.#rear] = x;
    }
  }
  pop() {
    if (this.isEmpty()) return null;
    else if (this.#front === this.#rear) {
      const data = this.#deque[this.#rear];
      delete this.#deque[this.#rear];

      return data;
    }
    const data = this.#deque[this.#rear];

    delete this.#deque[this.#rear--];

    return data;
  }
  popFront() {
    if (this.isEmpty()) return null;
    else if (this.#front === this.#rear) {
      const data = this.#deque[this.#front];
      delete this.#deque[this.#front];

      return data;
    }
    const data = this.#deque[this.#front];

    delete this.#deque[this.#front++];

    return data;
  }
  peek() {
    if (this.isEmpty()) return null;

    return this.#deque[this.#front];
  }
  peekBack() {
    if (this.isEmpty()) return null;

    return this.#deque[this.#rear];
  }
  print() {
    const list = [];
    for (let i = this.#front; i <= this.#rear; i++) {
      list.push(this.#deque[i]);
    }
    return this.isEmpty() ? "empty" : list.join(" ");
  }
}

▲Deque 구현 코드

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

deque.push(1); deque.print() // 1
deque.push(2); deque.print() // 2 1
deque.pushBack(3); deque.print() // 2 1 3
deque.peek(); // 2
deque.peekBack(); // 3
deque.pop(); deque.print() // 2 1
deque.popFront(); deque.print() // 1