원형 큐(Circular Queue)의 개념 및 구현
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 구조
대상자
- 초보 프로그래머 및 자료구조 학습자
- 큐 알고리즘의 효율성과 구현 방식에 관심 있는 개발자
- 난이도: 중급 (알고리즘 구현 및 배열 관리 이해 필요)
핵심 요약
- 원형 큐는 배열 기반으로 구현되어 공간 효율성을 높인 자료구조
FRONT
와REAR
포인터를 사용해 순환 증가(Circular Increment)를 수행REAR + 1 == FRONT
조건으로 가득 상태를 판단 (모듈로 연산 활용)
섹션별 세부 요약
1. 원형 큐의 필요성
- 일반 큐의 문제점: 삽입/삭제 후 앞부분에 여유 공간이 발생
- 공간 낭비 예시:
index 0
과1
이 사용 불가능한 상태 유지 - 해결 방안: 순환 구조로 잔여 공간 활용
2. 원형 큐의 동작 원리
- 포인터 관리:
FRONT
: 첫 번째 요소 위치REAR
: 마지막 요소 위치- 초기화:
FRONT = REAR = -1
- 모듈로 연산:
REAR = (REAR + 1) % size
- 가득 상태 조건:
FRONT == 0 && REAR == size - 1
REAR + 1 == FRONT
3. JavaScript 구현 예시
- 클래스 정의:
```javascript
class CircularQueue {
constructor(size) { ... }
```
- 핵심 메서드:
enqueue(element)
: 공간 여유 시 요소 삽입dequeue()
:FRONT
요소 제거 및 포인터 이동isFull()
/isEmpty()
: 상태 검사 (모듈로 연산 활용)- 시간 복잡도:
O(1)
(배열 기반 구현)
4. 실제 활용 사례
- CPU 스케줄링: 프로세스 큐 관리
- 메모리 관리: 가용 메모리 블록 할당
- 교통 관리: 신호등 제어 시스템
결론
- 원형 큐는 공간 낭비를 줄이고 높은 효율성 제공
- 모듈로 연산과
FRONT/REAR
포인터 관리가 핵심 - 실무 적용 시:
REAR + 1 == FRONT
조건에 주의하여 가득 상태를 정확히 판단