순환 큐(Circular Queue)란?
순환 큐는 FIFO(First In First Out, 선입선출) 원칙에 따라 연산이 수행되는 선형 자료구조입니다. 일반 큐와 달리 마지막 위치가 다시 첫 번째 위치와 연결되어 원형을 이루며, 이러한 특징 때문에 '링 버퍼(Ring Buffer)'라고도 부릅니다.
순환 큐의 가장 큰 장점은 큐 앞쪽의 빈 공간을 재활용할 수 있다는 점입니다. 일반적인 큐에서는 한 번 가득 차면 앞쪽에 빈 공간이 남아 있어도 더 이상 새로운 요소를 삽입할 수 없습니다. 하지만 순환 큐에서는 뒤쪽 끝이 앞쪽과 연결되어 있기 때문에, 앞쪽의 사용 가능한 공간에 새로운 값을 계속 저장할 수 있습니다.
문제 정의
이번 글에서는 JavaScript로 다음 연산들을 지원하는 순환 큐 클래스를 직접 설계하고 구현해 보겠습니다.
MyCircularQueue(k) — 생성자(Constructor). 큐의 크기를 k로 설정합니다.
Front() — 큐의 맨 앞에 있는 항목을 반환합니다. 큐가 비어 있으면 -1을 반환합니다.
Rear() — 큐의 마지막 항목을 반환합니다. 큐가 비어 있으면 -1을 반환합니다.
enQueue(value) — 순환 큐에 요소를 삽입합니다. 연산이 성공하면 true를 반환합니다.
deQueue() — 순환 큐에서 요소를 삭제합니다. 연산이 성공하면 true를 반환합니다.
isEmpty() — 순환 큐가 비어 있는지 여부를 확인합니다.
isFull() — 순환 큐가 가득 찼는지 여부를 확인합니다.
구현 아이디어
이 구현에서는 네 개의 포인터(start1, end1, start2, end2)를 활용해 배열의 앞부분과 뒷부분을 각각 추적합니다. enQueue는 뒤쪽 영역(end2)부터 채우고, 해당 영역이 가득 차면 배열 앞쪽(end1)으로 순환하여 데이터를 저장합니다. deQueue도 같은 방식으로 앞쪽(start2)부터 제거하고, 필요하면 start1 영역으로 이어서 처리합니다. 이렇게 하면 별도의 모듈로 연산 없이도 배열의 빈 공간을 효율적으로 재사용할 수 있습니다.
구현 예제
다음은 위에서 설명한 순환 큐를 JavaScript로 구현한 전체 코드입니다.
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
결과 해석
크기가 2인 큐에 1과 2를 삽입하면 각각 true가 반환되고, 이미 가득 찬 상태에서 세 번째 값 3을 삽입하려 하면 false가 반환됩니다. 이때 Rear()는 마지막으로 삽입된 2를 반환하며, isFull()은 true를 나타냅니다. 이후 deQueue()로 맨 앞의 1을 제거하면 true가 반환되고, 비워진 자리에 3을 다시 삽입할 수 있습니다. 마지막으로 Rear()를 호출하면 순환 구조 덕분에 새로 삽입된 3이 올바르게 조회되는 것을 확인할 수 있습니다.