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

이 기사는 javascript에 대한 관련 지식을 제공합니다. 주로 JavaScript의 대기열 구현과 관련된 문제를 소개하고 대기열 데이터 구조와 해당 작업을 설명하며 JavaScript의 대기열 구현을 보여줍니다. .

관련 권장사항: javascript 튜토리얼

1. 큐 데이터 구조

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

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

2. 대기열 작업

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

• Enqueue 연산
  enqueue 연산은 큐의 끝에 항목을 삽입하는 작업으로, 삽입된 항목이 큐의 끝이 됩니다.

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

queue.enqueue(8);

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

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

queue.dequeue(); // => 7

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

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

queue.peek(); // => 7

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

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

queue.length; // => 4

• 큐 작업 시간 복잡성
  중요한 것은 모든 대기열 작업(Enqueue, Dequeue, View 및 Length)에 대해 이러한 모든 작업은 고정된 시간에 O(1)을 실행해야 합니다.

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

3. JavaScript에서 대기열 구현

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

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

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(), dequeue(), peek() 및 length()는 다음만 사용합니다:

属性访问（例如this.items[this.headIndex]），

或执行算术操作（例如this.headIndex++）

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

4. 요약

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

Queue에는 enqueue와 dequeue라는 2가지 주요 작업이 있습니다. 또한 대기열에는 보기 및 길이와 같은 보조 작업이 있을 수 있습니다.

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

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

위 내용은 JavaScript로 대기열을 구현하기 위한 그림과 텍스트가 포함된 자세한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!