순환 대기열
순환 큐는 FIFO(선입 선출) 원리에 따라 연산을 수행하고 마지막 위치를 다시 첫 번째 위치에 연결하여 원을 만드는 선형 데이터 구조입니다. "링 버퍼"라고도 합니다.
순환 대기열의 이점 중 하나는 대기열 앞의 공간을 사용할 수 있다는 것입니다. 일반 큐에서는 큐가 가득 차면 큐 앞에 공백이 있어도 다음 요소를 삽입할 수 없습니다. 그러나 순환 대기열을 사용하면 공간을 사용하여 새 값을 저장할 수 있습니다.
문제
다음 작업을 지원할 수 있는 JavaScript의 순환 대기열 구현을 설계해야 합니다.
-
MyCircularQueue(k) - 생성자, 큐의 크기를 k로 설정합니다.
-
Front() - 대기열에서 전면 항목을 가져옵니다. 대기열이 비어 있으면 -1을 반환합니다.
-
Rear() - 대기열에서 마지막 항목을 가져옵니다. 대기열이 비어 있으면 -1을 반환합니다.
-
enQueue(value) - 순환 대기열에 요소를 삽입합니다. 작업이 성공하면 true를 반환합니다.
-
deQueue() - 순환 대기열에서 요소를 삭제합니다. 작업이 성공하면 true를 반환합니다.
-
isEmpty() - 순환 대기열이 비어 있는지 여부를 확인합니다.
-
isFull() - 순환 큐가 가득 찼는지 여부를 확인합니다.
예시
다음은 코드입니다 -
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