Javascript에서 우선 순위 큐를 구현하는 가장 좋은 방법

요약: 학습 우선순위 대기열은 예를 들어 Dijkstra의 최단 경로 알고리즘이 우선순위 대기열을 사용하는 것과 같이 많은 알고리즘에서 사용되기 때문에 중요합니다.

Introduction

Prerequisites

Implementation

Uses cases

소개

우선순위 큐는 선입선출(First In First Out)을 의미하는 FIFO 원칙을 따르는 데이터 구조이지만 일반적인 큐와는 접근 방식이 다릅니다. 그러나 그것들은 어떻게 다릅니까 우선 순위 큐는 우선 순위를 사용합니다. 즉, 우선 순위가 가장 높은 요소가 가장 먼저 삽입되고 마지막으로 삽입된 경우에도 gif가 잘 설명할 것입니다.



전제 조건

javascript를 알고 js에서 대기열을 구현하는 방법을 알고 있습니다.

구현

어떤 우선 순위 큐에 대한 견고한 기초가 있는지 코딩할 시간입니다. 이제 전체 코드를 본 다음 이를 이해하기 위해 조각으로 나눌 것입니다.



이해할 시간입니다.

class Elements {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

우리는 생성자를 만든 후에 클래스를 만들고 이름을 요소로 지정했지만 왜 이렇게 하는 걸까요? 이유는 간단합니다. 우리가 만든 클래스는 요소의 저장소이고 우선 순위는 우리가 잘 볼 수 있기 때문입니다.

class PriorityQueue {
  constructor() {
    this.collection = [];
  }

이제 우리는 PriorityQueue라는 클래스를 생성하고 생성자에서 생성한 것과 생성자에서 collection이라는 이름의 배열을 생성한 것에 대해 이야기하기 시작했습니다.

 enqueue(element, priority) {
    const queue = new Elements(element, priority);

    let contain = false;

    for (let i = 0; i < this.collection.length; i++) {
      if (this.collection[i].priority < queue.priority) {
        this.collection.splice(i, 0, queue);
        contain = true;

        break;
      }
    }

    if (!contain) {
      this.collection.push(queue);
    }
  }

많은 일들이 먼저 진행되기 때문에 주의를 기울이시기 바랍니다.

 enqueue(element, priority) {
    const queue = new Elements(element, priority);

    let contain = false;

enqueue 메서드는 일반 대기열에서와 동일합니다. 이제 요소 클래스를 초기화하고 대기열 변수에 저장했으며 포함 변수가 false인 경우 우리가 왜 그것을 사용하는지 볼 수 있습니다.

 for (let i = 0; i < this.collection.length; i++) {
      if (this.collection[i].priority < queue.priority) {
        this.collection.splice(i, 0, queue);
        contain = true;

        break;
      }
    }

우리는 for 루프를 생성한 다음 정상적인 작업을 수행하지만 대신 마법이 발생하는 곳이므로 if 문이 모든 우물을 살펴보는 것을 볼 수 있습니다. 컬렉션 우선 순위가 큐 변수가 우리가 생성한 변수를 기억하는 것보다 낮은지 확인하고 있습니다. 클래스 요소를 저장합니다. 스플라이스 방법이 이해가 되지 않는다면 영상을 참고하세요.



포함을 변경하고 true로 만든 후 루프를 중단합니다.

  if (!contain) {
      this.collection.push(queue);
    }

여전히 루프 외부의 enqueue 메서드에서 컬렉션을 푸시하는 경우 포함이 참인지 확인합니다. 계속.

 dequeue() {
    return this.collection.shift();
  }

  peek() {
    return this.collection[0];
  }
  rear() {
    return this.collection[this.collection.length - 1];
  }

  get isEmpty() {
    return this.collection.length === 0;
  }

  get print() {
    return console.log(this.collection);
  }

우리가 하는 일은 매우 간단합니다. 큐에서 빼는 것입니다. 그리고 배열의 첫 번째 요소를 제거하는 데 사용되는 shift 메서드를 사용하고 있습니다.
이 단계에서는 모든 것이 간단하고 이해할 수 있습니다.

const pQ = new PriorityQueue();

pQ.enqueue('john', 3);
pQ.enqueue('mike', 1);
pQ.enqueue('log', 2);

pQ.dequeue();

console.log('front of the array', pQ.peek());
console.log('last element', pQ.rear());
pQ.print;

결국 코드에서 모든 것이 단순하고 이해하고 소화하기 매우 쉽다고 생각합니다. 여기까지 했다면 당신은 다음 큰 일입니다. 문제가 있으면 집중하고 침착하세요. 기꺼이 도와드리겠습니다. 종료하기 전에 터미널을 살펴보겠습니다.



전체 코드

class Elements {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

class PriorityQueue {
  constructor() {
    this.collection = [];
  }

  enqueue(element, priority) {
    const queue = new Elements(element, priority);

    let contain = false;

    for (let i = 0; i < this.collection.length; i++) {
      if (this.collection[i].priority < queue.priority) {
        this.collection.splice(i, 0, queue);
        contain = true;

        break;
      }
    }

    if (!contain) {
      this.collection.push(queue);
    }
  }

  dequeue() {
    return this.collection.shift();
  }

  peek() {
    return this.collection[0];
  }
  rear() {
    return this.collection[this.collection.length - 1];
  }

  get isEmpty() {
    return this.collection.length === 0;
  }

  get print() {
    return console.log(this.collection);
  }
}

const pQ = new PriorityQueue();

pQ.enqueue('john', 3);
pQ.enqueue('mike', 2);
pQ.enqueue('log', 1);

pQ.dequeue();

console.log('front of the array', pQ.peek());
console.log('last element', pQ.rear());
pQ.print;