CirculaQueue

1. 개요

선입선출(先入先出, First In First Out; FIFO)의 자료구조로써, 데이터가 나가는 위치, 큐의 첫번째 위치를 Front 라고 하고 데이터가 삽입되는 지점, 큐의 마지막 데이터의 한 칸 다음 위치를 Rear 혹은 Back이라고 한다.
큐에 데이터를 삽입하는 과정을 Enqueue, 빼는 과정을 Dequeue라고 한다. 선입선출 형태이므로 주로 대기열, 줄서기 같은곳에 쓰이는 구조이다.

2. 선형 큐 (Linear Queue)

예를들어 사이즈가 5인 큐가 있다고 하자. 초기에는 Front와 Rear 둘다 0을 가리키고 있는상태이다. 데이터를 하나 삽입하면 Front값을 그대로 Rear값은 하나 증가한다 (1번방 가리키고있는상태) 그 다음 방금 넣었던 데이터를 삭제하면 Front값이 하나 증가하여 1번방을 가리키고, 이 상태는 큐가 비었다는것을 뜻 한다.( Front == Rear )

데이터를 5개 모두 넣었다면 Rear값은 5가 되어있을것이고 큐가 모두 찼으므로 이 상태는 큐가 포화상태라는 것을 뜻 한다. ( 큐 Size == Rear )

이렇게만 보면 선형 큐가 문제가 없어보이지만 바로 여기서 선형 큐의 맹점이 드러난다. 현재 큐가 꽉 차있는 상태에서 데이터를 하나 삭제하게되면 Front값이 1로 증가할것이고 빈 방 1개가 나올것이다, 그런데 Front는 1 이고 Rear는 5이므로 큐의 공백조건을 만족하지 못하므로 빈 방이 있음에도 불구하고 큐의 데이터삽입이 불가능하게 된다. 이러한 맹점을 보완한것이 바로 **원형 큐 (Circular Queue)**이다.

3. 원형 큐 (Circula Queue)

**원형 큐 (Circular Queue)**는 선입선출(先入先出, First In First Out; FIFO)를 그대로 유지하면서 큐의 입구와 출구를 연결하여 원형으로 만들어 사용하는 구조이다.이때, Front와 Rear사이에 완충지대를 두어 원형 큐의 비어있는 상태와 포화상태를 구분한다. 완충지대의 위치는 항상 Front의 하나 앞방이다. (유동성)

완충지대 때문에 예를들어 7개의 데이터를 넣는 큐를 만드려면 큐의 사이즈를 8으로 지정하여야한다. 초기에는 Front와 Rear는 0으로 설정한다. 자동으로 완충지대는 [7]번방이 된다.
원형 큐 에서는 Rear값 및 Front값을 증가시킬때 선형 큐처럼 단순히 +1을 하게되면 원형 큐가 되지 않으므로 “%” 기능을 활용하여 Rear값을 바꿔준다.
Rear가 0번방에서 1번방으로 가야하므로 +1을 해준뒤 큐 사이즈만큼 나눠주고 나머지 값을 Rear값으로 하면 된다. ( Rear = (Rear+1) % QueueSize )

계속 데이터를 삽입하여 7번방까지 데이터를 삽입하였다면 Rear가 완충지대를 가리키고 있을것이고 이 상태는 포화상태를 의미한다. 즉, Rear가 완충지대를 가리키고있다면 큐는 포화상태라는 뜻이다. 공백상태는 선형 큐와 같다. Rear와 Front가 같으면 공백상태를 뜻한다.
그러면 여기서, 아까 선형 큐가 해결하지 못했던 문제를 해결할 수 있다. 데이터가 꽉 차있는 상태에서 Dequeue를 하여 Front값을 1로 바꿔준다 ( Front = (Front +1) % QueueSize )
그러면 자동으로 완충지대는 Front가 이동하였으므로 원래위치 7번방에서 (Front의 이전 방) 0번방으로 옮겨갈 것이다.

따라서, Rear는 완충지대를 가리키고 있지 않으므로 큐의 포화조건에서 탈출하게 되고 데이터의 삽입이 가능해진다. Rear가 7번방이었으므로 위와같이 ( Rear = (Rear+1) % QueueSize ) 를 이용하면 Rear는 0번방을 가리키며 0번방에 데이터를 삽입하게 된다.

4. 코드 구현

4-1. define structure

typedef struct _queue {
    DataType *queue;
    int qSize;
    int front, rear;
}Queue;

4-2. Create Queue

void initQueue(Queue * qPtr, int size) {
    qPtr->qSize = size;
    qPtr->front = 0;
    qPtr->rear = 0;
    qPtr->queue = (DataType *)calloc(qPtr->qSize, sizeof(DataType));
}

4-3. Enqueue

int enqueue(Queue * qPtr, DataType inData) {
    // rear가 완충지대에 있으면 put불가 
    if((qPtr->rear+1)%qPtr->qSize == qPtr->front){
        return FALSE;
    }
    qPtr->queue[qPtr->rear] = inData;
    qPtr->rear++;
    qPtr->rear = (qPtr->rear)%qPtr->qSize;
    return TRUE;
}

4-4. Dequeue

int dequeue(Queue * qPtr, DataType * getData) {
    // 큐가 비어있으면 dequeue 불가
    if( isQueueEmpty(qPtr) ) {
        return FALSE;
    }
    *getData = qPtr->queue[qPtr->front];
    qPtr->front++;
    qPtr->front = (qPtr->front)%qPtr->qSize;

    return TRUE;
}

4-5. Check

int isQueueEmpty(const Queue *qPtr) {
    if(qPtr-> front == qPtr->rear)
        return TRUE;
    else
        return FALSE;
}