C언어에서 배열을 활용한 큐 구현과 사용법

큐는 FIFO(First In, First Out) 구조를 따르는 데이터 구조로, 데이터가 삽입된 순서대로 처리됩니다. 본 기사에서는 큐의 기본 개념을 시작으로, 배열을 활용한 큐 구현 방법, 순환 큐를 포함한 개선된 구현, 그리고 이를 활용한 응용 예제까지 자세히 다룹니다. 이를 통해 C언어를 사용해 큐를 효과적으로 구현하고 활용하는 방법을 이해할 수 있습니다.

큐란 무엇인가

큐는 데이터를 삽입한 순서대로 처리하는 FIFO(First In, First Out) 방식의 데이터 구조입니다. 이는 데이터를 처음 들어온 순서대로 처리해야 하는 작업에서 유용하게 사용됩니다.

큐의 기본 특성

삽입(Enqueue): 데이터를 큐의 끝에 추가하는 연산입니다.
삭제(Dequeue): 큐의 앞에서 데이터를 제거하는 연산입니다.
순서 유지: 데이터가 삽입된 순서대로 처리됩니다.

큐와 스택의 차이

큐는 FIFO 방식을 따르는 반면, 스택은 LIFO(Last In, First Out) 방식을 따릅니다. 즉, 큐는 먼저 들어온 데이터가 먼저 나가는 반면, 스택은 마지막에 들어온 데이터가 먼저 나갑니다.

큐의 실생활 예시

대기열: 은행의 고객 대기열처럼, 먼저 온 사람이 먼저 처리됩니다.
프린터 작업 큐: 문서가 요청된 순서대로 출력됩니다.

큐는 이러한 특성 덕분에 다양한 알고리즘과 시스템에서 필수적인 데이터 구조로 사용됩니다.

배열을 활용한 큐 구현의 기본 구조

큐를 배열로 구현하면 고정된 크기의 연속된 메모리 공간을 활용해 데이터를 저장하고 관리할 수 있습니다. 배열 기반 큐는 간단하면서도 큐의 기본 연산을 학습하는 데 적합합니다.

배열 기반 큐의 구성 요소

배열(Array): 데이터를 저장하는 고정 크기의 배열입니다.
프론트(Front): 큐의 가장 앞쪽 요소를 가리키는 인덱스입니다.
리어(Rear): 큐의 가장 뒤쪽 요소를 가리키는 인덱스입니다.
크기(Size): 배열의 크기를 나타내며, 큐의 용량을 제한합니다.

초기화

큐를 초기화하기 위해 다음과 같은 단계를 수행합니다.

배열 생성: 큐 데이터를 저장할 고정된 크기의 배열을 생성합니다.
프론트와 리어 초기화: 일반적으로 -1로 설정해 큐가 비어 있음을 나타냅니다.
큐 크기 정의: 배열의 최대 크기를 설정합니다.

작동 원리

데이터 삽입 시, 리어 인덱스를 증가시키며 데이터를 추가합니다.
데이터 삭제 시, 프론트 인덱스를 증가시키며 데이터를 제거합니다.
배열이 가득 차거나 비었을 때, 오류 처리를 통해 큐의 상태를 관리합니다.

배열 기반 큐의 초기 코드 구조

#include <stdio.h>
#define MAX 100

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

이 기본 구조를 활용해 큐의 삽입, 삭제 및 상태 점검 연산을 구현할 수 있습니다.

큐 연산: 삽입(Enqueue)

큐의 삽입 연산(Enqueue)은 새로운 데이터를 큐의 뒤쪽(Rear)에 추가하는 작업입니다. 배열 기반 큐에서는 리어(Rear) 인덱스를 조작해 데이터를 추가합니다.

삽입 과정

오버플로우 검사

리어(Rear)가 배열의 마지막 인덱스를 초과하면 큐가 가득 찬 상태로 간주됩니다.
오버플로우 상태에서는 삽입 연산을 수행할 수 없습니다.

첫 삽입 처리

큐가 비어 있다면, 프론트(Front)와 리어(Rear)를 동시에 0으로 설정합니다.

