[ 자료구조 ] 큐(Queue)

THIST·2024년 8월 29일

이번 글에서는 자료구조 중 하나인 큐(Queue)에 대해 알아보도록 하자.
큐는 컴퓨터 과학에서 자주 사용되는 기본적인 자료구조로, 데이터를 선입선출(FIFO, First In First Out) 방식으로 관리된다.
먼저 들어온 데이터가 먼저 처리되는 구조로, 여러 가지 상황에서 매우 유용하게 사용되고 있다.

큐(Queue)의 기본 개념

큐는 First In, First Out(FIFO) 구조를 따르는 선형 자료구조이다. 이는 줄을 서서 기다리는 상황과 유사하게, 먼저 들어온 데이터가 가장 먼저 나가는 것을 의미한다.

큐에서 사용되는 연산들은 다음과 같다.

삽입(Enqueue): 큐의 끝(Rear)에 새로운 Data를 추가한다.
삭제(Dequeue): 큐의 앞(Front)에 Data를 제거하고 반환한다.
큐가 가득 찼는지 확인(Queue_full): 큐가 더 이상 Data를 추가할 수 없는 상태인지 확인한다.
큐가 비어 있는지 확인(Queue_Empty): 큐에 Data가 없는 상태인지 확인한다.

위의 네 가지 경우에 대해 그림으로 보도록 하자.

1. 최초의 큐(Queue)상태

현재 Queue내에는 아무런 Data가 존재하지 않음으로, Front와 Rear를 -1로 초기화
(배열은 0번부터 시작하기 때문에)

2. 'Apple' Data 삽입(Enqueue)

최초의 Data가 Queue에 들어오게 된다면 Front와 Rear를 0으로 초기화.

3. 'Melon' Data 삽입(Enqueue)

Data가 삽입되었으므로 Rear를 1증가.

4. 'Cake' Data 삽입(Enqueue)

Data가 삽입되었으므로 Rear를 1증가.

5. 'Apple' Data 삭제(Dequeue)

Data가 삭제되었으므로 Front를 1증가.

6. 'Phone' Data 삽입(Enqueue)

Data가 삽입되었으므로 Rear를 1증가.

7. 'Melon' Data 삭제(Dequeue)

Data가 삭제되었으므로 Front를 1증가.

8. 'Cake' Data 삭제(Dequeue)

Data가 삭제되었으므로 Front를 1증가.
(Front와 Rear의 위치가 같아졌다. 이로써 Data가 하나만 남음을 의미.)

9. 'Phone' Data 삭제(Dequeue)

Data가 삭제되었으므로 Front를 1증가.
(Front가 Rear값을 초과하였다. 이로써, Queue는 값이 비었음을 의미.)

이렇듯 큐는 무조건 순차적으로 따르는것인가? 라고 생각할 수 있지만, Queue에는 종류가 많다.
이러한 Queue를 응용하여 선형큐(Circular Queue)와 우선순위큐(Priority Queue)등이 존재한다.

그리고 방금처럼 순환되지 않는 큐를 우리는 비순환 큐(Non-Circular Queue)라고 표현한다.

이러한 비순환 큐를 구현하는 가장 기본적이고 쉬운 방법은 1차원 배열을 사용하는 것이다.

큐는 이렇듯FIFO 구조를 가지며 다양한 상황에서 데이터를 효율적으로 관리하는 데 사용되게 된다.
하지만, 비순환 배열 기반 큐는 간단하지만 메모리 낭비가 발생할 수 있는 단점이 존재한다.

Code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define M 10000  // 큐의 최대 크기를 정의

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

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

int main(void) {
    int Sel = 0;

    // 메뉴를 출력하고 사용자의 선택을 처리하는 반복문
    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);  // 사용자로부터 삽입할 값을 입력받음

    if (Rear < M) {  // Rear 값이 M보다 작다면 (큐에 공간이 남아있다면)
        arr[Rear++] = S;  // Rear 인덱스에 값을 삽입하고 Rear를 1 증가
        printf("Value is successfully Inserted!\n");
    }
    else {
        printf("Queue is Full!!\n");  // 큐가 꽉 찬 경우
    }

    return;
}

// 큐에서 값을 삭제하는 함수
void Delete() {
    if (Front >= 0 && Front < Rear) {  // Front가 0 이상이고 Rear보다 작다면 (삭제할 값이 있다면)
        Front++;  // Front를 1 증가시켜 다음 요소를 가리키게 함
        printf("Value is successfully deleted!!\n");
    }
    else {
        printf("Queue is already empty!!\n");  // 큐가 비어있는 경우
    }

    return;
}

// 큐가 비어있는지 확인하는 함수
void Queue_Empty() {
    if (Front == Rear) {  // Front와 Rear가 같다면 큐가 비어있는 상태
        printf("Queue is Empty!!\n");
    }
    else {
        printf("Queue is not Empty!!\n");  // 큐에 요소가 있는 경우
    }
    return;
}

// 큐가 꽉 찼는지 확인하는 함수
void Queue_Full() {
    if (Front == 0 && Rear == M) {  // Rear가 큐의 최대 크기 M에 도달했다면 큐가 꽉 찬 상태
        printf("Queue is Full!!\n");
    }
    else {
        printf("Queue is not Full!!\n");  // 큐에 여유 공간이 있는 경우
    }
    return;
}

// 큐의 현재 상태를 출력하는 함수
void Print_Queue() {
    // Front부터 Rear까지의 모든 요소를 출력
    for (int i = Front; i < Rear; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return;
}