C로 구현하는 자료구조 - Queue

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

선형 큐 (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)**이다.

원형 큐 (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번방에 데이터를 삽입하게 된다.

Implementation

structure

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

큐를 관리하는 구조체
데이터를 저장할 데이터필드 영역과 큐의 크기를 저장하는 변수, Front와 Rear를 지정하는 변수로 이루어져있다.

initialize

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

큐를 초기화 및 생성하는 함수
전달인자로 큐의 사이즈를 받아서 큐의 사이즈를 넣어주고, Front와 Rear의 값을 모두 0으로 초기화한뒤 calloc함수를 통해 size만큼 메모리를 할당받는다.

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;
}

큐에 데이터를 삽입하는 함수
처음 조건문을 걸어서 큐가 비어있는지 확인한다. Rear가 완충지대에 있으면 큐가 포화상태인것이므로 True시 False를 리턴한다. False일시, 아래 코드로 내려와서 현재 Rear값에 데이터를 넣어주고, Rear값 증가한다.
(Rear = (Rear+1) % QueueSize)

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;
}

큐에서 데이터를 빼와 출력하는 함수
전달인자로 출력할 데이터의 주소값을 받아오고 초기 조건문으로 큐가 비어있는지 함수를 통해 확인, 비어있지않을시, Front방의 값을 불러오고 front를 하나 증가시킨다.
( Front = (Front +1) % QueueSize )

check

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

큐가 비었는지 확인하는 함수로 Front와 Rear가 같을때 큐가 빈것으로 판별

선형 큐 (Linear Queue)#

원형 큐 (Circula Queue)#

Implementation#

structure#

initialize#

enqueue#

dequeue#

check#