큐 - C

개요

큐(Queue)는 한 쪽 끝에서 삽입이 일어나고, 그 반대쪽 끝에서 삭제가 일어나는 순차 리스트입니다. 새로운 원소가 삽입되는 끝을 Rear라고 하고, 원소가 삭제되는 끝을 Front라고 합니다. 먼저 삽입된 원소가 먼저 제거되는 선입선출(FIFO, First-In-Last-Out)의 특성을 가집니다.

추상 자료형

구조

• 큐 (Queue)
  - Elements : 큐에 저장될 데이터의 배열.
  - Front : 큐의 최전방에 있는 원소의 위치.
  - Rear : 큐의 최후방에 있는 원소의 위치.

기능

1. Delete(Queue) : 큐의 Front에 위치한 원소를 제거.
2. Add(Queue, Element) : 큐의 Rear에 새로운 원소를 삽입. 큐가 가득 찼을 경우, Delete 실행.
3. IsEmpty(Queue) : 큐가 비어있을 경우, true를 반환함. 아닐 경우, false를 반환함.
4. IsFull(Queue) : 큐가 가득 찼을 경우, true를 반환함. 아닐 경우, false를 반환함.
5. Init(Queue) : 큐를 초기화함.
6. Error(Error Code) : 오류 발생 시 원인을 출력하고 프로그램을 종료함.
7. Amount(Queue) : 큐에 저장된 원소의 개수 출력.

구현

구조

#DEFINE ARRAY_SIZE N + 1	// 이 매크로 변수에 대해서는 '구현 과정에서 고려한 것' 참조

typedef struct IntQueue* IntQueueP;
typedef struct IntQueue {
    int Elements[6];
    int Rear, Front;
} IntQueue;

기능

int Delete(IntQueueP Queue)
{
    if (IsEmpty(Queue) == 1)
        Error(1);
    Queue->Front = (Queue->Front + 1) % ARRAY_SIZE;
    return Queue->Elements[Queue->Front];
}

int Add(IntQueueP Queue, int Element)
{
    if (IsFull(Queue) == 1)
        Error(0);
    Queue->Rear = (Queue->Rear + 1) % ARRAY_SIZE;
    Queue->Elements[Queue->Rear] = Element;
    return Element;
}

int IsEmpty(IntQueueP Queue)
{
    if (Amount(Queue) == 0) return 1;
    return 0;
}

int IsFull(IntQueueP Queue)
{
    if (Amount(Queue) == ARRAY_SIZE - 1) return 1;
    return 0;
}

IntQueueP Init()
{
    IntQueueP Temp;
    Temp = malloc(sizeof(IntQueue));
    Temp->Front = 0;
    Temp->Rear = 0;
    return Temp;
}

void Error(int Code)
{
    char* ErrCause[3] = { "큐가 꽉 참", "큐가 비어 있음", "기타 오류" };
    printf("다음과 같은 오류가 발생하여 프로그램을 종료합니다: %s\n", ErrCause[Code]);
    exit(-1);
}

int Amount(IntQueueP Queue)
{
    if (Queue->Front == Queue->Rear) return 0;
    else if (Queue->Front < Queue->Rear) return Queue->Rear - Queue->Front;
    else return (SIZE - (abs(Queue->Rear - Queue->Front)));
}

구현 과정에서 고려한 것

큐의 형태

이상의 코드는 원형 큐를 구현합니다. 원형 큐의 모습은 다음 그림과 같습니다:

데이터가 저장될 배열의 크기

큐가 꽉 차 있을 때 Front와 Rear의 위치는 다음 그림과 같습니다:

그림과 같이, 큐에 저장될 수 있는 원소가 최대 5개일 경우 배열에는 6칸의 공간이 필요합니다. 큐에 저장될 원소 5개에 Front가 차지할 공간 1개가 더해지기 때문입니다. 일반화하면, 큐의 최대 크기가 N일 때 배열의 크기는 N + 1이 되어야 합니다.

따라서, 매크로 변수 ARRAY_SIZE는 배열의 크기와 같이 N + 1로 설정합니다. 그리고 이를 고려하면 다음과 같은 관계가 성립합니다:

ARRAY_SIZE = 큐의 최대 크기 + 1

삽입 또는 삭제 후 Front, Rear의 위치

원형 큐의 특징을 다시 한 번 생각해보며 그림을 봅시다:
현재 큐의 Rear가 큐의 최대 크기인 5와 일치합니다. 만약 이 상태에서 원소를 삽입한다면,다음 Rear는 그림과 같이 0이 됩니다. 이를 수식화하면 다음과 같습니다:

Rear = (Rear + 1) % ARRAY_SIZE

• 현재 Rear = 1일 경우, 다음 Rear = (1 + 1) % 6 = 2
• 현재 Rear = 2일 경우, 다음 Rear = (2 + 1) % 6 = 3
  ...
• 현재 Rear = 5일 경우, 다음 Rear = (5 + 1) % 6 = 0

이상의 수식은 큐에 원소를 추가할 때의 Rear 뿐만 아니라, 큐에서 원소를 제거할 때의 Front에도 동일하게 적용할 수 있습니다.

큐에 저장된 원소의 개수

가능한 경우의 수는 3가지입니다:

1. Front == Rear일 때, 0.
2. Front < Rear일 때, Rear - Front.
3. Front > Rear일 때, ARRAY_SIZE - (|Front - Rear|).

1은 큐가 비어 있는 상태를 의미합니다. 이 경우 저장된 원소의 개수는 0입니다.
2와 3은 큐가 채워져 있는 상태를 의미하지만, 모양이 조금 다릅니다.

2는 다음과 같은 모양을 갖습니다:이 경우 저장된 원소의 개수는 단순하게 Rear - Front입니다.

3은 다음과 같은 모양을 갖습니다:
이 경우 저장된 원소의 개수는 ARRAY_SIZE - (|Front - Rear|)입니다.