큐 구조 기초

큐는 선입선출(FIFO) 구조를 가진 자료구조입니다. 배열을 이용하여 큐를 구현할 수 있으며, 기본 구현과 원형 큐(Circular Queue) 방식으로 나뉩니다.

기본 배열 큐(비최적화)

1. 필요 변수: front = -1, rear = -1, maxSize, int[] arr
2. 큐가 가득 찬 조건: rear == maxSize - 1, 큐가 빈 조건: rear == front
3. 삽입(enqueue): 큐가 가득 찼는지 확인 후, rear++로 인덱스 증가 후 데이터 저장. 삭제(dequeue): 큐가 비었는지 확인(throw new RuntimeException("Queue is empty")), front++로 인덱스 증가
4. 큐 길이는 maxSize, 순회 출력 시 maxSize까지 반복

원형 큐(Circular Queue) - 최적화 버전

1. 필요 변수: front = 0, rear = 0, maxSize, int[] arr
2. 큐가 가득 찬 조건: (rear + 1) % maxSize == front, 큐가 빈 조건: rear == front
3. 삽입: arr[rear] = n 후 rear = (rear + 1) % maxSize, 삭제: value = arr[front] 후 front = (front + 1) % maxSize, 빈 큐는 throw new RuntimeException("Queue is empty")
4. 유효 큐 길이: (rear + maxSize - front) % maxSize, 순회 출력 시 front부터 front + size()까지 반복(인덱스는 i % maxSize로 접근)

원형 큐 구현 예제

class CircularQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] data;

    public CircularQueue(int size) {
        maxSize = size;
        data = new int[maxSize];
        front = 0;
        rear = 0;
    }

    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        data[rear] = value;
        rear = (rear + 1) % maxSize;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int result = data[front];
        front = (front + 1) % maxSize;
        return result;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d] = %d%n", i % maxSize, data[i % maxSize]);
        }
    }

    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
}

메인 함수 예제

import java.util.Scanner;

public class CircularQueueDemo {
    public static void main(String[] args) {
        // 실제 저장 가능한 요소는 3개 (약속된 공간 1개 제외)
        CircularQueue queue = new CircularQueue(4);
        Scanner scanner = new Scanner(System.in);
        boolean running = true;

        while (running) {
            System.out.println("\n1. Show Queue");
            System.out.println("2. Enqueue");
            System.out.println("3. Dequeue");
            System.out.println("4. Exit");
            System.out.print("Enter option: ");
            String input = scanner.next();

            switch (input) {
                case "1":
                    queue.display();
                    break;
                case "2":
                    System.out.print("Enter value: ");
                    int val = scanner.nextInt();
                    queue.enqueue(val);
                    break;
                case "3":
                    try {
                        int dequeued = queue.dequeue();
                        System.out.println("Dequeued: " + dequeued);
                    } catch (RuntimeException e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "4":
                    scanner.close();
                    running = false;
                    System.out.println("Exiting...");
                    break;
                default:
                    System.out.println("Invalid option");
            }
        }
    }
}

원형 큐는 rear + 1 % maxSize == front 로 가득 찬 상태를 판단하며, 빈 공간 하나를 예약하여 rear가 front를 추월하지 못하도록 합니다. 유효 길이 계산은 (rear + maxSize - front) % maxSize 공식을 사용합니다.