[자료구조및알고리즘이해] 원형 Queue

과제3을 진행하면서 이런 방식의 원형 큐도 구현할 수 있길래 정리해둔다. 

 

// Queue 구조체 정의 (FIFO)
typedef struct
{
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;

원형 큐를 정의하면서 size와 capacity변수가 추가되었다. 

 

// Queue 생성 함수
Queue *createQueue(int capacity)
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity -1;
    queue->data = (int *)malloc(queue->capacity * sizeof(int));
    return queue;
}

createQueue 함수는 Queue를 생성하는 함수이다. front를 0으로 초기화하는 반면 rear는 capacity - 1로 초기화하고 있다. 

 

이와 같은 구조는 일반적으로 원형 큐가 front와 rear 사이 한칸의 공백을 두는 것과는 차이가 있다. 이는 아래의 enqueue동작을 수행할 때, 처음으로 데이터를 삽입하면 front를 rear와 일치시키기 위한 목적이다. 

 

 

void enqueue(Queue *queue, int item)
{
    // 함수 구현
    if (isQueueFull(queue)) // if queue is full
        return; // cannot enqueue as queue is full
    else
    {
        queue->rear = (queue->rear + 1) % queue->capacity; // move rear to the next position (Circular Queue)
        queue->data[queue->rear] = item; // add the item at the rear position
        queue->size++; // increase the queue size
    }
}

enqueue 함수는 Queue에 새로운 항목을 추가하는 함수이다. 

첫 번째 항목의 enqueue 이후 front는 이 항목의 인덱스여야 한다. 따라서 queue->rear을 다음 위치, 즉 (queue->rear + 1) mod (queue->capacity)로 설정한다. 그 결과 rear은 0이 되고, queue->data[queue->rear]에 항목을 삽입함으로써 front = rear = 0 에 항목이 저장된다. 그리고 size를 1 증가시켜 queue의 항목 수를 업데이트한다. 그 결과 (b)와 같은 상태가 된다. 만약 한번 더 enqueue를 수행하면 (c)와 같은 상태가 된다.