자료구조 - 원형 큐(Circular Queue)

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. 1번 타자 입장: Rear가 1로 이동(Front: 0, Rear: 1)
  2. 2번 타자 입장: Rear가 2로 이동(Front: 0, Rear: 2)
  3. 3번 타자 입장: Rear가 3으로 이동(Front: 0, Rear: 3)
  4. 4번 타자 입장 (꽉 참)
     
     • 원형 큐니까 Rear가 3에서 0으로 다시 돌아옴. (Front: 0, Rear: 0)

 

컴퓨터의 입장에서는 큐가 꽉 찼는데도 불구하고 비어있다고 착각하여 데이터를 덮어쓰기 하거나 비어있는 데 데이터를 꺼내려는 오류가 발생할 수 있다.

 

해결책

• 그래서 개발자들끼리 약속을 정한 것이다. "야, 헷갈리니까 Rear가 Front 꼬리 바로 뒤까지 쫓아오면, 꽉찬걸로 치고 멈추자."

즉, 칸이 4개라면 데이터를 3개만 넣는다. -> 4번을 넣으려고 보니 Front가 0에 있네? -> Front 바로 뒤니까 꽉 찬 걸로 간주한다.

 

이렇게 구현을 하게 되면 상태가 명확하게 구분된다.

• 텅 빔: Front == Rear (완전히 겹침)
• 꽉 참: Rear + 1 == Front (Rear가 Front 바로 뒤에 있을 때)

 

데이터를 한 개 덜 저장하는 손해를 보더라도 꽉 찼는지 비었는지 즉시 계산하기 위해서는 한 칸을 일부러 비워두는 것이다.