[자료구조][C] 큐 _ 원형큐 (Circle Queue)

🔔 원형 큐 

선형 큐에서 더 발전된 형태인 원형 큐를 살펴보자. 앞서 말했듯 선형 큐는 front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지 못한다. 따라서 주기적으로 모든 요소들을 왼쪽으로 옮겨주어야 한다.

즉, 매번 요소들을 이동시키기 위해서는 상당한 시간과 복잡한 코딩이 소요된다.

 

원형 큐는 이러한 선형 큐들의 문제점을 해결한다. 배열을 선형이 아닌 원형으로 생각을 하는 건데 즉 front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1) 에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다. 

 

 

🔔 원형 큐 전체 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct{
    element data[MAX_QUEUE_SIZE];
    int rear,front;
}QueueType;

void error(char* message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}
void init_queue(QueueType* q){
    q->front=q->rear=0;
}
int is_empty(QueueType* q){
    return (q->front == q->rear);
}
int is_full(QueueType* q){
    return ((q->rear+1) % MAX_QUEUE_SIZE == q->front);
}
void queue_print(QueueType* q){
    printf("QUEUE(front=%d rear=%d)",q->front,q->rear);
    if(!is_empty(q)){
        int i=q->front;
        do {
            i=(i+1)%(MAX_QUEUE_SIZE);
            printf(" %d |",q->data[i]);
            if(i==q->rear)
                break;
        }while (i!=q->front);
    }
    printf("\n");
}
void enqueue(QueueType* q,element item){
    if (is_full(q))
        error("큐가 포화상태입니다.");
    else{
        q->rear=(q->rear+1) % MAX_QUEUE_SIZE;
        q->data[q->rear]=item;
    }
}
element dequeue(QueueType* q)
{
    if (is_empty(q))
        error("큐가 공백상태 입니다.");
    q->front=(q->front+1)%MAX_QUEUE_SIZE;
    return q->data[q->front];
}

element peek(QueueType* q){
    if(is_empty(q))
        error("큐가 공백상태입니다.");
    return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}

int main(){
    QueueType queue;
    int element;
    
    init_queue(&queue);
    printf("---- 데이터 추가 단계 -----\n");
    while (!is_full(&queue))
    {
        printf("정수를 입력하시오: ");
        scanf("%d",&element);
        enqueue(&queue,element);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다.\n\n");
    
    printf("-- 데이터 삭제 단계 --\n");
    while(!is_empty(&queue))
    {
        element=dequeue(&queue);
        printf("꺼내진 정수: %d\n",element);
        queue_print(&queue);
    }
    printf("큐는 공백상태입니다. \n");
    return 0;
}

 

 

---

 

typedef int element;
typedef struct{
    element data[MAX_QUEUE_SIZE];
    int rear,front;
}QueueType;

원형 큐도 기본적으로는 큐이기 때문에 큐와 똑같은 구조체를 지닌다. 

 

void init_queue(QueueType* q){
    q->front=q->rear=0;
}

front == rear 는 원형 큐가 비어 있음을 나타낸다. 원형큐에서는 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백상태를 구분하기 위함이다. 만약 한 자리를 비워두지 않는다면 공백과 포화상태 모두 rear==front 이기 때문에 구분할 수없다. 따라서 원형 큐에서 만약 front==rear 이면 공백 상태가 되고 만약 front가 rear보다 하나 앞에 있으면 포화 상태가 된다. 

 

int is_full(QueueType* q){
    return ((q->rear+1) % MAX_QUEUE_SIZE == q->front);
}

현재 큐가 공백상태인지 검사하기 위해, 현재 rear 변수에서 한 칸 더 커질때 front 함수와 같은지를 확인하여 리턴해준다. 

 

void enqueue(QueueType* q,element item){
    if (is_full(q))
        error("큐가 포화상태입니다.");
    else{
        q->rear=(q->rear+1) % MAX_QUEUE_SIZE;
        q->data[q->rear]=item;
    }
}

enqueue 함수는 데이터를 삽입하는 역할이다. 여기서 중요한 점은 rear의 인덱스가 0 -> 1 -> 2 -> 3 -> ... -> MAX_QUEUE_SIZE-1까지 진행되다 index 초과시 다시 0으로 돌아가게 해야한다는 것이다.

 

가장 간단한 방법으론 아래처럼 if 문을  사용하는 방안이 있다. 

if(q->rear == MAX_QUEUE_SIZE-1){
	q->rear==0;
}

그러나 매번 rear이나 front 변수를 업데이트 할 때마다 검사하기엔 귀찮고 힘들다. 따라서 % 연산자를 활용해준다. 

(q->rear+1) % (MAX_QUEUE_SIZE)를 해준다면 q->rear+1 < MAX_SIZE 면 q->rear+1 이 그대로 유지될 것이고, q->rear+1 == MAX_SIZE 라면 MAX_SIZE % MAX_SIZE 이므로 0이 나오게 된다. 원형 큐에서는 이러한 알고리즘으로 rear 변수와 front 변수를 업데이트 해준다. 

 

element dequeue(QueueType* q)
{
    if (is_empty(q))
        error("큐가 공백상태 입니다.");
    q->front=(q->front+1)%MAX_QUEUE_SIZE;
    return q->data[q->front];
}

 dequeue 함수는 데이터를 삭제하는 역할을 한다. 데이터 삭제시 front가 움직이면서 데이터를 삭제한다.

front 변수를 한 칸 이동한 뒤, front 변수에 해당하는 index의 값을 리턴한다. 중요한 점은 dequeue() 함수에선 return 만을 수행하고 따로 기존에 저장되어 있던 값을 바꾸지 않는 다는 점이다. 

 

 

---

참고 - 

https://m.blog.naver.com/sooftware/221512458414 

c언어로 구현하는 원형큐(Circle Queue) [자료구조]