JavaScript로 대기열을 구현하기 위한 그림과 텍스트가 포함된 자세한 예

관련 권장사항: 자바스크립트 튜토리얼

1. 큐 데이터 구조

• 큐는 FIFO(선입선출) 데이터 구조 유형입니다. 대기열에 추가된 첫 번째 항목(입력)이 대기열에서 처음으로 제거된 항목(출력)입니다.
• 큐에는 헤드와 테일이라는 2개의 포인터가 있습니다. 대기열에서 가장 오래 대기 중인 항목이 맨 앞에 있고, 가장 최근에 대기열에 있는 항목이 맨 뒤에 있습니다.
• 줄은 지하철에서 줄을 서서 기다리는 것과 같습니다. 문 근처에 있는 승객이 줄의 맨 앞에 있고, 줄에 막 들어간 승객이 줄의 맨 뒤에 있습니다.

높은 수준의 관점에서 보면 큐는 데이터베이스에 저장된 순서대로 각 데이터 항목을 처리할 수 있게 해주는 데이터 구조입니다.

2. 대기열 작업

대기열은 대기열에 넣기와 대기열에서 빼기라는 두 가지 주요 작업을 지원합니다. 또한 대기열에서 미리보기 및 길이 작업을 수행하는 것이 유용할 수도 있습니다.

• Enqueue 작업 <br/>Enqueue 작업은 대기열 끝에 항목을 삽입하는 것이며, 삽입된 항목은 대기열의 끝이 됩니다.

위 그림의 enqueue 작업은 항목 8을 끝에 삽입하고 8이 대기열의 끝이 됩니다.

queue.enqueue(8);

• Dequeue 작업 <br/> Dequeue 작업은 대기열의 시작 부분에서 항목을 추출하는 것이며 대기열의 다음 항목이 선두 항목이 됩니다.

위 그림에서 대기열 제거 작업은 대기열에서 항목 7을 반환하고 제거합니다. 대기열에서 제거한 후 항목 2가 새 헤드 항목이 됩니다.

queue.dequeue(); // => 7

• 검사 작업 <br/> 검사 작업은 대기열을 변경하지 않고 대기열의 시작 부분을 읽습니다.

항목 7은 위 그림에서 대기열의 시작 부분이며 검사 작업에서는 대기열을 수정하지 않고 헤더(항목) 7만 반환합니다.

queue.peek(); // => 7

• 대기열 길이 길이 연산은 대기열에 포함된 항목 수를 계산합니다.

그림의 대기열에는 4개, 6, 2, 7개의 항목이 있습니다. 결과적으로 대기열 길이는 4입니다.

queue.length; // => 4

• 대기열 작업 시간 복잡도 모든 대기열 작업(enqueue, dequeue, view 및 length)에서 중요한 점은 이러한 모든 작업이 고정된 시간 O(1)에 실행되어야 한다는 것입니다.

상수 시간 O(1)은 대기열 크기(1천만 또는 100만 개 항목 포함 가능)에 관계없이 대기열 추가, 대기열 제거, 픽 및 길이 작업이 모두 동시에 수행되어야 함을 의미합니다.

3. JavaScript에서 대기열 구현

모든 작업이 일정한 시간 O(1)에서 수행되어야 한다는 요구 사항을 유지하면서 대기열 데이터 구조의 가능한 구현을 살펴보겠습니다.

클래스 대기열 {
  생성자() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  대기열에 넣기(항목) {
    this.items[this.tailIndex] = 항목;
    this.tailIndex++;
  }

  큐에서 빼기() {
    const item = this.items[this.headIndex];
    this.items[this.headIndex]를 삭제하세요.
    this.headIndex++;
    반품 상품;
  }

  엿보기() {
    return this.items[this.headIndex];
  }

  길이를 얻습니다() {
    this.tailIndex 반환 - this.headIndex;
  }
}

const 대기열 = 새로운 대기열();

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek(); // => 2

queue.length; // => 3

const queue = new Queue()는 큐의 인스턴스를 생성하는 방법입니다.

queue.enqueue(7) 메서드를 호출하여 항목 7을 대기열에 넣습니다.

queue.dequeue()는 대기열에서 헤드 항목을 제거하는 반면, queue.peek()는 처음부터 엿보기만 합니다.

마지막으로 queue.length는 대기열에 남아 있는 항목 수를 보여줍니다.

구현 관련: Queue 클래스 내부의 일반 객체 this.items는 숫자 인덱스로 대기열의 항목을 보유합니다. 헤드 항목의 인덱스는 this.headIndex에 의해 추적되고, 테일 항목의 인덱스는 this.tailIndex에 의해 추적됩니다.

• 대기열 메소드의 복잡성

Queue 클래스의 메소드 queue(), dequeue(), peek() 및 length()는 다음만을 사용합니다:

속성 액세스(예: this.items[this.headIndex]),

또는 산술 연산(예: this.headIndex++)을 수행합니다.

따라서 이러한 메서드의 시간 복잡도는 상수 시간 O(1)입니다.

4. 요약

대기열 데이터 구조는 "선입선출(FIFO)" 유형입니다. 대기열에 추가되는 가장 빠른 항목이 대기열에서 제거되는 가장 빠른 항목입니다.

대기열에는 대기열에 넣기와 대기열에서 빼기라는 두 가지 주요 작업이 있습니다. 또한 대기열에는 보기 및 길이와 같은 보조 작업이 있을 수 있습니다.

모든 대기열 작업은 일정한 시간에 O(1)을 수행해야 합니다.

관련 권장사항: JavaScript 학습 튜토리얼

위는 예제와 그림을 통해 JavaScript로 큐를 구현하는 방법에 대한 자세한 설명입니다. 자세한 내용은 PHP 중국어 웹사이트의 다른 관련 기사를 참조하세요.