[c언어] 큐의 종류

26 Dec 2023

c언어

C언어에서 큐는 메모리 내부에서 데이터를 순서대로 저장하고 삭제하는 자료 구조입니다. 큐는 여러 종류가 있지만 대표적인 두 가지 종류를 다루어 보겠습니다.

1. 배열 기반 큐 (Array-based Queue)

배열 기반 큐는 배열을 사용하여 데이터를 저장하는 큐입니다. 크기가 정해져 있기 때문에 고정된 개수의 데이터를 저장하고 삭제할 수 있습니다. 데이터를 삽입하거나 삭제할 때 배열의 크기를 변경하는 것은 불가능하기 때문에, 크기에 대해 미리 알고 있어야 합니다.

#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = -1, rear = -1;

void enqueue(int data) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue is full");
    } else {
        if (front == -1) {
            front = 0;
        }
        rear++;
        queue[rear] = data;
    }
}

int dequeue() {
    int data;
    if (front == -1 || front > rear) {
        printf("Queue is empty");
        return -1;
    } else {
        data = queue[front];
        front++;
        return data;
    }
}

2. 연결 리스트 기반 큐 (Linked List-based Queue)

연결 리스트 기반 큐는 연결 리스트를 사용하여 데이터를 저장하는 큐입니다. 크기가 동적으로 변경될 수 있기 때문에, 데이터를 삽입하거나 삭제할 때마다 메모리를 동적으로 할당 또는 해제할 수 있습니다. 이는 배열 기반 큐와 달리 큐의 크기에 대해 미리 알 필요가 없다는 장점이 있습니다.

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

struct Node* front = NULL;
struct Node* rear = NULL;

void enqueue(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    if (front == NULL && rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

int dequeue() {
    int data;
    if (front == NULL) {
        printf("Queue is empty");
        return -1;
    } else {
        struct Node* temp = front;
        data = temp->data;
        if (front == rear) {
            front = rear = NULL;
        } else {
            front = front->next;
        }
        free(temp);
        return data;
    }
}

위에서 설명한 두 종류의 큐는 각각 배열 기반 큐와 연결 리스트 기반 큐로, 데이터를 저장하고 삭제하는 방식에서의 차이가 있습니다. 적절한 상황에 맞게 선택하여 사용할 수 있도록 이해하는 것이 중요합니다.

1. 배열 기반 큐 (Array-based Queue)

2. 연결 리스트 기반 큐 (Linked List-based Queue)

참고 자료