[java] 자바 큐 인터페이스의 순환 큐 구현 방법

15 Dec 2023

java

자바에서 큐(Queue)는 데이터를 선입선출(FIFO) 방식으로 처리하기 위한 자료 구조로, 자바 컬렉션 프레임워크에서 제공하는 Queue 인터페이스를 구현하여 사용할 수 있습니다. 이번에는 Queue 인터페이스를 구현한 순환 큐(Circular Queue)를 구현하는 방법에 대해 알아보겠습니다.

1. 순환 큐(Circular Queue)의 개념

순환 큐는 고정된 크기의 원형 구조를 가지며, 큐의 끝에 도달하면 다시 처음으로 돌아가는 특징을 가지고 있습니다. 이는 배열이나 원형 연결 리스트를 이용하여 구현할 수 있습니다.

2. 배열을 이용한 순환 큐 구현 방법

public class CircularQueue {

    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int nItems;

    public CircularQueue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(int value) {
        if (rear == maxSize - 1) {
            rear = -1;
        }
        queueArray[++rear] = value;
        nItems++;
    }

    public int remove() {
        int temp = queueArray[front++];
        if (front == maxSize) {
            front = 0;
        }
        nItems--;
        return temp;
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public boolean isFull() {
        return (nItems == maxSize);
    }
}

위의 코드는 배열을 이용하여 순환 큐를 구현한 예시입니다. insert 메서드를 통해 항목을 삽입하고, remove 메서드를 통해 항목을 제거할 수 있습니다.

3. 원형 연결 리스트를 이용한 순환 큐 구현 방법

배열 이외에도 원형 연결 리스트를 이용하여 순환 큐를 구현할 수 있습니다. 이 경우, 원형 연결 리스트 구조를 활용하여 큐의 끝에 도달하면 다시 처음으로 돌아가는 특성을 구현할 수 있습니다.

class Node {
    int data;
    Node next;
}

public class CircularQueue {

    private Node front, rear;

    public CircularQueue() {
        front = null;
        rear = null;
    }

    public void insert(int value) {
        Node newNode = new Node();
        newNode.data = value;
        if (front == null) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        rear.next = front;
    }

    public int remove() {
        if (front == null) {
            throw new NoSuchElementException();
        }
        int value = front.data;
        if (front == rear) {
            front = null;
            rear = null;
        } else {
            front = front.next;
            rear.next = front;
        }
        return value;
    }

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

위의 코드는 원형 연결 리스트를 이용하여 순환 큐를 구현한 예시입니다. insert 메서드를 통해 항목을 삽입하고, remove 메서드를 통해 항목을 제거할 수 있습니다.

순환 큐는 데이터가 넘치더라도 기존의 공간을 재활용하여 효율적으로 저장하고, 연결 구조를 가진 원형 연결 리스트를 활용하면 구현이 간단해집니다. 따라서 상황에 맞게 적절한 방식을 선택하여 순환 큐를 구현할 수 있습니다.

참고 자료

Java API 문서: Queue 인터페이스