C 언어로 큐(Queue) 자료구조 구현하기: 기초부터 응용까지

큐(Queue)는 데이터가 삽입된 순서대로 처리되는 선형 자료구조로, FIFO(First In, First Out) 방식을 따릅니다. 이는 마치 줄을 서서 차례를 기다리는 것과 같은 방식으로 작동합니다. 큐는 운영 체제의 작업 스케줄링, 데이터 스트림 처리, 네트워크 패킷 처리 등 다양한 분야에서 사용됩니다. 이번 기사에서는 C 언어를 사용하여 큐를 구현하는 기본적인 방법과 함께, 실전에서 활용할 수 있는 다양한 응용 사례를 단계적으로 소개합니다. 이를 통해 자료구조와 알고리즘의 기초를 탄탄히 다질 수 있을 것입니다.

큐 자료구조란?
큐 구현의 기본 설계
링 버퍼를 활용한 큐 확장
연결 리스트를 사용한 동적 큐 구현
큐의 주요 연산 구현
큐의 예외 처리 및 경계 조건
응용 예제: 프린터 작업 관리 시스템
큐 구현을 위한 연습 문제
요약

큐 자료구조란?

큐(Queue)는 데이터를 선형으로 관리하며, FIFO(First In, First Out) 원칙을 따르는 자료구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 처리됩니다. 이는 스택(Stack)의 LIFO(Last In, First Out) 원칙과 대조적입니다.

큐의 구조와 특성

삽입(Enqueue): 큐의 뒤쪽(Rear)에서 새로운 데이터를 추가합니다.
삭제(Dequeue): 큐의 앞쪽(Front)에서 데이터를 제거합니다.
Peek(Front 확인): 큐의 앞쪽 데이터를 삭제하지 않고 확인합니다.

큐의 사용 사례

작업 스케줄링: 운영 체제의 작업 큐에서 프로세스를 순차적으로 처리.
데이터 스트림 처리: 네트워크 패킷 전송 및 수신 시 FIFO 방식으로 데이터 처리.
프린터 작업 관리: 프린터 작업 요청을 차례로 처리.

큐의 기본 유형

일반 큐: 기본 FIFO 구조를 가진 큐.
원형 큐(Circular Queue): 마지막 위치와 처음 위치가 연결되어 공간을 효율적으로 활용.
우선순위 큐(Priority Queue): 특정 조건에 따라 처리 우선순위를 결정.
이중 끝 큐(Deque): 양쪽 끝에서 삽입과 삭제가 가능한 큐.

큐는 이러한 특성과 사용 사례를 바탕으로 소프트웨어 개발의 필수적인 구성 요소로 사용됩니다. C 언어에서는 배열과 연결 리스트를 활용하여 큐를 구현할 수 있으며, 각각의 방법은 특정한 장단점을 가집니다.

큐 구현의 기본 설계

큐를 구현하기 위해 가장 단순한 방법은 배열을 사용하는 것입니다. 배열 기반 큐는 정해진 크기의 메모리를 사용하여 데이터를 순차적으로 저장하고, 삽입 및 삭제 연산을 제공합니다. 아래는 배열을 사용한 큐 설계의 주요 단계입니다.

구조체 설계

큐를 표현하기 위해 필요한 요소는 다음과 같습니다.

배열: 데이터를 저장할 메모리 공간.
크기(size): 큐의 최대 크기.
Front와 Rear 포인터: 큐의 시작과 끝 위치를 추적.

typedef struct {
    int *data;    // 큐 데이터 저장을 위한 배열
    int front;    // 큐의 앞쪽 인덱스
    int rear;     // 큐의 뒤쪽 인덱스
    int size;     // 큐의 최대 크기
} Queue;

초기화 함수

큐를 사용하기 전에 배열을 동적 할당하고, 초기 상태를 설정해야 합니다.

Queue* initQueue(int size) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (int*)malloc(sizeof(int) * size);
    q->front = -1;
    q->rear = -1;
    q->size = size;
    return q;
}

큐 연산 구현

삽입 연산(Enqueue)
새로운 데이터를 Rear 위치에 추가합니다. 큐가 가득 차 있는 경우 오류를 처리합니다.

