원형큐 구현하기

앞에서는 선형큐를 구현해보았다.

선형큐는 이해하기 쉽고 간편하지만, 문제점이 있다.

front와 rear가 계속 증가만 하기 때문에 한정적인 배열에서 결국 끝에 도달하게 되고,

큐의 앞부분이 비어있더라도 사용하지 못한다.

따라서 요소들을 왼쪽으로 매번 이동시켜야한다. (코딩 복잡도 상승, 속도 느림)

이런 문제점들을 해결하기 위해서 나온 방법이 원형큐 이다.

---

원형큐의 구조와 간단한 원리

원형 큐 구조

원리는 이렇다. 만약 MAX_QUEUE_SIZE가 6이라고 가정해보자.

front과 rear의 값이 계속 증가할 때, MAX_QUEUE_SIZE - 1에 도달하면

다음으로 증가되는 값을 0이 되도록 하면된다.

실제로 원형으로 생성되는 것이 아니라, 개념상 원형으로 구현이 된다고 생각하면 된다.

---

원형큐의 데이터 삽입 과정

 

초기상태

초기상태

선형큐와는 달리 원형큐에서는 front와 rear가 0부터 시작한다.

데이터 삽입시에 rear를 한칸 증가시키고 그 자리에 삽입

삭제시에 front를 한칸 증가시키고 그 자리에 삽입.

 

 

A삽입

A삽입

rear를 1칸 증가시키고 A데이터를 삽입한다.

 

과정

계속 데이터를 삽입하고, 삭제를 하는 과정을 그림으로 간단히 보면,

이런 과정을 가진다.

---

주의할 점

원형큐에서 주의할 점이 있다.

원형큐에서는 하나의 자리는 항상 비워둔다.

만약, 하나의 자리를 비워두지 않는다면

그림과 같이 공백상태와 포화상태를 구별할 수 없다.

 

 

그래서 한칸 비워두는 것을 원칙으로 하고, 그것을 포화 상태라고 한다.

---

원형큐에서의 나머지 연산

원형큐에서 삽입과 삭제를 구현할 때, 나머지 연산을 이용한다.

왜 나머지 연산을 이용할까?

예를 들어, 원형큐의 사이즈가 5(MAX_QUEUE_SIZE)라고 가정해보자.

데이터의 삽입 삭제를 한다면, front와 rear가 계속 증가시켜야 할 것인데, 

++front, ++rear를 사용한다면 언젠가 큐의 사이즈를 벗어날 것이다.

 

이 문제를 어떻게 해결 할까?

rear = (rear + 1) % MAX_QUEUE_SIZE

front = (front + 1) % MAX_QUEUE_SIZE

이렇게 한다면, rear와 front가 증가하지만 증가하는 범위가 0, 1, 2, 3, 4, 0이런식으로

0~4에서 순환하는 형태가 된다.

 

나머지 연산을 사용해야 원형으로 빙글빙글 돌 수 있는 형태가 된다.

---

원형큐의 구현

이제부터 원형큐를 구현해보자.

먼저 큐를 구현하기 위해 필요한 것들을 작성해 보면,

 

1. empty인지, full인지 확인하는 함수

2. 원형큐를 초기화 하는 함수

3. 데이터 삽입, 데이터 삭제 함수

4. 삭제하지않고 데이터 확인하는 함수

5. 원형큐 출력하는 함수

 

 

 

1.empty상태인지 full상태인지 확인하는 함수

int is_empty(QueueType *q)
{
    if(q->front == q->rear) //공백상태
        return 1;
    else
        return 0;
}

front와 rear가 같다면 공백상태 이다.

 

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

여기서 나머지 연산이 사용된다.

rear + 1은 front와 한칸차이가 나야하기 때문이다.(한칸 비워야지 포화상태)

그리고 rear값이 큐 사이즈(5)를 넘어도 0~4까지 돌기 위해서 나머지 연산자를 사용했음.

 

2. 원형큐를 초기화하는 함수

#include <stdio.h>
#define MAX_QUEUE_SIZE 5

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

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

큐 사이즈는 5로 했다.

그렇다면 front와 rear가 0~4만 빙글빙글 돌아야한다.

마찬가지로 원형큐는 front와 rear가 0부터 시작한다.

 

3. 데이터 삽입, 삭제 함수

void enqueue(QueueType *q, element item)
{
    if(is_full(q) == 1){
        printf("full");
    }
    else{
        q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
        q->data[q->rear] = item;
    }
}

여기서도 마찬가지.

rear을 단순히 증가만 시키면 큐 사이즈를 벗어나게 된다.

rear = (rear + 1) % MAX_QUEUE를 해줘야, rear를 증가시키면서도 0~4를 돌면서 증가시키도록 한다.

 

element dequeue(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
    }
    else{
        q->front = (q->front + 1) % MAX_QUEUE_SIZE;
        return q->data[q->front];
    }
}

여기서도 , front를 증가시키고 , 나머지연산을 이용해서

데이터를 추출해온다.

 

4. 삭제하지않고 데이터만 확인하는 함수

element peek(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
    }
    else
        return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

데이터를 삭제하는 함수하고 다른점은

front 자체를 이동시키지는 않는다는 점이다.

(삭제함수와는 달리 q->front = (q->front + 1) % MAX_QUEUE 이부분이 없다)

 

5. 원형큐 출력하는 함수

void print_queue(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);
    }
}

---

전체 코드

#include <stdio.h>
#define MAX_QUEUE_SIZE 5

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

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

int is_empty(QueueType *q)
{
    if(q->front == q->rear) //공백상태
        return 1;
    else
        return 0;
}

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

void enqueue(QueueType *q, element item)
{
    if(is_full(q) == 1){
        printf("full");
    }
    else{
        q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
        q->data[q->rear] = item;
    }
}

element dequeue(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
    }
    else{
        q->front = (q->front + 1) % MAX_QUEUE_SIZE;
        return q->data[q->front];
    }
}

element peek(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
    }
    else
        return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

void print_queue(QueueType *q)
{
    printf("Queue = (front %d rear %d) \n", 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");
}

int main(void)
{
    QueueType q;
    init_queue(&q);
    int element;

    printf("======데이터 삽입======\n");
    while(!is_full(&q)){ //가득 찰 때까지
        printf("정수 입력 : ");
        scanf("%d", &element);
        enqueue(&q, element);
        print_queue(&q);
    }
    printf("큐가 포화상태\n");

    printf("=======데이터 삭제========\n");
    while(!is_empty(&q)){ //공백 상태 될 때까지
        dequeue(&q);
        print_queue(&q);
    }
    return 0;
}