Deque의 구현 및 쓰임 (javascript)

class로 생성시

생성자로는

1. 배열 / 양방향 연결 노드

2. head

3. tail

메소드로는

add front / back : 앞이나 뒤에 추가

pop front / back : 앞이나 뒤 제거 + 값 반환

peek front / back : 제거하지않고 반환

isEmpty : 비어있는지 확인

size

toString

간단 자바스크립트 코드

class Deque {
  constructor() {
    this.items = [];
    this.head = 0; // 데크의 앞쪽
    this.tail = 0; // 데크의 뒤쪽
  }

  addFront(element) {
    if (this.isEmpty()) {
      this.items[this.head] = element;
    } else if (this.head > 0) {
      this.items[--this.head] = element;
    } else {
      this.items.unshift(element);
    }
  }

  addRear(element) {
    this.items[this.tail++] = element;
  }

  removeFront() {
    if (this.isEmpty()) {
      return "Deque is empty";
    }
    const removedElement = this.items[this.head++];
    if (this.head === this.tail) {
      this.head = 0;
      this.tail = 0;
    }
    return removedElement;
  }

  removeRear() {
    if (this.isEmpty()) {
      return "Deque is empty";
    }
    const removedElement = this.items[--this.tail];
    if (this.head === this.tail) {
      this.head = 0;
      this.tail = 0;
    }
    return removedElement;
  }

  peekFront() {
    if (this.isEmpty()) {
      return "Deque is empty";
    }
    return this.items[this.head];
  }

  peekRear() {
    if (this.isEmpty()) {
      return "Deque is empty";
    }
    return this.items[this.tail - 1];
  }

  isEmpty() {
    return this.head === this.tail;
  }

  size() {
    return this.tail - this.head;
  }

  toString() {
    return this.items.slice(this.head, this.tail).toString();
  }
}

// 데크의 사용 예시
const deque = new Deque();
deque.addFront(1);
deque.addRear(2);
deque.addFront(3);

console.log(deque.toString()); // [3, 1, 2]
console.log(deque.peekFront()); // 3
console.log(deque.peekRear()); // 2

deque.removeFront();
console.log(deque.toString()); // [1, 2]

deque.removeRear();
console.log(deque.toString()); // [1]

데크(Deque, Double-ended Queue)는 양쪽 끝에서의 삽입과 삭제가 가능한 자료구조로, 다양한 응용 분야에서 유용하게 활용됩니다. 여기서는 데크가 주로 어디에서 사용되는지 다섯 가지 구체적인 예시를 알려드리겠습니다:

슬라이딩 윈도우 구현:

데크는 슬라이딩 윈도우(Sliding Window) 문제에서 유용하게 활용됩니다. 고정된 크기의 윈도우가 데이터 스트림을 따라 이동하면서 최소, 최대 또는 특정 연산을 수행할 때 사용됩니다.

LRU(Least Recently Used) 캐시 구현:

캐시에서 가장 최근에 사용되지 않은 항목을 삭제하고, 가장 최근에 사용된 항목을 추가하는 LRU 캐시 알고리즘에서 데크가 사용될 수 있습니다. 최근에 사용된 항목을 앞이나 뒤에 추가하거나, 가장 오래된 항목을 제거할 때 데크가 효과적입니다.

문자열에서 팰린드롬 검사:

데크는 문자열에서 팰린드롬 여부를 검사하는 데에도 사용됩니다. 문자열을 양쪽에서 하나씩 비교하며 팰린드롬 여부를 판단할 때 효과적입니다.

이중연결리스트의 대체:

데크는 양쪽에서의 삽입과 삭제가 가능하므로, 이중연결리스트의 역할을 대체할 수 있습니다. 특히, 양쪽 끝에서의 삽입과 삭제가 빈번한 경우에 유용합니다.

최솟값/최댓값 큐:

데크를 사용하여 양쪽에서 원소를 추가하거나 삭제할 때, 최솟값 또는 최댓값을 유지하는 큐를 구현할 수 있습니다. 이는 삽입과 삭제가 O(1)에 이루어질 수 있는 특성을 활용한 것입니다.

출처 : chat gpt

참고 : https://velog.io/@kimhyo_0218/JavaScript-%EB%8D%B1Deque-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0