int enqueue(Queue* q, int value) {
    if ((q->rear + 1) % q->size == q->front) {
        return -1;  // 큐가 가득 참
    }
    if (q->front == -1) q->front = 0;  // 첫 삽입 시 front 설정
    q->rear = (q->rear + 1) % q->size;
    q->data[q->rear] = value;
    return 0;
}

삭제 연산(Dequeue)
Front 위치의 데이터를 제거하고, 다음 데이터를 Front로 설정합니다. 큐가 비어 있으면 오류를 처리합니다.

int dequeue(Queue* q, int* value) {
    if (q->front == -1) {
        return -1;  // 큐가 비어 있음
    }
    *value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;  // 큐가 비게 됨
    } else {
        q->front = (q->front + 1) % q->size;
    }
    return 0;
}

큐 상태 확인

큐가 비어 있는지 확인

int isEmpty(Queue* q) {
    return q->front == -1;
}

큐가 가득 찼는지 확인

int isFull(Queue* q) {
    return (q->rear + 1) % q->size == q->front;
}

요약

배열 기반 큐는 구현이 단순하며, 고정 크기의 데이터를 효율적으로 관리할 수 있습니다. 하지만 고정된 크기 때문에 메모리 낭비가 발생할 수 있고, 크기를 초과하면 동적 확장이 어렵습니다. 이후 섹션에서 이러한 문제를 해결하기 위한 대안인 링 버퍼와 연결 리스트 기반 큐를 다룹니다.

링 버퍼를 활용한 큐 확장

배열 기반 큐는 고정된 크기로 인해 메모리 낭비와 오버플로 문제가 발생할 수 있습니다. 이를 해결하기 위해 링 버퍼(Circular Buffer) 를 활용하면 메모리를 효율적으로 사용할 수 있습니다. 링 버퍼는 큐의 Rear가 마지막 위치에 도달하면 다시 처음으로 순환하며, 메모리를 재활용합니다.

링 버퍼 큐의 구조

링 버퍼 큐는 배열 기반 큐와 동일한 구조를 가지지만, Rear와 Front가 순환한다는 점에서 차이가 있습니다.

Rear 포인터: 데이터를 삽입할 위치를 가리킴.
Front 포인터: 데이터를 삭제할 위치를 가리킴.
빈 공간 확인: 큐가 비었거나 가득 찼는지를 Front와 Rear 포인터의 위치로 판단.

링 버퍼 큐 구현

큐 초기화

Queue* initQueue(int size) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (int*)malloc(sizeof(int) * size);
    q->front = -1;
    q->rear = -1;
    q->size = size;
    return q;
}

삽입 연산(Enqueue)
Rear가 배열 끝에 도달하면 0으로 돌아갑니다.

int enqueue(Queue* q, int value) {
    if ((q->rear + 1) % q->size == q->front) {
        return -1;  // 큐가 가득 참
    }
    if (q->front == -1) q->front = 0;  // 첫 삽입 시 초기화
    q->rear = (q->rear + 1) % q->size;
    q->data[q->rear] = value;
    return 0;
}

삭제 연산(Dequeue)
Front가 배열 끝에 도달하면 0으로 돌아갑니다.

int dequeue(Queue* q, int* value) {
    if (q->front == -1) {
        return -1;  // 큐가 비어 있음
    }
    *value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;  // 큐가 비게 됨
    } else {
        q->front = (q->front + 1) % q->size;
    }
    return 0;
}

큐가 비어 있는지 확인

int isEmpty(Queue* q) {
    return q->front == -1;
}

큐가 가득 찼는지 확인

int isFull(Queue* q) {
    return (q->rear + 1) % q->size == q->front;
}

링 버퍼의 장점

효율적인 메모리 사용: Front와 Rear가 순환하여 고정된 배열 크기 내에서 메모리를 재활용합니다.
상수 시간 연산: 삽입과 삭제 연산은 모두 O(1) 시간에 수행됩니다.
단순한 구현: 복잡한 동적 메모리 관리를 필요로 하지 않습니다.

사용 시 주의점

큐가 가득 찬 상태와 비어 있는 상태를 Front와 Rear의 관계로 정확히 구분해야 합니다.
큐의 크기를 넘는 삽입 시도는 반드시 차단해야 합니다.

