728x90
반응형
1. 무한 동력, 원형 큐(Circular Queue)
큐를 구현할 때 배열의 끝에 다다르면, 다시 처음으로 돌아가라 라는 규칙이 필요하다.
이때 등장하는 것이 바로 "나머지 연산자(Modulo, %)"다.
공식 : (인덱스 + 1) % 배열 크기
이 공식 하나면 인덱스가 0, 1, 2, 3, 4 -> 0, 1, 2 .. 식으로 빙글빙글 돈다.
나머지 연산자를 이용해서 배열 크기보다 작은 값의 포인터를 이용하여 1씩 늘어나는 반복적인 작업을 진행 할 수 있는 것이다.
package step03;
public class MyCircularQueue {
private int[] queue;
private int front;
private int rear;
private int maxBufferSize;
public MyCircularQueue(int size) {
this.maxBufferSize = size;
this.queue = new int[size];
this.front = 0;
this.rear = 0; // 원형 큐의 구현 편의상 0에서 시작하는 것이 일반적입니다.
}
// 1. 데이터 넣기 (Enqueue)
public boolean enqueue(int value) {
queue[rear] = value;
rear = (rear + 1) % maxBufferSize;
return true;
}
// 2. 데이터 꺼내기 (Dequeue)
public int dequeue() {
int value = queue[front];
front = (front + 1) % maxBufferSize;
return value; // 임시 반환값
}
// --- 테스트용 출력 메서드 ---
public void printStatus() {
System.out.printf("Front: %d, Rear: %d, 배열상태: ", front, rear);
for(int n : queue) System.out.print(n + " ");
System.out.println();
}
public static void main(String[] args) {
// 크기가 4인 큐 생성 (공간을 하나 비워두는 방식이라 실제 데이터는 3개까지 저장됨)
MyCircularQueue q = new MyCircularQueue(4);
System.out.println("--- 1. 데이터 채우기 ---");
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.printStatus(); // 10, 20, 30 잘 들어갔는지 확인
System.out.println("\n--- 2. 데이터 2개 꺼내기 (앞쪽 공간 비우기) ---");
System.out.println("꺼낸 값: " + q.dequeue());
System.out.println("꺼낸 값: " + q.dequeue());
q.printStatus();
System.out.println("\n--- 3. 원형 회전 테스트 (비어있는 앞쪽으로 다시 들어가나?) ---");
q.enqueue(40); // 여기서 선형 큐라면 에러가 났을 겁니다.
q.enqueue(50);
q.printStatus(); // Rear가 0번 인덱스로 돌아왔는지 확인하세요.
}
}
여기서 핵심은 공간을 하나 비워 두고 원형 큐를 구현하는 방식인 것이다.
2. 왜 하나를 비워두고 원형 큐를 구현할까?
- 꽉 채웠을 때의 상황
- 1번 타자 입장: Rear가 1로 이동(Front: 0, Rear: 1)
- 2번 타자 입장: Rear가 2로 이동(Front: 0, Rear: 2)
- 3번 타자 입장: Rear가 3으로 이동(Front: 0, Rear: 3)
- 4번 타자 입장 (꽉 참)
- 원형 큐니까 Rear가 3에서 0으로 다시 돌아옴. (Front: 0, Rear: 0)
컴퓨터의 입장에서는 큐가 꽉 찼는데도 불구하고 비어있다고 착각하여 데이터를 덮어쓰기 하거나 비어있는 데 데이터를 꺼내려는 오류가 발생할 수 있다.
해결책
- 그래서 개발자들끼리 약속을 정한 것이다. "야, 헷갈리니까 Rear가 Front 꼬리 바로 뒤까지 쫓아오면, 꽉찬걸로 치고 멈추자."
즉, 칸이 4개라면 데이터를 3개만 넣는다. -> 4번을 넣으려고 보니 Front가 0에 있네? -> Front 바로 뒤니까 꽉 찬 걸로 간주한다.
이렇게 구현을 하게 되면 상태가 명확하게 구분된다.
- 텅 빔: Front == Rear (완전히 겹침)
- 꽉 참: Rear + 1 == Front (Rear가 Front 바로 뒤에 있을 때)
데이터를 한 개 덜 저장하는 손해를 보더라도 꽉 찼는지 비었는지 즉시 계산하기 위해서는 한 칸을 일부러 비워두는 것이다.
728x90
반응형
'Coding Test' 카테고리의 다른 글
| 알고리즘 - 이분 탐색(Binary Search) (0) | 2026.02.03 |
|---|---|
| 코딩 테스트 명심해야할 사항 (0) | 2026.01.29 |
| 자료구조 - 큐(Queue) (0) | 2026.01.29 |
| 자료구조 - 스택(Stack) (0) | 2026.01.29 |
| 자료구조 - 배열(Array) vs 연결 리스트(Linked List) (0) | 2026.01.29 |