큐 데이터 구조에 대한 자세한 설명, js에서 구현하는 방법은 무엇입니까?
- 青灯夜游앞으로
- 2021-04-29 09:52:582056검색
훌륭한 프로그래머가 되려면 폭넓은 지식이 필요합니다. 첫 번째는 선택한 프로그래밍 언어를 이해하는 것입니다. 이 글을 읽고 있다면 아마도 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; // => 3const 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)rrreee
🎜🎜at 위 그림에서 대기열 제거 작업은 7 항목을 반환하고 대기열에서 제거합니다. 대기열에서 제거된 후 항목 2가 새 팀 리더가 됩니다. 🎜rrreee🎜🎜2.3 Peek 작업 🎜🎜🎜Peek 작업은 대기열의 선두에 있는 항목을 읽지만 대기열을 변경하지는 않습니다. 🎜🎜🎜🎜위로 사진 속 7은 팀의 리더입니다. peek 작업은 단순히 7 대기열의 헤드를 반환하지만 대기열을 수정하지는 않습니다. 🎜rrreee🎜🎜2.4 length🎜🎜🎜 길이 연산은 대기열에 포함된 항목 수를 반환합니다. 🎜🎜🎜🎜위로 그림의 대기열에는 4, 6, 2 및 의 4개 항목이 있습니다. 7. 결과 대기열 길이는 4입니다. 🎜rrreee🎜🎜2.5 대기열 작업의 시간 복잡도 🎜🎜🎜 대기열의 모든 작업에 대한 중요한 사항: enqueue, dequeue, peek 및 length는 일정한 시간 복잡도 O(1)로 실행되어야 합니다. 🎜🎜일정한 시간 복잡도 O(1)는 이러한 작업이 대기열 크기(항목이 1천만 개 또는 100만 개인지 여부)에 관계없이 상대적으로 일관된 시간에 수행되어야 함을 의미합니다. 🎜🎜🎜3. JavaScript를 사용하여 대기열 구현 🎜🎜🎜 모든 작업이 일정한 시간 복잡도 O(1)로 수행되도록 하면서 대기열 데이터 구조를 구현하는 방법을 살펴보겠습니다. 🎜rrreee🎜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] code >), - 산술 연산 수행(예:
this.headidex++)
아(1). 🎜4. 요약
큐는 FIFO(선입선출) 규칙을 따르는 데이터 구조입니다.
Queue에는 enqueue와 dequeue라는 2가지 주요 작업이 있습니다. 또한 대기열에는 엿보기 및 길이와 같은 보조 작업이 있을 수 있습니다.
모든 대기열 작업은 일정한 시간 O(1)으로 수행되어야 합니다. O(1) 执行。
挑战一下：改进 dequeue() 和 peek()
dequeue() 및 peek() 메서드를 개선하세요. 프로그래밍 비디오🎜를 방문하세요! ! 🎜위 내용은 큐 데이터 구조에 대한 자세한 설명, js에서 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!