응용 사례

링 버퍼는 실시간 시스템이나 네트워크 버퍼링, 오디오 데이터 처리 등에서 자주 사용됩니다. 특히 제한된 메모리 환경에서 안정적인 데이터 관리가 요구될 때 적합한 선택입니다.

링 버퍼 큐는 배열 기반 큐의 단점을 보완하며, 메모리를 효율적으로 사용하는 실용적인 대안입니다. 연결 리스트 기반 큐와 비교했을 때, 메모리 할당 및 해제 비용이 없다는 점도 중요한 장점입니다.

연결 리스트를 사용한 동적 큐 구현

배열 기반 큐와 링 버퍼는 고정된 크기로 인해 메모리 낭비 또는 크기 제한이 발생할 수 있습니다. 이를 해결하기 위해 연결 리스트(Linked List) 를 사용하면 큐의 크기를 동적으로 조정할 수 있습니다. 연결 리스트 기반 큐는 메모리 활용이 유연하며, 큐의 크기에 제한이 없습니다.

연결 리스트 기반 큐의 구조

연결 리스트 기반 큐는 다음과 같은 구성 요소로 이루어집니다.

노드(Node): 데이터를 저장하고 다음 노드를 가리키는 구조체.
Front 포인터: 큐의 앞쪽 노드를 가리킴.
Rear 포인터: 큐의 마지막 노드를 가리킴.

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;  // 큐의 앞쪽
    Node* rear;   // 큐의 뒤쪽
} Queue;

큐 초기화

큐를 초기화할 때 Front와 Rear 포인터를 NULL로 설정합니다.

Queue* initQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

삽입 연산(Enqueue)

새로운 노드를 생성하여 Rear에 추가합니다.

void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {  // 큐가 비어 있는 경우
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

삭제 연산(Dequeue)

Front에 있는 노드를 제거하고, 다음 노드를 Front로 설정합니다.

int dequeue(Queue* q, int* value) {
    if (q->front == NULL) {  // 큐가 비어 있음
        return -1;
    }
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {  // 큐가 비게 되면 Rear도 NULL로 설정
        q->rear = NULL;
    }
    free(temp);
    return 0;
}

큐 상태 확인

큐가 비어 있는지 확인

int isEmpty(Queue* q) {
    return q->front == NULL;
}

연결 리스트 기반 큐의 장점

크기 제한 없음: 배열 기반 큐와 달리 크기를 동적으로 확장할 수 있습니다.
효율적 메모리 사용: 필요한 만큼만 메모리를 할당하므로 공간 낭비가 없습니다.
삽입 및 삭제 효율성: O(1) 시간에 삽입과 삭제가 가능합니다.

연결 리스트 기반 큐의 단점

메모리 관리 부담: 노드마다 메모리를 동적으로 할당하고 해제해야 하므로 관리가 복잡합니다.
추가 메모리 사용: 각 노드에 데이터와 함께 포인터를 저장하기 때문에 약간의 추가 메모리가 필요합니다.

응용 사례

연결 리스트 기반 큐는 크기 제한이 없는 데이터 처리가 필요한 곳에서 유용합니다. 예를 들어, 네트워크 데이터 패킷 처리, 동적 작업 스케줄링 등 다양한 상황에서 활용할 수 있습니다.

연결 리스트 기반 큐는 배열 기반 큐와 링 버퍼의 한계를 극복하며, 유연한 자료구조 설계에 중요한 역할을 합니다. 이를 통해 실시간 시스템이나 복잡한 데이터 흐름을 처리할 수 있는 강력한 도구를 제공할 수 있습니다.

큐의 주요 연산 구현

큐의 기본 연산은 삽입(Enqueue), 삭제(Dequeue), 확인(Peek)입니다. 이러한 연산은 큐의 작동 원리를 이해하고 실제로 활용하기 위해 반드시 구현해야 합니다. 아래에서는 배열 기반 큐와 연결 리스트 기반 큐의 연산 구현 방법을 모두 다룹니다.

배열 기반 큐 연산

삽입(Enqueue)
큐의 Rear 위치에 데이터를 추가하며, 가득 찬 상태를 처리합니다.

int enqueue(Queue* q, int value) {
    if ((q->rear + 1) % q->size == q->front) {
        return -1;  // 큐가 가득 참
    }
    if (q->front == -1) q->front = 0;  // 큐가 비어 있는 경우 초기화
    q->rear = (q->rear + 1) % q->size;
    q->data[q->rear] = value;
    return 0;  // 성공
}

삭제(Dequeue)
큐의 Front 위치에서 데이터를 제거하며, 비어 있는 상태를 처리합니다.

int dequeue(Queue* q, int* value) {
    if (q->front == -1) {
        return -1;  // 큐가 비어 있음
    }
    *value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;  // 큐가 비게 됨
    } else {
        q->front = (q->front + 1) % q->size;
    }
    return 0;  // 성공
}

