특징

선형 큐(Queue)는, 이미 사용한 영역인 front의 앞부분에 대해서 다시 활용을 못하기 때문에 메모리를 낭비한다는 단점이 있었다.
그리고 큐가 다 찼을 경우 데이터들을 앞쪽으로 이동시켜 사용하는 방법이 있지만 남아있는 모든 데이터를 다 이동시켜야 한다는 불편한 작업을 수행해야 하기 때문에 그리 효율적으로 동작하지 못한다.

이런 문제를 해결하고자 나온 큐가 바로 원형 큐이다.

큐의 형태가 다음과 같이 원형으로 되어 있어 원형 큐라고 한다.
원형 큐는 처음과 끝이 연결되어 있는 형태로, 데이터가 배열의 끝에 다다르면 다시 처음으로 돌아올 수 있어 이미 사용했던 부분도 재사용이 가능하다.

연산

원형 큐의 연산은 선형 큐와 거의 흡사하다.
여기서는 삽입, 삭제만 다룰 것이다.

삽입

처음에 front와 rear는 같은 지점에서 시작하게 된다.
이후 삽입이 될때마다 rear가 한 칸씩 증가되는 것은 선형 큐와 동일하다.

삽입할 때 선형 큐와 다른 점이라고 한다면, 데이터가 삭제된 부분에도 다시 삽입이 가능하다는 점이다.
위 배열에서 A와 B를 지우고 다시 삽입을 한다고 하면, 데이터를 다시 삽입할 때 A와 B자리에도 데이터를 삽입할 수 있다.

단, 원형 큐의 경우에는 배열이 꽉차있는지, 비어있는지를 구분하기 위하여 한 칸의 공백은 무조건 있어야 한다.
위 배열에서 E, F, G를 삽입 했다면 한 칸이 남음에도 불구하고 front가 가리키는 위치에는 데이터를 삽입할 수 없다.

삭제

데이터 삭제 연산은 선형큐와 똑같이 작용한다.

장단점

장점

• 선형큐와 비교하였을 때, 메모리 낭비가 발생하지 않는다.

단점

• 똑같은 배열이기에 크기가 정해져있다.

예제코드

public class CircularQueue {
    
    // 큐 배열은 front와 rear 그리고 maxSize를 가진다.
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    public CircularQueue(int maxSize){    
        this.front = 0;
        this.rear = -1;
        
        // 실제 크기보다 하나 크게 지정한다 (공백과 포화를 막기 위함)
        this.maxSize = maxSize+1;    
        this.queueArray = new Object[this.maxSize];
    }
    
    public boolean empty(){
        return (front == rear+1) || (front+maxSize-1 == rear);
    }
    
    public boolean full(){
        return (rear == maxSize-1) || (front+maxSize-2 == rear);
    }
    
    public void insert(Object item){
        if(full()) throw new ArrayIndexOutOfBoundsException();
        
        // rear 가 배열의 마지막이면 rear 포인터를 앞으로 돌린다.
        if(rear == maxSize-1){
            rear = -1;
        }
        queueArray[++rear] = item;
    }
    
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        
        return queueArray[front];
    }
    
    public Object remove(){
        
        Object item = peek();
        front++;
        
        // front의 다음 index가 배열크기+1 이면 처음으로 돌아간다
        if(front==maxSize){
            front = 0;
        }
        
        return item;
    }

}