JavaScript에서 대기열 구조를 구현하는 방법에 대한 자세한 설명

이 기사에서는 대기열 데이터 구조를 이해하고 해당 작업과 JavaScript에서 대기열 구조를 구현하는 방법을 자세히 소개합니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

1. 큐 데이터 구조

큐는 FIFO(선입 선출) 데이터 구조 유형입니다. 대기열에 추가된 첫 번째 항목(입력)이 대기열에서 처음으로 제거된 항목(출력)입니다.

큐에는 머리와 꼬리라는 2개의 포인터가 있습니다. 대기열에서 가장 오래 대기 중인 항목이 맨 앞에 있고, 가장 최근에 대기열에 있는 항목이 맨 뒤에 있습니다.

줄은 우리가 지하철에서 줄을 서 있는 것과 같습니다. 문 근처에 있는 승객이 줄의 맨 앞에 있고, 줄에 막 들어간 승객이 줄의 맨 뒤에 있습니다.

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

2. 대기열 작업

대기열은 peek 및 길이 작업 외에도 enqueue(enqueue) 및 dequeue(dequeue)라는 두 가지 주요 작업을 지원합니다.

2.1 Enqueue 연산

enqueue 연산은 큐의 끝에 항목을 삽입하여 큐의 끝으로 만듭니다.

위 그림의 조인 연산은 대기열 끝에 8를 삽입하고, 그러면 8가 대기열의 끝이 됩니다. 8，之后 8 成为队列的队尾。

queue.enqueue(8);

2.2 出队操作

出队操作取出队列中第一个项目，此时队列中的下一个项目成为队首。

在上图中，出队操作返回项目7并从队列中删除。 出队之后之后，项目 2 成为新的队首。

queue.dequeue(); // => 7

2.3 Peek 操作

Peek 操作读取队首的项目，但是不改变队列。

上图中 7 是队首。 peek 操作只需返回队首 7 但是不修改队列。

queue.peek(); // => 7

2.4 length

length 操作返回队列中包含项目的数量。

上图中的队列有 4 项：4、6、2 和。7。结果队列长度为 4。

queue.length; // => 4

2.5 队列操作的时间复杂度

关于队列所有操作的重点：enqueue，dequeue，peek 和 length 必须以常数时间复杂度 O(1) 执行。

常数时间复杂度 O(1) 意味着无论队列大小如何（不管是有 10 个还是 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  将队列的项目通过数值索引保持。 队首项的索引由 Where.HeadInex 跟踪，队尾项由 this.tailIndex 跟踪。

队列方法的复杂度

在 Queue 的 queue()、 dequeue()、 peek() 和 length() 方法中存在：

• 属性访问器（如:this.items[this.headIndex]），
• 执行算数操作（如:this.headidex++）

这些方法的时间复杂度是恒定的时间 O(1)。

4. 总结

队列是一种遵循先入先出（FIFO）规则的的数据结构。

队列有 2 个主要操作：入队和出队。 另外，队列可以有辅助操作，例如 peek 和 length。

所有队列操作都必须以常数时间 O(1) 执行。

挑战一下：改进 dequeue() 和 peek()rrreee

Dequeue 연산은 큐의 첫 번째 항목을 꺼내는 작업입니다. 이때 큐의 다음 항목이 큐의 리더가 됩니다.

🎜큐 메소드의 복잡성🎜

• 속성 접근자(예: this.items[this.headIndex] code >),
• 산술 연산 수행(예: this.headidex++)

위 내용은 JavaScript에서 대기열 구조를 구현하는 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!