확인(Peek)
Front 위치의 데이터를 확인합니다.

int peek(Queue* q, int* value) {
    if (q->front == -1) {
        return -1;  // 큐가 비어 있음
    }
    *value = q->data[q->front];
    return 0;  // 성공
}

연결 리스트 기반 큐 연산

삽입(Enqueue)
Rear 노드에 새로운 노드를 추가합니다.

void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {  // 큐가 비어 있는 경우
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

삭제(Dequeue)
Front 노드를 제거하고, 다음 노드를 Front로 설정합니다.

int dequeue(Queue* q, int* value) {
    if (q->front == NULL) {  // 큐가 비어 있음
        return -1;
    }
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {  // 큐가 비게 되면 Rear도 NULL로 설정
        q->rear = NULL;
    }
    free(temp);
    return 0;
}

확인(Peek)
Front 노드의 데이터를 확인합니다.

int peek(Queue* q, int* value) {
    if (q->front == NULL) {
        return -1;  // 큐가 비어 있음
    }
    *value = q->front->data;
    return 0;
}

큐 상태 확인 연산

비어 있는지 확인

int isEmpty(Queue* q) {
    return q->front == NULL;
}

가득 찼는지 확인(배열 기반 큐)

int isFull(Queue* q) {
    return (q->rear + 1) % q->size == q->front;
}

큐 연산 테스트

큐 연산이 올바르게 작동하는지 확인하기 위해 아래와 같은 테스트 코드를 사용할 수 있습니다.

int main() {
    Queue* q = initQueue(5);

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);

    int value;
    dequeue(q, &value);
    printf("Dequeued: %d\n", value);  // 출력: 10

    peek(q, &value);
    printf("Front: %d\n", value);  // 출력: 20

    return 0;
}

요약

큐의 주요 연산은 데이터를 삽입, 삭제, 확인하며, 각각의 상태를 처리하는 방법을 포함합니다. 배열 기반 큐와 연결 리스트 기반 큐 모두 고유한 장점과 단점을 가지고 있으며, 구현 목적에 따라 적절한 방식을 선택할 수 있습니다. 이러한 연산을 바탕으로 큐를 다양한 응용 사례에 활용할 수 있습니다.

큐의 예외 처리 및 경계 조건

큐를 구현할 때, 예외 상황과 경계 조건을 처리하는 것은 안정적이고 신뢰할 수 있는 프로그램을 만드는 데 필수적입니다. 큐가 비었거나 가득 찼을 때의 처리는 모든 큐 구현에서 중요한 요소입니다. 이 섹션에서는 배열 기반 큐와 연결 리스트 기반 큐에서의 예외 처리 방법을 다룹니다.

배열 기반 큐의 예외 처리

큐가 비었을 때(Underflow)
큐가 비었을 때 데이터를 제거하거나 확인하려고 하면 오류를 반환합니다.

int dequeue(Queue* q, int* value) {
    if (q->front == -1) {  // 큐가 비어 있음
        printf("Error: Queue underflow.\n");
        return -1;
    }
    *value = q->data[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;  // 큐가 비게 됨
    } else {
        q->front = (q->front + 1) % q->size;
    }
    return 0;
}

큐가 가득 찼을 때(Overflow)
큐가 가득 찼을 때 데이터를 삽입하려고 하면 오류를 반환합니다.

int enqueue(Queue* q, int value) {
    if ((q->rear + 1) % q->size == q->front) {
        printf("Error: Queue overflow.\n");
        return -1;
    }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % q->size;
    q->data[q->rear] = value;
    return 0;
}

