C Data Structure - 원형 큐

드디어 원형 큐이다. 자기소개 페이지를 좀 작성하느라, 기록을 하지 못했다.. ㅎㅎ ㅠ.ㅠ

일단, 원형 큐이다. 지난 포스팅 기록에서 처럼 구조로 인해 어쩔 수 없는 단점과 문제를 가지고 있는 일반 배열 기반 큐에서 개선된 것이 원형 큐이다. 그 단점이자 문제는 다음과 같다.

아니 그러면, 삽입 인덱스와 꺼냄 인덱스를 모두 초기화 시켜서 다시 앞으로 옮겨오면 되는 것 아닌가? 라는 생각이 들었었는데 이를 반박할 수 있는 사례가 또 나타난다....

바로 이 경우이다. 순서대로 읽으면 된다. 35와 43 값을 추가 후, 배열의 끝이기 때문에 가정했던대로 삽입 인덱스를 초기화 시켜서 다시 삽입하여 공간을 활용하려는 노력이 보이는 그림이다. 그럼 만약에 위 상황에서 데이터를 순회하려면 어떻게 해야하는가?

7 -> 11 -> 15 -> 35 -> 43 으로 순회를 해야할까? 아니다. 이렇게 되면 큐의 기본 원리에 제대로 위배된다. 35와 43이 먼저 나와야한다. 

위 상황에서 큐의 기본 원리를 지키며 데이터를 순회하기 위해서는
1) 꺼냄 인덱스부터 먼저 확인 후 값을 꺼낸 뒤,
2) 다시 꺼냄 인덱스를 초기화하여 인덱스 0부터 들어간 값을 꺼내며 인덱스를 증가시키고,
3) 삽입 인덱스와 접하는지를 확인한다.
-> 2, 3 을 반복한다.

나 같으면 위와 같은 짓, 안 하겠다. 원형 큐에 대해 당장 알아본다.

먼저, 왼쪽과 같은 일반 배열을 오른쪽처럼 가상으로 구부렸다고 생각하고 모든 기록을 전개할 것이다. 기본 세팅에 대해서 좀 더 설명하자면, 다음 그림과 같다.

일반 큐처럼 삽입 인덱스와 꺼냄 인덱스가 존재하며, 이름이 각각 그림과 같이 달라질 뿐이다. 그리고 각 인덱스는 대입 연산이나 삭제 연산이 진행된 후에 증가하는 형태를 기본으로 한다.

그럼 삽입과 삭제는 그림 한 장으로 설명이 가능할 것 같다.

삽입(왼) / 삭제(오)

그렇다면 삽입을 하려면 큐가 꽉 찾는지 확인해야하며, 삭제하려면 큐가 비어있는지 확인해야한다. 원형 큐의 문제가 바로 이것이기 때문에 중요하다!!!!

먼저, 다음 그림을 보면 문제가 뭔지 알 수 있다

큐가 모두 비었을 때와 가득 찼을 때의 인덱스들의 상태가 완전히 똑같다. 인덱스의 위치에 상관없이 front가 rear을 따라 잡았다는 소리는 삭제를 모두 완료했다고 볼 수 있다. 그러나, rear이 front를 따라 잡았다는 소리는 삽입을 모두 완료했다고 볼 수도 있기 때문이다. 아주 기가 막힙니다.

그래서 원형 큐를 삽입할 때, 큐의 길이 - 1 만큼만 삽입하도록 할 예정이다. 꽉 찬 상태와 텅 빈 상태는 그림과 같다.

이 약속들만 지킨다면 원형 큐를 구현하면서 기가 막힐 일은 없을 것이다.

코드 및 실행 결과

----

#include <stdio.h>
 
#define QUEUE_LEN 11
 
#define TRUE 1
#define FALSE 0
 
// 배열 기반 원형 큐 구현
struct array_queue
{
    int front;
    int rear;
    int queue_array[QUEUE_LEN];
};
typedef struct array_queue queue;
 
void QueueInit(queue* q);
int Dequeue(queue* q);
int Enqueue(queue* q, int data);
void ShowQueue(queue* q);
 
int main(void)
{
    queue q;
 
    QueueInit(&q);
 
    for (int i = 0; i < 10; i++)
    {
        Enqueue(&q, i);
        ShowQueue(&q);
    }
    Enqueue(&q, 1000);
    printf("------ end enqueue ------\n");
    ShowQueue(&q);
 
    printf("####################################################################################\n");
 
    for (int i = 0; i < q.rear; i++)
    {
        Dequeue(&q);
        ShowQueue(&q);
    }
    Dequeue(&q);
    printf("------ end dequeue ------\n");
    ShowQueue(&q);
 
 
    printf("####################################################################################\n");
 
    Enqueue(&q, 1000); ShowQueue(&q);
    Enqueue(&q, 1002); ShowQueue(&q);
    Enqueue(&q, 1004); ShowQueue(&q);
    Enqueue(&q, 1006); ShowQueue(&q);
    Dequeue(&q); ShowQueue(&q);
    Dequeue(&q); ShowQueue(&q);
 
 
    return 0;
}
 
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = -1; // 큐 출력을 위한 초기화
    return;
}
int Dequeue(queue* q)
{
    int rval = 0;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        printf("Queue가 이미 비었습니다.\n");
        return 0;
    }
    rval = q->queue_array[q->front];
 
    q->queue_array[q->front] = -1;
    q->front = (q->front + 1) % QUEUE_LEN;
 
    return rval;
}
int Enqueue(queue* q, int data)
{
    int rval = 0;
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    // 2.
    if ((q->rear + 1) % QUEUE_LEN == q->front) // 원형 큐이기 때문에 나머지 연산을 통해서 원형 순회를 이룬다.
    {
        printf("Queue가 가득 찼습니다.\n");
        return 0;
    }
    // 1.
    q->queue_array[q->rear] = data;
    rval = q->queue_array[q->rear];
    q->rear = (q->rear + 1) % QUEUE_LEN;
 
    return rval;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < QUEUE_LEN; i++)
        printf("[%2d]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 

----