원형 큐 - Circular Queue

큐 자료구조의 특징은 First In First Out이라는 것이다. 

큐를 구현하기 위해 보통 선형 큐를 구현하는데 

배열의 메모리 공간에서 front 포인터와 rear포인터를 규칙에 맞게 이동하면서 구현하게 된다.

enqueue : rear + 1 , dequeue : front + 1

과 같이 포인터를 조정해준다. 

그렇다면 원형큐는 무엇인가?

선형 큐를 구현하면서 문제는 주기적으로 enqueue 되고 dequeue되면 인덱스를 조정하면서 front가 점차 뒤로 가게되면서 앞쪽 메모리 공간을 효율적으로 사용 할 수 없게 된다. 그래서 메모리 공간을 다 쓰면 다시 앞으로 돌아와서 메모리공간에 enqueue, dequeue할 수 있는 원형 큐가 필요하게 된 것이다. 

원형큐는 어떤식으로 구현하나?

우선 10의 크기를 가진 큐를 사용하기 위해서는 11만큼의 배열 사이즈를 할당해야 한다. 

큐의 첫 번째 인덱스는 항상 비워두어야 하기 때문이다. 첫 번째 인덱스를 비워놓음으로서 원형 큐가 공백상태인지 포화상태인지 판단 할 수 있게 된다.

공백 상태 : front == rear

포화 상태 : front % M == (rear + 1) % M

	초기상태 FRONT = 0 REAR = 0
	A, B가 차례로 삽입되면서 REAR의 포인터가 하나씩 상승했다. FRONT = 0 REAR = 2
	10개의 메모리 공간이 가득 찼다. 그러므로 큐에 더 이상 값을 삽입할 수 없는 상태다. ISFULL상태 (REAR + 1) % SIZE == FRONT % SIZE 이 만족되므로 더 이상 푸시할 수 없다.
	DEQUEUE했다. FRONT = (FRONT + 1) % SIZE 를 실행해준다. 이제 가득 차 있는 상태가 아니다.
	다시 하나 더 ENQUEUE해준다. 다시 가득 찬 상태가 되었다.
	모두 DEQUEUE해주면서 FRONT를 하나씩 증가시켜준다. 다시 제자리로 돌아온다. FRONT == REAR 조건이므로 더 이상 큐를 DEQUEUE할 수 없다.

코드로 표현하면 다음과 같다. 

ISFULL상태와 ISEMPTY상태를 따로 빼지 않았다.

<CIRCULAR QUEUE 소스 코드>

public class CirCularQueue {
    final int ArraySize = 10;
    int front = 0, rear = 0;
    int[] arr = new int[ArraySize];
    public void Enqueue(int data){
        if((rear + 1) % ArraySize ==  front % ArraySize){
            System.out.println("CircularQueue Full!!");
        }
        else{
            rear = (rear + 1) % ArraySize;
            arr[rear] = data;
        }
    }
    public void Dequeue(){
        if(front == rear){
            System.out.println("CircularQueue Empty!!");
        }
        else{
            front = (front + 1) % ArraySize;
            System.out.println(arr[front]);
        }
    }
    public void showArray(){
        for(int i = 1;i<ArraySize;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public int getFront(){
        return arr[front + 1];
    }
}