연결 리스트 기반 큐의 예외 처리

큐가 비었을 때(Underflow)
연결 리스트 기반 큐에서는 Front 포인터가 NULL인 경우 큐가 비어 있음을 나타냅니다.

int dequeue(Queue* q, int* value) {
    if (q->front == NULL) {  // 큐가 비어 있음
        printf("Error: Queue underflow.\n");
        return -1;
    }
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;  // 큐가 비게 됨
    free(temp);
    return 0;
}

메모리 할당 실패
새 노드를 생성할 때 동적 메모리 할당이 실패하면 오류를 처리합니다.

void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {  // 메모리 할당 실패
        printf("Error: Memory allocation failed.\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

경계 조건 처리

빈 큐 확인
큐가 비어 있는 상태인지 확인합니다.

int isEmpty(Queue* q) {
    return (q->front == -1 || q->front == NULL);
}

가득 찬 큐 확인(배열 기반 큐)
배열 기반 큐에서는 Rear와 Front 포인터의 위치를 비교하여 가득 찬 상태를 확인합니다.

int isFull(Queue* q) {
    return (q->rear + 1) % q->size == q->front;
}

일반적인 예외 처리 전략

에러 메시지 출력: 사용자에게 현재 상태를 알립니다.
상태 반환값 활용: 연산 성공 여부를 호출한 함수에 반환합니다.
복구 가능 상태 유지: 예외 상황 발생 시 큐가 손상되지 않도록 일관성을 유지합니다.

테스트 코드

int main() {
    Queue* q = initQueue(3);

    // Overflow 처리 테스트
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    if (enqueue(q, 40) == -1) {
        printf("Queue is full.\n");
    }

    // Underflow 처리 테스트
    int value;
    dequeue(q, &value);
    dequeue(q, &value);
    dequeue(q, &value);
    if (dequeue(q, &value) == -1) {
        printf("Queue is empty.\n");
    }

    return 0;
}

요약

큐의 예외 처리 및 경계 조건은 데이터 손실과 프로그램 오류를 방지하기 위해 필수적입니다. 배열 기반 큐와 연결 리스트 기반 큐는 각각의 구현 방식에 따라 다른 예외 처리 방법을 요구하지만, 기본 원칙은 큐의 상태를 항상 일관되게 유지하는 것입니다. 이를 통해 안정적이고 신뢰할 수 있는 큐 구현이 가능합니다.

응용 예제: 프린터 작업 관리 시스템

큐는 여러 작업을 순차적으로 처리해야 하는 시스템에서 특히 유용합니다. 프린터 작업 관리 시스템은 이를 설명하기 좋은 사례입니다. 프린터는 동시에 여러 작업을 처리할 수 없으므로, 작업 요청은 FIFO 방식으로 대기열에 저장되며, 순서대로 처리됩니다.

이 섹션에서는 큐를 활용해 간단한 프린터 작업 관리 시스템을 구현하는 방법을 소개합니다.

문제 정의

프린터는 여러 사용자가 보낸 작업을 처리해야 합니다. 각 작업은 다음 정보를 포함합니다.

작업 ID: 고유 작업 식별자.
페이지 수: 각 작업의 출력 페이지 수.
우선순위: 높은 우선순위의 작업이 먼저 처리됩니다(선택적).

큐를 사용해 작업을 순차적으로 저장하고 처리하며, 작업 완료 후 큐에서 제거합니다.

구조 설계

작업 구조체
각 작업의 정보를 저장하는 구조체를 정의합니다.

typedef struct {
    int jobId;
    int pageCount;
} PrintJob;

큐 구조체
프린터 작업 대기열을 관리하기 위한 큐를 정의합니다.

typedef struct {
    PrintJob* data;  // 작업 데이터 배열
    int front;       // 대기열의 앞쪽
    int rear;        // 대기열의 뒤쪽
    int size;        // 큐의 크기
    int capacity;    // 큐의 최대 용량
} Queue;

프린터 큐 구현

큐 초기화
큐를 초기화하는 함수입니다.

Queue* initQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (PrintJob*)malloc(sizeof(PrintJob) * capacity);
    q->front = -1;
    q->rear = -1;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

작업 추가(Enqueue)
작업을 큐에 추가합니다.

int enqueue(Queue* q, int jobId, int pageCount) {
    if (q->size == q->capacity) {
        printf("Queue is full. Cannot add job %d.\n", jobId);
        return -1;
    }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % q->capacity;
    q->data[q->rear].jobId = jobId;
    q->data[q->rear].pageCount = pageCount;
    q->size++;
    printf("Added job %d with %d pages.\n", jobId, pageCount);
    return 0;
}

작업 처리(Dequeue)
작업을 처리하고 대기열에서 제거합니다.

int dequeue(Queue* q) {
    if (q->size == 0) {
        printf("Queue is empty. No jobs to process.\n");
        return -1;
    }
    PrintJob job = q->data[q->front];
    printf("Processing job %d with %d pages.\n", job.jobId, job.pageCount);
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return 0;
}

현재 대기열 상태 확인
현재 대기 중인 작업을 출력합니다.

void printQueue(Queue* q) {
    if (q->size == 0) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Current print queue:\n");
    for (int i = 0; i < q->size; i++) {
        int index = (q->front + i) % q->capacity;
        printf("Job ID: %d, Pages: %d\n", q->data[index].jobId, q->data[index].pageCount);
    }
}

테스트 코드

int main() {
    Queue* printerQueue = initQueue(5);

    enqueue(printerQueue, 101, 10);
    enqueue(printerQueue, 102, 5);
    enqueue(printerQueue, 103, 15);

    printQueue(printerQueue);

    dequeue(printerQueue);
    dequeue(printerQueue);

    printQueue(printerQueue);

    return 0;
}

실행 결과

Added job 101 with 10 pages.
Added job 102 with 5 pages.
Added job 103 with 15 pages.
Current print queue:
Job ID: 101, Pages: 10
Job ID: 102, Pages: 5
Job ID: 103, Pages: 15
Processing job 101 with 10 pages.
Processing job 102 with 5 pages.
Current print queue:
Job ID: 103, Pages: 15

요약

큐를 활용한 프린터 작업 관리 시스템은 FIFO 방식을 기반으로 하여 간단하고 효과적인 대기열 관리를 제공합니다. 이 예제를 통해 큐의 실제 응용 사례를 이해하고, 다양한 시스템에서 큐를 적용할 수 있는 방법을 배울 수 있습니다.

큐 구현을 위한 연습 문제

큐의 원리를 이해하고, 구현 능력을 강화하기 위해 다양한 연습 문제를 풀어보는 것이 중요합니다. 아래는 배열 기반 큐와 연결 리스트 기반 큐를 다루는 연습 문제와 힌트를 제공합니다.

문제 1: 고정 크기 큐의 크기 조정

배열 기반 큐에서 초기 크기를 초과하는 경우, 동적으로 크기를 두 배로 늘리는 기능을 추가하세요.

힌트:

기존 배열의 데이터를 새로운 배열로 복사합니다.
Rear와 Front 포인터의 위치를 조정하여 순환 구조를 유지합니다.

코드 초안:

void resizeQueue(Queue* q) {
    int newCapacity = q->capacity * 2;
    int* newData = (int*)malloc(sizeof(int) * newCapacity);

    // 기존 데이터를 새로운 배열로 복사
    for (int i = 0; i < q->size; i++) {
        newData[i] = q->data[(q->front + i) % q->capacity];
    }

    free(q->data);
    q->data = newData;
    q->capacity = newCapacity;
    q->front = 0;
    q->rear = q->size - 1;
}

문제 2: 우선순위 큐 구현

큐에 저장되는 작업에 우선순위를 부여하고, 높은 우선순위의 작업이 먼저 처리되도록 구현하세요.

힌트:

각 작업에 우선순위 필드를 추가합니다.
Enqueue 시 우선순위를 비교하여 올바른 위치에 삽입합니다.

코드 초안:

typedef struct {
    int jobId;
    int priority;
} PriorityJob;

void enqueueWithPriority(PriorityQueue* q, int jobId, int priority) {
    if (q->size == q->capacity) {
        printf("Queue is full.\n");
        return;
    }
    int i;
    for (i = q->size - 1; i >= 0; i--) {
        if (q->data[i].priority >= priority) {
            q->data[i + 1] = q->data[i];
        } else {
            break;
        }
    }
    q->data[i + 1].jobId = jobId;
    q->data[i + 1].priority = priority;
    q->size++;
}

문제 3: 이중 끝 큐(Deque) 구현

큐의 양쪽 끝에서 삽입과 삭제가 가능한 이중 끝 큐를 구현하세요.

힌트:

Front에서의 삽입과 삭제 연산을 추가합니다.
Rear에서의 삽입과 삭제는 기존 방식과 동일하게 처리합니다.

문제 4: 링 버퍼와 연결 리스트 비교

배열 기반의 링 버퍼와 연결 리스트 기반 큐의 성능을 비교하는 프로그램을 작성하세요.

목표:

큐에 10,000개의 작업을 삽입하고 제거하는 시간을 측정하세요.
배열 기반 큐와 연결 리스트 큐의 메모리 사용량을 비교하세요.

문제 5: 회전 작업 큐 구현

작업이 완료되지 않으면 큐의 뒤로 다시 삽입되는 회전 작업 큐를 구현하세요.

설명:

작업은 한 번의 처리로 완료되지 않을 수 있습니다.
작업이 완료되지 않으면 dequeue 후 다시 enqueue 합니다.

문제 6: 큐를 활용한 BFS 구현

그래프 탐색 알고리즘인 BFS(Breadth-First Search)를 큐를 사용해 구현하세요.

힌트:

큐에 그래프의 노드를 저장합니다.
큐에서 노드를 꺼내 방문하며, 연결된 노드를 다시 큐에 추가합니다.

문제 7: 문자열 회문 검사

큐와 스택을 사용해 주어진 문자열이 회문인지 확인하는 프로그램을 작성하세요.

설명:

큐는 문자열의 순서를 유지합니다.
스택은 문자열의 역순을 저장합니다.
두 데이터를 비교해 일치 여부를 확인합니다.

문제 8: 실시간 데이터 스트림 처리

큐를 사용하여 실시간으로 들어오는 데이터 스트림에서 최근 N개의 데이터를 저장하고, 평균을 계산하세요.

힌트:

고정 크기의 링 버퍼를 사용합니다.
데이터 삽입 시 오래된 데이터를 제거합니다.

문제 9: 스케줄러 시뮬레이터 구현

큐를 활용해 운영 체제의 라운드 로빈 스케줄러를 시뮬레이션하세요.

설명:

각 프로세스는 실행 시간을 가집니다.
큐에 프로세스를 삽입하고, 일정 시간(TIME SLICE) 동안 실행 후 다시 큐에 삽입합니다.

문제 10: 다중 큐 시스템 구현

하나의 시스템에서 서로 다른 우선순위를 가진 여러 큐를 관리하는 다중 큐 시스템을 구현하세요.

설명:

각 큐는 고유한 우선순위를 가집니다.
높은 우선순위 큐가 먼저 처리되며, 같은 우선순위의 작업은 FIFO로 처리됩니다.

요약

위 연습 문제들은 큐의 기본 동작 원리뿐만 아니라, 다양한 응용 시나리오에서 큐를 활용하는 방법을 익힐 수 있도록 구성되었습니다. 이를 통해 자료구조와 알고리즘에 대한 깊은 이해를 얻을 수 있습니다.

요약

본 기사에서는 큐 자료구조의 기초부터 구현, 그리고 다양한 응용과 연습 문제를 다뤘습니다.
큐의 정의와 특성을 이해하고, 배열 기반, 링 버퍼 기반, 연결 리스트 기반 큐의 구현 방법을 학습했습니다. 또한, 프린터 작업 관리 시스템과 같은 실전 사례를 통해 큐의 활용 가능성을 확인했으며, 추가적인 연습 문제를 통해 큐의 개념을 강화할 수 있는 기회를 제공했습니다.

큐는 단순하면서도 강력한 자료구조로, 소프트웨어 개발의 다양한 분야에서 활용됩니다. 이를 통해 더욱 효율적이고 안정적인 프로그램을 설계할 수 있을 것입니다.