[java] 자바의 원형 큐(Circular Queue) 자료구조 이해하기

14 Dec 2023

java

이번에는 자바에서 사용되는 원형 큐(Circular Queue) 자료구조에 대해 알아보겠습니다. 원형 큐는 고정된 크기를 가지고 있는 선입선출(FIFO) 자료구조로, 배열을 이용하여 구현됩니다. 여기서는 원형 큐의 동작 방식과 자바에서의 구현 예제를 살펴보겠습니다.

원형 큐의 동작 방식

원형 큐는 선형 큐와 달리 Queue의 끝에 도달하면 시작 지점으로 다시 돌아가는 특징을 가지고 있습니다. 이를 통해 배열의 초기 공간을 활용할 수 있고, 메모리를 효율적으로 사용할 수 있습니다.

다음은 원형 큐의 주요 동작 방식입니다.

큐는 배열과 두 개의 포인터(Front, Rear)로 구성됩니다.
Front는 큐의 첫 번째 요소를 가리키고, Rear는 마지막 요소를 가리킵니다.
요소를 추가할 때, Rear를 한 칸 뒤로 이동한 뒤에 해당 위치에 요소를 추가합니다.
요소를 추출할 때, Front를 한 칸 뒤로 이동한 뒤에 해당 위치의 요소를 추출합니다.
큐의 양 끝이 배열의 경계에 다다를 때, 원형 큐는 배열의 처음과 끝이 연결되어 있는 것으로 간주합니다.

자바에서의 원형 큐 구현 예제

다음은 자바에서 원형 큐를 배열을 이용하여 구현한 예제 코드입니다.

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public void enqueue(int item) {
        if (size == capacity) {
            System.out.println("Queue is full. Cannot enqueue.");
        } else {
            queue[rear] = item;
            rear = (rear + 1) % capacity;
            size++;
        }
    }

    public int dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return -1;
        } else {
            int item = queue[front];
            front = (front + 1) % capacity;
            size--;
            return item;
        }
    }
}

위 코드에서는 큐의 크기를 지정하여 초기화하고, enqueue 메서드와 dequeue 메서드를 구현하여 요소의 추가와 추출을 수행합니다.

마무리

자바에서의 원형 큐는 고정된 크기를 가지고 있으며, 배열을 이용하여 구현됩니다. 원형 큐의 동작 방식과 자바에서의 구현 예제를 통해 원형 큐에 대한 이해를 높일 수 있습니다. 또한, 효율적인 자료구조를 활용하여 프로그램을 개발하는 데 도움이 될 것입니다.

이상으로 자바의 원형 큐(Circular Queue) 자료구조에 대한 이해를 마무리하도록 하겠습니다.

참고문헌: GeeksforGeeks - Circular Queue