리어 인덱스 증가 및 데이터 추가

리어(Rear)를 1 증가시킨 후, 해당 위치에 데이터를 저장합니다.

삽입 연산의 구현

#include <stdio.h>
#define MAX 100

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Queue;

// 삽입(Enqueue) 함수
void enqueue(Queue* q, int data) {
    if (q->rear == MAX - 1) {
        printf("Queue Overflow! 삽입할 수 없습니다.\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0; // 큐가 비어있을 경우 프론트 초기화
    }
    q->rear++;
    q->arr[q->rear] = data;
    printf("삽입된 데이터: %d\n", data);
}

삽입 시 고려 사항

큐가 가득 찼을 경우 오버플로우를 방지하는 오류 처리가 필요합니다.
첫 데이터 삽입 시 프론트와 리어의 동시 초기화가 필수입니다.

삽입 연산 예제

다음 코드는 큐에 3개의 숫자를 삽입하는 과정을 보여줍니다.

int main() {
    Queue q;
    initQueue(&q);

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

    return 0;
}

결과 출력

삽입된 데이터: 10  
삽입된 데이터: 20  
삽입된 데이터: 30

삽입 연산을 통해 큐의 끝부분에 데이터를 차례대로 추가할 수 있습니다.

큐 연산: 삭제(Dequeue)

큐의 삭제 연산(Dequeue)은 큐의 앞쪽(Front)에서 데이터를 제거하는 작업입니다. 배열 기반 큐에서는 프론트(Front) 인덱스를 조작해 데이터를 제거하며, 삭제된 데이터를 반환하거나 단순히 제거합니다.

삭제 과정

언더플로우 검사

프론트(Front)가 -1이거나 프론트가 리어(Rear)를 초과하면 큐가 비어 있는 상태로 간주됩니다.
언더플로우 상태에서는 삭제 연산을 수행할 수 없습니다.

데이터 제거 및 프론트 인덱스 이동

프론트 위치의 데이터를 제거한 후, 프론트를 1 증가시킵니다.

큐가 비어 있는 상태 처리

마지막 데이터를 제거한 후, 프론트와 리어를 -1로 초기화해 큐가 비어 있음을 표시합니다.

삭제 연산의 구현

#include <stdio.h>
#define MAX 100

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Queue;

// 삭제(Dequeue) 함수
int dequeue(Queue* q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow! 삭제할 수 없습니다.\n");
        return -1;
    }
    int data = q->arr[q->front];
    q->front++;
    // 큐가 비어 있으면 프론트와 리어를 초기화
    if (q->front > q->rear) {
        q->front = -1;
        q->rear = -1;
    }
    printf("삭제된 데이터: %d\n", data);
    return data;
}

삭제 시 고려 사항

큐가 비어 있는 상태에서의 언더플로우 방지가 필요합니다.
마지막 데이터를 제거했을 때 큐를 초기화해야 합니다.

삭제 연산 예제

다음 코드는 큐에서 데이터를 삭제하는 과정을 보여줍니다.

int main() {
    Queue q;
    initQueue(&q);

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

    dequeue(&q);
    dequeue(&q);
    dequeue(&q);

    return 0;
}

결과 출력

삽입된 데이터: 10  
삽입된 데이터: 20  
삽입된 데이터: 30  
삭제된 데이터: 10  
삭제된 데이터: 20  
삭제된 데이터: 30

삭제 연산을 통해 큐의 앞부분에서 데이터를 차례로 제거할 수 있습니다.

배열 기반 큐의 한계와 해결 방법

배열을 사용한 큐 구현은 간단하고 이해하기 쉽지만, 몇 가지 한계가 존재합니다. 이러한 한계는 효율적인 사용과 확장을 어렵게 만들 수 있으며, 이를 해결하기 위해 개선된 구조가 필요합니다.

배열 기반 큐의 주요 한계

고정 크기 제한

배열의 크기가 고정되어 있으므로, 큐가 가득 차면 더 이상 데이터를 삽입할 수 없습니다.
크기를 초과하는 데이터를 처리하려면 배열 크기를 동적으로 재조정해야 하지만, 이는 비효율적입니다.

