(C언어) 자료구조: 배열로 큐(Queue) 표현하기, 장점 단점

큐는 데이터 구조 중 하나로, FIFO(First In First Out) - 데이터를 먼저 집어넣은 순서대로 꺼낼 수 있는 - 자료구조입니다. 이 예제에서는 배열(Array)을 사용하여 큐(queue)를 구현하는 C언어 코드입니다.

 

테스트를 위해서 큐의 크기를 5로 설정했습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5

struct Queue {
    int items[MAX_QUEUE_SIZE];
    int front;
    int rear;
};

struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

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

int isFull(struct Queue* queue) {
    return (queue->rear == MAX_QUEUE_SIZE - 1);
}

void enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) {
        printf("큐가 꽉 찼습니다. %d를 추가할 수 없습니다.\n", item);
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear++;
    queue->items[queue->rear] = item;
    printf("%d를 큐에 추가했습니다.\n", item);
}

int dequeue(struct Queue* queue) {
    int item;
    if (isEmpty(queue)) {
        printf("큐가 비어 있습니다. 데이터를 꺼낼 수 없습니다.\n");
        return -1;
    }
    item = queue->items[queue->front];
    queue->front++;
    if (queue->front > queue->rear) {
        // 모든 아이템이 큐에서 제거된 경우 큐를 초기화합니다.
        queue->front = queue->rear = -1;
    }
    return item;
}

int main() {
    struct Queue* queue = createQueue();

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

    printf("꺼낸 아이템: %d\n", dequeue(queue));
    printf("꺼낸 아이템: %d\n", dequeue(queue));

    enqueue(queue, 40);
    enqueue(queue, 50);
    enqueue(queue, 60);

    printf("꺼낸 아이템: %d\n", dequeue(queue));
    printf("꺼낸 아이템: %d\n", dequeue(queue));
    printf("꺼낸 아이템: %d\n", dequeue(queue));
    printf("꺼낸 아이템: %d\n", dequeue(queue));

    return 0;
}

(Output)

10를 큐에 추가했습니다. 20를 큐에 추가했습니다. 30를 큐에 추가했습니다. 꺼낸 아이템: 10 꺼낸 아이템: 20 40를 큐에 추가했습니다. 50를 큐에 추가했습니다. 큐가 꽉 찼습니다. 60를 추가할 수 없습니다. 꺼낸 아이템: 30 꺼낸 아이템: 40 꺼낸 아이템: 50 큐가 비어 있습니다. 데이터를 꺼낼 수 없습니다. 꺼낸 아이템: -1

(C언어) 배열로 큐(Queue) 표현하기

 

배열로 표현된 큐(Queue)는 다음과 같은 장점과 단점을 갖습니다:

장점:
간단하고 빠른 접근: 배열은 인덱스를 사용하여 원하는 요소에 빠르게 접근할 수 있습니다. 큐의 앞부분(프런트)과 뒷부분(리어)을 배열의 인덱스로 효율적으로 관리할 수 있습니다.

메모리 효율성: 배열은 다른 동적 메모리 할당 방식에 비해 상대적으로 메모리를 효율적으로 사용합니다. 메모리 단편화와 할당/해제 오버헤드가 없습니다.

구현이 간단: 배열로 큐를 구현하는 것은 비교적 간단하며, 소스 코드가 직관적이며 이해하기 쉽습니다.

단점:
크기 제한: 배열의 크기는 고정되어 있으므로 크기를 미리 정의해야 합니다. 이로 인해 크기 초과나 남은 공간을 효율적으로 활용하지 못할 수 있습니다.

큐의 크기 확장: 배열 크기를 동적으로 조절하는 것은 복잡하며, 새 배열을 할당하고 데이터를 복사해야 합니다.

메모리 낭비: 큐가 비어 있을 때에도 일정한 크기의 배열이 필요하므로 메모리 낭비가 발생할 수 있습니다.

오버플로우 및 언더플로우: 배열 크기를 초과하거나 언더플로우가 발생할 경우 데이터 손실 또는 오류가 발생할 수 있습니다.

큐의 크기 제한: 배열 큐의 크기가 고정되므로 큐에 저장할 수 있는 데이터의 수에 제한이 있습니다.

배열로 표현된 큐는 간단하고 빠른 접근을 제공하지만, 크기의 제한과 큐의 크기 조절 등의 한계를 가지고 있습니다. 이러한 단점을 극복하기 위해 링크드 리스트로 구현된 큐를 사용하기도 합니다. 링크드 리스트 큐는 크기 조절이 더 유연하며, 동적 메모리 할당을 통해 큐의 크기를 조절할 수 있습니다.