원형 큐

1. 원형 큐란?

원형 큐(Circular Queue)는 일반적인 큐(Queue)의 한계를 극복한 자료구조로,
배열을 원형 형태로 연결하여 큐의 공간을 효율적으로 활용하는 방식이다.

✅ 일반적인 큐의 문제점

• 일반적인 선형 큐(Linear Queue)는 enqueue(삽입)과 dequeue(삭제)를 반복하면 배열의 앞쪽 공간이 비어도 재사용할 수 없음
• 즉, 배열의 크기를 초과하면 사용되지 않는 공간이 발생하여 비효율적임

✅ 원형 큐의 특징

• 선형 큐의 메모리 낭비 문제를 해결
• 배열의 끝과 시작이 연결된 형태
• 배열을 넘어가면 다시 처음으로 돌아갈 수 있음 (모듈러 연산 활용)

---

2. 원형 큐 vs 선형 큐 비교

비교 항목선형 큐 (Linear Queue)원형 큐 (Circular Queue)

메모리 활용

비효율적 (삭제 후 공간 재사용 불가)

효율적 (공간 재사용 가능)

구현 방식

배열 또는 연결 리스트

배열 기반 (끝과 처음 연결)

Front & Rear 이동

한 방향으로만 이동

원형으로 회전 가능

오버헤드

크기 초과 시 새로운 배열 할당 필요

배열 크기 내에서 회전하여 사용

💡 즉, 원형 큐는 선형 큐의 공간 낭비 문제를 해결한 구조다!

 

3. 원형 큐의 동작 방식

배열을 사용한 원형 큐의 주요 연산

• enqueue(x): 데이터 삽입 (Rear 이동)
• dequeue(): 데이터 삭제 (Front 이동)
• isEmpty(): 큐가 비었는지 확인
• isFull(): 큐가 가득 찼는지 확인

✅ 원형 큐의 핵심 로직

1. enqueue(x) 삽입
   • rear 위치에 데이터 추가
   • rear = (rear + 1) % 배열 크기 (모듈러 연산 활용)
2. dequeue() 삭제
   • front 위치의 데이터를 삭제
   • front = (front + 1) % 배열 크기 (모듈러 연산 활용)
3. 원형 큐에서 "가득 찼는지" 확인하는 조건
   • rear가 한 칸 이동하면 front와 같아질 경우, 큐가 가득 참 (Full 상태)

(rear + 1) % 배열 크기 == front

• rear가 한 칸 이동하면 front와 같아질 경우, 큐가 가득 참 (Full 상태)

🎯 원형 큐의 주요 기능

1. enqueue(int value) → 원형 큐에 데이터를 삽입 (O(1))
2. dequeue() → 원형 큐에서 데이터를 제거 (O(1))
3. isFull() → 큐가 가득 찼는지 확인
4. isEmpty() → 큐가 비었는지 확인
5. peek() → 현재 front 값을 조회
6. printQueue() → 큐의 현재 상태 출력

4. 원형 큐의 구현

 

✔ 원형 큐는 모듈러 연산(%)을 활용하여 배열의 끝에서 다시 앞으로 돌아갈 수 있도록 구현됨.
✔ 공간을 낭비하지 않고, 효율적으로 활용할 수 있음!

class CircularQueue {
    private int[] queue; // 원형 큐를 저장할 배열
    private int front;   // 첫 번째 요소 위치
    private int rear;    // 마지막 요소 위치
    private int size;    // 큐의 최대 크기
    private int count;   // 현재 요소 개수

    // 생성자: 원형 큐 초기화
    public CircularQueue(int size) {
        this.size = size;
        this.queue = new int[size];
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }

    // ✅ 원형 큐가 비어 있는지 확인
    public boolean isEmpty() {
        return count == 0;
    }

    // ✅ 원형 큐가 가득 찼는지 확인
    public boolean isFull() {
        return count == size;
    }

    // ✅ 원형 큐에 데이터 삽입 (enqueue)
    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        queue[rear] = value;
        rear = (rear + 1) % size; // 원형으로 이동
        count++;
    }

    // ✅ 원형 큐에서 데이터 제거 (dequeue)
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int removedValue = queue[front];
        queue[front] = -1; // 값 제거 (옵션)
        front = (front + 1) % size; // 원형으로 이동
        count--;
        return removedValue;
    }

    // ✅ 현재 front 값을 조회 (peek)
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[front];
    }

    // ✅ 큐의 현재 상태 출력
    public void printQueue() {
        System.out.print("Queue: ");
        for (int i = 0; i < size; i++) {
            System.out.print(queue[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);
        
        // 데이터 삽입
        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        cq.printQueue(); // 1 2 3 -1 -1
        
        // 데이터 제거
        System.out.println("Dequeued: " + cq.dequeue()); // 1 제거
        cq.printQueue(); // -1 2 3 -1 -1
        
        // 추가 삽입
        cq.enqueue(4);
        cq.enqueue(5);
        cq.enqueue(6);
        cq.printQueue(); // 6이 rear로 들어가며 원형 큐 동작 확인
    }
}

🔍 원형 큐의 핵심 로직

• rear = (rear + 1) % size; → 데이터를 추가할 때, rear가 배열 끝에 도달하면 다시 처음으로 이동
• front = (front + 1) % size; → 데이터를 제거할 때, front가 배열 끝에 도달하면 다시 처음으로 이동
• isFull() 조건: (rear + 1) % size == front
• isEmpty() 조건: count == 0

5. 원형 큐의 시간 복잡도

연산시간 복잡도

enqueue()	O(1)
dequeue()	O(1)
isEmpty() / isFull()	O(1)

💡 모든 연산이 O(1)로 빠르게 수행됨!
💡 선형 큐보다 효율적인 메모리 사용이 가능!

---

6. 원형 큐의 활용 예시

✅ 운영체제(Operating System)

• CPU 스케줄링 (Round Robin 방식)
• I/O 버퍼 관리

✅ 네트워크(Computer Networks)

• 패킷 큐(Buffer Overflow 방지)

✅ 데이터 스트림 처리

• 음악/영상 플레이어의 버퍼 관리

---

7. 정리 및 결론

✔ 원형 큐는 선형 큐의 공간 낭비 문제를 해결한 구조
✔ 모듈러 연산을 활용해 배열의 끝에서 다시 앞으로 연결
✔ 모든 연산이 O(1)로 빠르게 수행됨
✔ 운영체제, 네트워크, 데이터 스트림 처리 등 다양한 곳에서 활용됨

💡 즉, 원형 큐는 메모리를 효율적으로 활용하면서도 빠른 성능을 제공하는 자료구조! 🚀

---

🎯 발표 팁

• "선형 큐의 문제점"을 강조한 후, 원형 큐가 이를 어떻게 해결하는지 설명하기
• 실제 사용 사례(CPU 스케줄링, 네트워크 패킷 처리)와 연관지어 설명하면 이해하기 쉬움
• 모듈러 연산(%)이 핵심 개념이므로, 이를 강조하여 설명하면 좋음

🔥 실제 코드 예제와 시각적 자료(배열이 순환하는 GIF 등)를 활용하면 발표가 더욱 효과적일 것! 🚀