- 원형 큐, 기본 Queue의 단점을 보완한 자료구조, 배열의 양 끝이 서로 연결되어 있는 상태
특징
- 배열의 끝에 도달했을 때 다시 처음으로 돌아가서 빈 공간을 활용할 수 있다
- front와 rear의 위치가 순환하기에, Queue의 크기를 효과적으로 사용할 수 있다
- 일반 Queue는 데이터가 추가, 삭제되면 배열 앞쪽 데이터가 삭제되고, 뒤쪽 데이터가 추가되지만, 빈 공간을 활용할 수 없게 된다
- 원형 큐는 이 문제를 해결하기 위해 배열 끝과 처음을 연결해 메모리를 더 활용한단 뜻
장점과 단점
- 장점 : 메모리 공간을 효율적으로 사용하여, 공간 낭비를 줄일 수 있다
- 단점 : 구현이 복잡하며, 공간이 비었는지, 다 찼는지를 구분해야 한다
예시 코드
class CircularQueue {
constructor(size) {
this.elements = Array(size);
this.size = size;
this.front = 0;
this.rear = 0;
this.currentLength = 0;
}
isEmpty() {
return this.currentLength === 0;
}
enqueue(item) {
if (this.currentLength === this.size) throw new Error('Full!');
// 데이터를 rear에 넣고, rear는 다음 위치로 이동, 끝에 도달하면 0으로
this.elements[this.rear] = item;
this.rear = (this.rear + 1) % this.size;
this.currentLength++;
}
dequeue() {
if (this.isEmpty()) throw new Error('Empty!');
// front 위치의 데이터를 삭제, front를 다음 위치로 이동, 끝에 도달하면 0으로
const item = this.elements[this.front];
this.front = (this.front + 1) % this.size;
this.currentLength--;
return item;
}
peek() {
if (this.isEmpty()) return null;
return this.elements[this.front];
}
}
const queue = new CircularQueue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
console.log(queue.peek());
queue.dequeue();
console.log(queue.peek());