Circular Queue (Circular Buffer)#
이는 선형 큐의 확장된 버전으로, 데이터를 효율적으로 저장하고 관리하는 특정한 방식을 제공한다.
Circular Queue는 마지막 요소가 첫 번째 요소와 연결되어 원형 구조를 형성하는 큐 데이터 구조이다.
이는 ‘Ring Buffer’라고도 불리며, 고정 크기의 배열을 사용하여 데이터를 연속적인 루프로 저장한다.
https://www.geeksforgeeks.org/what-is-circular-queue-circular-queue-meaning/
- 원형 구조: 마지막 위치가 첫 번째 위치와 연결되어 있다.
- FIFO (First In First Out) 원칙을 따른다.
- 두 개의 포인터: 큐의 front와 rear를 추적하는 두 개의 포인터를 사용한다.
- 고정 크기: 초기화 시 크기가 설정되며, 이후 변경이 어렵다.
- 메모리 효율성: 선형 큐의 주요 한계인 메모리 낭비 문제를 해결한다.
- 빠른 연산: 삽입과 삭제 연산의 시간 복잡도가 O(1)이다.
- 공간 재사용: 큐의 앞부분이 비어있을 때 재사용이 가능하다.
- 캐시 지역성: 연속된 메모리 사용으로 CPU 캐시 성능이 향상된다.
- 크기 제한: 고정 크기로 인해 오버플로우와 데이터 손실 가능성이 있다.
- 구현 복잡성: 선형 큐보다 구현이 복잡하다.
- 디버깅 어려움: 원형 구조로 인해 디버깅이 어려울 수 있다.
- 동적 크기 조정의 어려움: 크기를 동적으로 조정하기 어렵다.
- CPU 스케줄링: 운영 체제에서 프로세스 관리에 사용된다.
- 트래픽 관리 시스템: 교차로에서의 효율적인 흐름 제어에 활용된다.
- 메모리 관리: 운영 체제의 메모리 관리에 사용된다.
- 스트리밍 서비스: 오디오 및 비디오 스트리밍에 활용된다.
- 네트워크 패킷 관리: 라우터와 스위치에서 패킷 데이터 처리에 사용된다.
동작 원리#
- 초기화: front와 rear 포인터를 -1로 설정한다.
- 삽입(Enqueue):
- 큐가 가득 찼는지 확인한다.
- rear 포인터를 원형으로 증가시킨 ((rear + 1) % size).
- 새 요소를 rear 위치에 삽입한다[11].
- 삭제(Dequeue):
- 큐가 비어있는지 확인한다.
- front 위치의 요소를 반환한다.
- front 포인터를 원형으로 증가시킨다 ((front + 1) % size).
구성 요소#
- 배열: 데이터를 저장하는 고정 크기의 배열.
- front 포인터: 큐의 첫 번째 요소를 가리킨다.
- rear 포인터: 큐의 마지막 요소를 가리킨다.
- size: 큐의 최대 크기를 나타낸다.
구현 방식#
JavaScript를 사용한 Circular Queue 구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class CircularQueue {
constructor(size) {
this.size = size;
this.queue = new Array(size);
this.front = -1;
this.rear = -1;
}
enqueue(element) {
if (this.isFull()) {
console.log("Queue is full");
return;
}
if (this.isEmpty()) {
this.front = 0;
}
this.rear = (this.rear + 1) % this.size;
this.queue[this.rear] = element;
}
dequeue() {
if (this.isEmpty()) {
console.log("Queue is empty");
return null;
}
const element = this.queue[this.front];
if (this.front === this.rear) {
this.front = -1;
this.rear = -1;
} else {
this.front = (this.front + 1) % this.size;
}
return element;
}
isEmpty() {
return this.front === -1 && this.rear === -1;
}
isFull() {
return (this.rear + 1) % this.size === this.front;
}
display() {
if (this.isEmpty()) {
console.log("Queue is empty");
return;
}
let i = this.front;
do {
console.log(this.queue[i]);
i = (i + 1) % this.size;
} while (i !== (this.rear + 1) % this.size);
}
}
// 사용 예시
const cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.display(); // 출력: 1, 2, 3
console.log(cq.dequeue()); // 출력: 1
cq.enqueue(4);
cq.display(); // 출력: 2, 3, 4
|
이 구현은 Circular Queue의 기본 동작을 보여준다.
enqueue와 dequeue 연산은 O(1)의 시간 복잡도를 가지며, 원형 구조를 통해 메모리를 효율적으로 사용한다.
참고 및 출처#