[ 자료구조 ] 원형큐(Circular Queue)

앞전에, 큐(Queue)에 대해서 포스팅을 진행했었다.
내가 마지막에 코드를 작성하고, 마지막줄에 이 코드는 메모리 효율성이 굉장히 떨어진다고, 비추하는 코드라고 작성했었던 기억이 있다.

처음 해보는 사람들이라면 "이게 무슨말이지?" 할 수도 있어서 그림으로 간단하게 보여주겠다.

앞선, Queue에서는 원소삭제시 단순히 Front를 앞으로 이동시키고 있기 때문에, 이전에 사용했던 원소들은 Front의 앞쪽에 고스란히 남아있게 된다.
즉, 이 공간은 사용하지 않는 쓰레기 공간이라는 것이다.
이러한 구조를 선형큐라고 (Non-Circular Queue)라고 한다.
그렇다면 어떻게 앞에 공간들을 알뜰하게 이용할 수 있을까?
그래서 나온것이 바로 원형큐라고 (Circular Queue)라고 한다.

구조는 굉장히 단순하다.

나머지 연산자(%)를 통해서 큐를 마치 원형처럼 사용하는 것이다.

잘 이해가 되지 않는가? 다음을 보자

배열의 길이가 총 5인 Arr라고 하는 배열이 있다 가정했을 때,
Point라고 배열의 인덱스를 가리키는 변수가 있다고 가정해보자.

이 때,
Point가 0일 때, Point%5 = 0 ---> Arr[0]
Point가 1일 때, Point%5 = 1 ---> Arr[1]
Point가 2일 때, Point%5 = 2 ---> Arr[2]
Point가 3일 때, Point%5 = 3 ---> Arr[3]
Point가 4일 때, Point%5 = 4 ---> Arr[4]
Point가 5일 때, Point%5 = 0 ---> Arr[0]
즉, 다시 첫 지점으로 돌아온다.

이러한 점을 이용하여, Rear이 끝까지 다 찼을경우, 다시 배열의 앞부분에 원소를 넣을 수 있는 공간이 있다면 이용하는 것이다.

그림으로 만나보자.

최초의 원형큐 상태이다. 여기서, 값을 넣으면 어떻게 될까?


이전 Queue강좌에서 동일하게 Rear 0번지에 원소가 들어가게 된다.

다음 70을 넣으면, 똑같이 Rear이 증가하면서 원소가 넣어지고 있는것을 확인해볼 수가 있다.

100 Insert.

60 Insert.

이번엔, 삭제를 해보자.

보다싶이, Front가 1증가하면서 앞의 원소를 삭제시켜주며 40이 삭제되었다.

한번 더, 삭제시켜 보겠다.

이번에도 똑같이, Front가 삭제되면서 앞으로 이동한 것을 볼 수 있다.
이제 다시 값을 넣어보자.

Rear이 원소의 마지막에 도달했다.

만약, 이상태에서 값을 넣으면 어떻게 될까?

Rear이 다시 0번지를 가르키며 값이 들어간 것을 확인할 수 있다.

이렇게, 공간을 아끼면서 넣을 수 있다는 것이 원형큐의 장점이다.

Code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define N 5  // 큐의 최대 크기를 정의

// 함수 선언
void Insert();
void Delete();
void Queue_Empty();
void Queue_Full();
void Print_Queue();

// 전역 변수 선언
int arr[N];  // 큐 배열
int Front, Rear;  // 큐의 Front와 Rear 인덱스
int cnt;

int main(void) {

    memset(arr, -1, N * sizeof(int));  // 여기서 arr은 배열, -1은 설정 값, N * sizeof(int)는 설정할 메모리 크기

    int Sel = 0;
    printf("------Circular Queue Version.------\n");
    // 메뉴를 출력하고 사용자의 선택을 처리하는 반복문
    do {
        printf(" --------------------\n");
        printf(" |    1.Insert      |\n");
        printf(" |    2.Delete      |\n");
        printf(" |    3.Is_Empty?   |\n");
        printf(" |    4.Is_Full?    |\n");
        printf(" |    5.Print       |\n");
        printf(" --------------------\n");

        printf("Select Mode:");
        scanf("%d", &Sel);  // 사용자로부터 선택을 입력받음

        // 사용자가 선택한 옵션에 따라 함수 호출
        switch (Sel) {
        case 1: {
            Insert();  // 값 삽입
            break;
        }
        case 2: {
            Delete();  // 값 삭제
            break;
        }
        case 3: {
            Queue_Empty();  // 큐가 비었는지 확인
            break;
        }
        case 4: {
            Queue_Full();  // 큐가 꽉 찼는지 확인
            break;
        }
        case 5: {
            Print_Queue();  // 큐에 있는 값을 출력
            break;
            }
        }
    } while (Sel != -1);  // 사용자가 -1을 입력할 때까지 반복

    return 0;
}

void Insert() {
    int S;
    printf("Input:");
    scanf("%d", &S);  // 사용자로부터 삽입할 값을 입력받음

    // 만약 이미 해당 위치에 원소가 있다면 Queue에는 값을 더 이상 넣을 수가 없다.

    if (arr[ Rear ] != -1) printf("Queue is already full!!\n");
        
    else { // 만약 그렇지 않다면
        arr[Rear] = S;
        Rear = (Rear + 1) % N; // Queue에는 아직 공간이 남아 있다. Rear의 다음 인덱스 지정.
        cnt++;
    }

    return;
    
}

void Delete() {
    // 만약 Front의 위치가 -1이라면 값이 없다는 것이므로
    if (arr[Front] == -1) printf("Queue is already empty!!\n");
    
    else {
            arr[Front] = -1; // 해당 요소의 Index 삭제.
            Front = (Front + 1) % N;
            cnt--;
    }

    return;
}

void Queue_Empty() {
    // 만약 Queue가 최초의 상태에서 delete를 시킬경우엔
    if (arr[Front] == -1)  printf("Queue is already empty!!\n");
    else printf("Queue is not empty!!\n");
       
    return;
}

void Queue_Full() {
    // 만약 이미 Rear의 다음인덱스에 원소가 있다면
    if (arr[Rear] != -1) printf("Queue is already full!!\n"); // Queue에는 값을 더 이상 넣을 수가 없다.    
    else printf("Queue is not full!!\n");
    
    return;
}

void Print_Queue() {
    int K;
    K = Front;
    for (int i = 0; i < cnt; i++) printf("%d ", arr[K++ % N]);
        
    printf("\n");

    return;
}