Circular Queue는 선형 데이터 구조로, 그 동작은 FIFO(선입선출) 원칙을 기반으로 하며, 마지막 위치가 다시 첫 번째 위치로 연결되어 루프를 형성합니다. "링 버퍼"라고도 합니다.
순환 대기열의 장점 중 하나는 대기열 앞 공간을 활용할 수 있다는 것입니다. 일반 큐에서는 큐가 가득 차면 큐 앞에 공간이 있어도 다음 요소를 삽입할 수 없습니다. 그러나 순환 큐를 사용하면 공간을 사용하여 새 값을 저장할 수 있습니다.
다음 작업을 지원하려면 JavaScript에서 순환 대기열 구현을 설계해야 합니다.
MyCircularQueue(k) - 생성자, 대기열 크기를 k로 설정합니다.
Front() - 대기열에서 맨 앞 항목을 가져옵니다. 큐가 비어 있으면 -1이 반환됩니다.
Rear() - 대기열에서 마지막 항목을 가져옵니다. 큐가 비어 있으면 -1이 반환됩니다.
enQueue(value) - 순환 대기열에 요소를 삽입합니다. 작업이 성공하면 true를 반환합니다.
deQueue() - 순환 대기열에서 요소를 제거합니다. 작업이 성공하면 true를 반환합니다.
isEmpty() - 순환 대기열이 비어 있는지 확인합니다.
isFull() - 순환 대기열이 가득 찼는지 확인합니다.
코드는 다음과 같습니다 -
Demo
const CircularQueue = function(k) { this.size = k this.queue = [] this.start1 = 0 this.end1 = 0 this.start2 = 0 this.end2 = 0 } CircularQueue.prototype.enQueue = function(value) { if(this.isFull()) { return false } if(this.end2 <= this.size - 1) { this.queue[this.end2++] = value } else { this.queue[this.end1++] = value } return true } CircularQueue.prototype.deQueue = function() { if(this.isEmpty()) { return false } if(this.queue[this.start2] !== undefined) { this.queue[this.start2++] = undefined } else { this.queue[this.start1++] = undefined } return true } CircularQueue.prototype.Front = function() { if(this.isEmpty()) { return -1 } return this.queue[this.start2] === undefined ? this.queue[this.start1] : this.queue[this.start2] } CircularQueue.prototype.Rear = function() { if(this.isEmpty()) { return -1 } return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] : this.queue[this.end1 - 1] } CircularQueue.prototype.isEmpty = function() { if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) { return true } return false } CircularQueue.prototype.isFull = function() { if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) { return true } return false } const queue = new CircularQueue(2); console.log(queue.enQueue(1)); console.log(queue.enQueue(2)); console.log(queue.enQueue(3)); console.log(queue.Rear()); console.log(queue.isFull()); console.log(queue.deQueue()); console.log(queue.enQueue(3)); console.log(queue.Rear());
true true false 2 true true true 3
위 내용은 JavaScript에서 순환 큐 링 버퍼 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!