공간 낭비

데이터를 삭제하면 프론트 인덱스가 증가하면서 배열의 앞부분이 비어 있습니다.
그러나 리어 인덱스는 여전히 배열 끝으로 이동하므로, 비어 있는 공간을 재사용할 수 없습니다.

큐 초기화 필요성

마지막 데이터를 삭제한 후에도 배열의 메모리는 유지되므로, 메모리 초기화 작업이 필요합니다.

한계 해결 방안: 순환 큐(Circular Queue)

순환 큐는 배열의 고정된 크기를 유지하면서도 공간 낭비 문제를 해결하기 위한 구조입니다.

작동 원리

큐의 끝(Rear)이 배열의 끝에 도달하면, 큐는 배열의 시작으로 “순환”합니다.
프론트와 리어 인덱스는 배열의 크기를 초과하지 않고 순환 구조로 유지됩니다.

장점

배열의 모든 공간을 활용할 수 있어 효율적입니다.
고정된 메모리를 사용하므로 동적 메모리 할당에 따른 오버헤드가 없습니다.

구현 방법

배열 크기(MAX)를 기준으로 모듈로 연산(% MAX)을 사용하여 순환을 구현합니다.

순환 큐의 기본 연산

void enqueueCircular(Queue* q, int data) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue Overflow! 삽입할 수 없습니다.\n");
        return;
    }
    if (q->front == -1) { 
        q->front = 0; // 큐가 비어있을 경우 초기화
    }
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = data;
    printf("삽입된 데이터: %d\n", data);
}

int dequeueCircular(Queue* q) {
    if (q->front == -1) {
        printf("Queue Underflow! 삭제할 수 없습니다.\n");
        return -1;
    }
    int data = q->arr[q->front];
    if (q->front == q->rear) {
        q->front = -1; // 큐가 비어있음을 나타냄
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    printf("삭제된 데이터: %d\n", data);
    return data;
}

결론

배열 기반 큐는 간단하지만 고정 크기와 공간 낭비라는 한계를 가집니다. 순환 큐를 도입하면 이러한 문제를 해결할 수 있으며, 배열 기반의 효율적인 큐 구현이 가능합니다. 이를 통해 더 큰 유연성과 활용성을 제공할 수 있습니다.

순환 큐의 구현 방법

순환 큐(Circular Queue)는 배열 기반 큐의 공간 낭비 문제를 해결하기 위해 배열을 원형으로 연결하여 설계된 데이터 구조입니다. 이를 통해 고정된 배열 크기 내에서 메모리를 효율적으로 활용할 수 있습니다.

순환 큐의 기본 원리

순환 구조: 배열의 끝에서 새로운 데이터를 삽입하거나 삭제할 때, 배열의 시작으로 되돌아옵니다.
모듈로 연산 사용: 인덱스를 조정할 때 배열 크기로 나눈 나머지 연산(%)을 사용해 순환 효과를 만듭니다.
공간 최적화: 삭제된 요소로 인해 비는 공간도 다시 사용할 수 있습니다.

순환 큐 구현 코드

#include <stdio.h>
#define MAX 5

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} CircularQueue;

// 순환 큐 초기화
void initCircularQueue(CircularQueue* q) {
    q->front = -1;
    q->rear = -1;
}

// 순환 큐 삽입 연산(Enqueue)
void enqueue(CircularQueue* q, int data) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue Overflow! 삽입할 수 없습니다.\n");
        return;
    }
    if (q->front == -1) { 
        q->front = 0; // 큐가 비어있으면 초기화
    }
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = data;
    printf("삽입된 데이터: %d\n", data);
}

