패스트캠퍼스 JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 강의 3주차

ch.2 JavaScript 핵심 자료구조[우선순위 큐 (Priority Queue)]

우선순위 큐(Priority Queue) 자료구조란 ? 

먼저들어간 데이터가 먼저 나오는 큐와는 다르게, 우선순위큐는 힙(heap)을 이용한 우선순위를 통해 가장 우선순위가 높은 데이터가 먼저 나오게된다.

주로 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용된다.

 

 

---

우선순위 큐(Queue) 구현하는 방법 

우선순위 큐는  우선순위를 정의하고, 가장높은 우선순위의 데이터를 먼저 꺼내는 자료구조이다.

C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다.

그래서, JS환경에서 우선순위큐는 보통 힙(heap) 이라는 이진트리를 이용해서 구현한다.

힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다.

 

 

---

힙(heap)의 구현

힙이란?

• 힙(heap)은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조다.

• 최대 힙(max heap): 값이 큰 원소부터 추출한다.

• 최소 힙(min heap): 값이 작은 원소부터 추출한다. • 힙은 원소의 삽입과 삭제를 위해 𝑂 𝑙𝑜𝑔𝑁 의 수행 시간을 요구한다.

• 단순한 𝑁개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다.

• 이 경우 시간 복잡도는 𝑂 𝑁𝑙𝑜𝑔𝑁 이다.

 

// 큐 추상화 인터페이스
interface Queue {
  readonly size: number;
  enQueue(value: string): void;
  deQueue(): void;
  search(num: number): string;
}
 
// 추가될 노드 타입 생성
type QueueNode = {
  value: string;
  next?: QueueNode;
}
 
// 큐 클래스
class QueueImpl implements Queue {
  private _size: number = 0; // _size 값을 외부에서 접근하지 못하게 묶습니다.
  private head?: QueueNode; // head는 노드 인터페이스 타입
  private tail?: QueueNode; // tail도 노드 인터페이스 타입
 
  // 묶여있는 _size를 밖에서 호출해주기 위해 getter를 사용합니다.
  get size() {
    return this._size;
  }
 
  // 큐 추가
  enQueue(value: string) {
    const node: QueueNode = { value };
    if (this._size === 0) {
      this.head = node;
    } else {
      this.tail!.next = node;
    }
    this.tail = node;
    this._size++;
  }
 
  // 큐 제거
  deQueue() {
    if (!this.head) throw new Error('queue not exist..😑'); // 큐가 하나도 없는 상태면 에러 발생
    if (this.head.value === this.tail?.value) {
      this.tail = undefined;
    }
    const next = this.head.next;
    this.head = next;
    this._size--;
  }
 
  // 큐 검색 = index
  search(num: number): string {
    // 큐가 하나도 없거나 해당하는 큐가 없을 경우에 에러 발생
    if (!this.head) throw new Error('queue not exist..😑');
    if (num < 0 || num >= this._size) {
      throw new Error('No corresponding stacks found..😣');
    }
    let count: number = 0;
    let current: QueueNode = this.head;
    while (count < num) {
      current = current.next!;
      count++;
    }
    return current.value;
  }
}

const queue = new QueueImpl(); // 클래스 생성
console.log(queue); // 초기 데이터
 
// 데이터 추가
queue.enQueue('samsung');
console.log(queue);
queue.enQueue('apple');
console.log(queue);
queue.enQueue('google');
console.log(queue);
 
// index 확인
console.log(queue.search(0), queue.search(1), queue.search(2));
 
// 데이터 제거
queue.deQueue();
console.log(queue);
queue.deQueue();
console.log(queue);
queue.deQueue();
console.log(queue);

---

---

https://fastcampus.co.kr/dev_online_upjscodingtest

UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.