자료구조 C언어 큐(Queue) 예제

큐(Queue)는 데이터를 일시적으로 저장하는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조를 갖습니다. 큐는 일반적으로 줄 서기(linear queue)나 자동차 대기 줄(car queue) 등에서 사용됩니다.

큐는 크게 두 가지 연산을 지원합니다.

Enqueue(삽입): 큐의 뒤쪽(rear)에 새로운 데이터를 추가하는 연산입니다.
Dequeue(삭제): 큐의 앞쪽(front)에서 데이터를 삭제하고 반환하는 연산입니다.

큐는 일반적으로 배열(array)이나 연결 리스트(linked list)를 이용하여 구현됩니다. 배열을 이용한 구현에서는 큐의 앞과 뒤를 가리키는 포인터(front, rear)를 이용하여 삽입과 삭제 연산을 수행합니다. 연결 리스트를 이용한 구현에서는 각 노드가 다음 노드를 가리키는 포인터(next)를 갖고 있으며, 삽입과 삭제 연산에서는 이 포인터를 이용하여 노드를 추가하거나 제거합니다.

큐는 다음과 같은 특징을 갖습니다.

선입선출(FIFO) 구조를 갖습니다.
삽입과 삭제 연산이 O(1)의 시간 복잡도를 갖습니다.
큐의 크기는 동적으로 변경할 수 있습니다.
큐는 일반적으로 스레드(Thread)나 프로세스(Process) 간의 통신에서 사용됩니다.

#include <stdio.h>
#define MAX_SIZE 100 // 큐의 최대 크기

int queue[MAX_SIZE];
int front = 0, rear = 0; // 큐의 앞과 뒤를 가리키는 포인터

// 큐가 비어있는지 확인하는 함수
int is_empty() {
    return front == rear;
}

// 큐가 가득 차있는지 확인하는 함수
int is_full() {
    return rear == MAX_SIZE;
}

// 큐에 데이터를 추가하는 함수
void enqueue(int data) {
    if (is_full()) {
        printf("Queue is full.\n");
        return;
    }
    queue[rear++] = data;
}

// 큐에서 데이터를 삭제하고 반환하는 함수
int dequeue() {
    if (is_empty()) {
        printf("Queue is empty.\n");
        return -1;
    }
    int data = queue[front++];
    return data;
}

// 큐의 모든 데이터를 출력하는 함수
void print_queue() {
    printf("Queue: ");
    for (int i = front; i < rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    print_queue();
    printf("Dequeued data: %d\n", dequeue());
    print_queue();
    return 0;
}

위 예제에서는 배열을 이용하여 큐를 구현하였습니다. front와 rear는 각각 큐의 앞과 뒤를 가리키는 포인터입니다. enqueue 함수는 데이터를 큐의 뒤에 추가하고, dequeue 함수는 큐의 앞에서부터 데이터를 삭제하고 반환합니다. print_queue 함수는 큐의 모든 데이터를 출력합니다.



위 예제를 실행하면 다음과 같은 결과가 출력됩니다.

Queue: 1 2 3
Dequeued data: 1
Queue: 2 3