// 순환 큐 삭제 연산(Dequeue)
int dequeue(CircularQueue* q) {
    if (q->front == -1) {
        printf("Queue Underflow! 삭제할 수 없습니다.\n");
        return -1;
    }
    int data = q->arr[q->front];
    if (q->front == q->rear) {
        q->front = -1; // 큐가 비었음을 표시
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    printf("삭제된 데이터: %d\n", data);
    return data;
}

// 큐 상태 출력
void displayQueue(CircularQueue* q) {
    if (q->front == -1) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (1) {
        printf("%d ", q->arr[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

순환 큐 예제 실행

int main() {
    CircularQueue q;
    initCircularQueue(&q);

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

    displayQueue(&q);

    dequeue(&q);
    dequeue(&q);

    displayQueue(&q);

    enqueue(&q, 50);
    enqueue(&q, 60);

    displayQueue(&q);

    return 0;
}

결과 출력

삽입된 데이터: 10  
삽입된 데이터: 20  
삽입된 데이터: 30  
삽입된 데이터: 40  
Queue elements: 10 20 30 40  
삭제된 데이터: 10  
삭제된 데이터: 20  
Queue elements: 30 40  
삽입된 데이터: 50  
삽입된 데이터: 60  
Queue elements: 30 40 50 60

순환 큐의 장점

고정된 크기의 배열을 사용하면서도 모든 공간을 활용할 수 있습니다.
연속적인 데이터 삽입과 삭제 연산이 가능하며, 메모리 낭비를 최소화합니다.

순환 큐는 배열 기반 큐의 단점을 해결하며, 메모리 효율성을 극대화할 수 있는 실용적인 구현 방법입니다.

배열 기반 큐를 활용한 응용 예시

큐는 데이터가 순서대로 처리되어야 하는 다양한 실제 문제에 유용하게 사용됩니다. 배열 기반 큐를 활용하면 효율적으로 문제를 해결할 수 있습니다. 아래는 큐의 주요 응용 예시를 소개합니다.

응용 예시 1: 프로세스 스케줄링

운영체제에서 프로세스 스케줄링은 여러 프로세스가 CPU를 공평하게 사용할 수 있도록 관리하는 핵심 개념입니다. 큐는 프로세스 순서를 관리하는 데 사용됩니다.

작동 방식

프로세스가 준비 상태가 되면 큐에 삽입(Enqueue)됩니다.
CPU가 프로세스를 처리할 준비가 되면 큐의 앞에서 프로세스를 삭제(Dequeue)합니다.
시간이 초과되거나 작업이 완료되지 않으면 다시 큐에 삽입하여 순환합니다.

코드 예제

#include <stdio.h>
#define MAX 5

typedef struct {
    int pid; // 프로세스 ID
    int burstTime; // 실행 시간
} Process;

typedef struct {
    Process arr[MAX];
    int front;
    int rear;
} Queue;

void enqueueProcess(Queue* q, Process p) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue Overflow! 프로세스를 추가할 수 없습니다.\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = p;
}

Process dequeueProcess(Queue* q) {
    if (q->front == -1) {
        printf("Queue Underflow! 프로세스가 없습니다.\n");
        Process empty = {-1, 0};
        return empty;
    }
    Process p = q->arr[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return p;
}

void simulateProcessQueue() {
    Queue q = {{0}, -1, -1};
    Process p1 = {1, 5};
    Process p2 = {2, 3};
    Process p3 = {3, 7};

    enqueueProcess(&q, p1);
    enqueueProcess(&q, p2);
    enqueueProcess(&q, p3);

    while (q.front != -1) {
        Process p = dequeueProcess(&q);
        printf("프로세스 %d 실행 중 (실행 시간: %d)\n", p.pid, p.burstTime);
    }
}

int main() {
    simulateProcessQueue();
    return 0;
}

결과 출력

프로세스 1 실행 중 (실행 시간: 5)  
프로세스 2 실행 중 (실행 시간: 3)  
프로세스 3 실행 중 (실행 시간: 7)

응용 예시 2: 프린터 작업 관리

프린터는 문서가 요청된 순서대로 출력되도록 큐를 사용해 작업을 관리합니다.

작동 방식

인쇄 요청이 들어오면 작업을 큐에 추가합니다.
프린터가 준비되면 큐에서 작업을 제거하여 출력합니다.

코드 예제

typedef struct {
    char jobName[50];
} PrintJob;

typedef struct {
    PrintJob arr[MAX];
    int front;
    int rear;
} PrintQueue;

// PrintQueue enqueue and dequeue functions are similar to the Process queue.

결론

큐는 프로세스 스케줄링, 작업 관리, 네트워크 패킷 처리 등 다양한 분야에서 사용됩니다. 배열 기반 큐는 이러한 문제를 간단하고 효율적으로 해결하는 데 적합한 선택입니다.

배열 기반 큐 구현 코드와 설명

다음은 배열을 사용하여 큐를 구현한 전체 코드와 각 부분에 대한 자세한 설명입니다. 이 코드는 삽입(Enqueue), 삭제(Dequeue), 초기화, 상태 확인 등의 기본 연산을 포함합니다.

전체 구현 코드

#include <stdio.h>
#define MAX 5

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Queue;

// 큐 초기화
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// 삽입 연산 (Enqueue)
void enqueue(Queue* q, int data) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue Overflow! 삽입할 수 없습니다.\n");
        return;
    }
    if (q->front == -1) { 
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = data;
    printf("삽입된 데이터: %d\n", data);
}

// 삭제 연산 (Dequeue)
int dequeue(Queue* q) {
    if (q->front == -1) {
        printf("Queue Underflow! 삭제할 수 없습니다.\n");
        return -1;
    }
    int data = q->arr[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    printf("삭제된 데이터: %d\n", data);
    return data;
}

// 큐 상태 출력
void displayQueue(Queue* q) {
    if (q->front == -1) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (1) {
        printf("%d ", q->arr[i]);
        if (i == q->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

// 메인 함수
int main() {
    Queue q;
    initQueue(&q);

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

    dequeue(&q);
    dequeue(&q);
    displayQueue(&q);

    enqueue(&q, 40);
    enqueue(&q, 50);
    displayQueue(&q);

    return 0;
}

코드 설명

초기화 함수

initQueue 함수는 큐를 초기 상태로 설정합니다.
front와 rear를 -1로 설정하여 비어 있음을 표시합니다.

삽입 함수 (Enqueue)

큐가 가득 찬 경우((rear + 1) % MAX == front), Overflow 상태를 출력합니다.
비어 있는 경우(front == -1), front를 초기화합니다.
새로운 데이터는 rear 인덱스에 추가되며, rear는 순환적으로 업데이트됩니다.

삭제 함수 (Dequeue)

큐가 비어 있는 경우(front == -1), Underflow 상태를 출력합니다.
데이터를 제거한 후, front를 순환적으로 업데이트합니다.
마지막 데이터를 제거하면 front와 rear를 초기 상태로 재설정합니다.

상태 출력 함수

큐의 모든 요소를 front에서 rear까지 순환적으로 출력합니다.

실행 결과

입력

enqueue(10), enqueue(20), enqueue(30), displayQueue()
dequeue(), dequeue(), displayQueue()
enqueue(40), enqueue(50), displayQueue()

출력

삽입된 데이터: 10  
삽입된 데이터: 20  
삽입된 데이터: 30  
Queue elements: 10 20 30  
삭제된 데이터: 10  
삭제된 데이터: 20  
Queue elements: 30  
삽입된 데이터: 40  
삽입된 데이터: 50  
Queue elements: 30 40 50

결론

배열 기반 큐는 간단한 데이터 구조로, 순환 큐 방식을 적용하여 공간 효율성을 높일 수 있습니다. 이 코드는 큐의 기본 원리와 배열을 활용한 효율적인 구현 방법을 이해하는 데 유용합니다.

요약

본 기사에서는 C언어에서 배열을 활용한 큐의 개념, 구현 방법, 그리고 응용 예제에 대해 다뤘습니다. 큐의 기본 구조와 연산(삽입, 삭제), 배열 기반 큐의 한계와 이를 해결하는 순환 큐의 구현 방법을 코드와 함께 설명했습니다. 또한, 프로세스 스케줄링과 프린터 작업 관리 등 큐의 실제 응용 사례를 통해 이해를 심화시켰습니다. 배열 기반 큐는 간단하면서도 다양한 문제 해결에 유용한 데이터 구조입니다.