FIFO Queue

FIFO Queue

Queue(큐)는 데이터 구조 중 하나로, 먼저 들어간 데이터가 먼저 나오는(FIFO, First-In-First-Out) 방식으로 작동합니다. 큐는 선입선출 구조이기 때문에, 대기열, 작업 스케줄링, 메시지 전달 등 여러 상황에서 유용하게 사용됩니다.

큐의 기본 연산은 다음과 같습니다:

1. Enqueue: 큐의 뒤쪽(rear)에 데이터를 추가하는 연산.
2. Dequeue: 큐의 앞쪽(front)에서 데이터를 제거하고 반환하는 연산.
3. Front/Peek: 큐의 가장 앞에 있는 데이터를 반환하되, 큐에서 제거하지 않는 연산.
4. isEmpty: 큐가 비어 있는지 확인하는 연산.

큐는 배열 또는 연결 리스트로 구현될 수 있으며, Python에서는 collections 모듈의 deque나 queue 모듈의 Queue 클래스를 사용하여 쉽게 큐를 다룰 수 있습니다.

큐는 일반적으로 다음과 같은 용도로 많이 사용됩니다:

• 프로세스 스케줄링: 운영체제에서 프로세스를 대기열로 관리하여 순서대로 처리.
• 네트워크 패킷 처리: 네트워크 트래픽을 처리할 때 데이터 패킷이 순서대로 처리되도록 관리.
• BFS (Breadth-First Search): 그래프 탐색 알고리즘에서 노드들을 순서대로 탐색하기 위해 큐를 사용.

큐는 또한 여러 동시성 문제를 해결하기 위해 메시지 큐(Message Queue)로 사용되기도 합니다. 예를 들어, 프로듀서-컨슈머 패턴에서 작업을 안전하게 전달하는 방식으로 활용됩니다.

#include <stdio.h>
#include <stdlib.h>
// stdio.h: 입출력 관련 함수(printf, scanf 등)를 사용하기 위한 헤더 파일입니다.
// stdlib.h: 동적 메모리 할당 등 유틸리티 함수들을 사용하기 위한 헤더 파일입니다. 
//           여기서는 사용되지 않았지만, 일반적으로 큐 구현에서 동적 할당을 위해 포함할 수 있습니다.

// 큐의 최대 크기를 100으로 정의합니다. 큐의 크기는 고정되어 있으며 이 크기를 초과해서는 데이터를 저장할 수 없습니다.
#define MAX_QUEUE_SIZE 5

/**
 * @brief 
 * Queue라는 구조체를 정의합니다.
 * data[MAX_QUEUE_SIZE]: 큐 데이터를 저장하는 배열입니다.
 * front: 큐의 앞쪽 인덱스를 나타내며, 첫 번째 요소의 위치를 가리킵니다.
 * rear: 큐의 마지막 요소 인덱스를 나타냅니다.
 */
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

// init 함수는 큐를 초기화합니다. front와 rear를 -1로 설정하여 큐가 비어 있음을 나타냅니다.
void init(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// isEmpty 함수는 큐가 비어 있는지 확인합니다. front가 -1이면 큐가 비어 있는 상태입니다.
int isEmpty(Queue *q) {
    return q->front == -1;
}

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

// enqueue 함수는 큐에 요소를 추가합니다.
void enqueue(Queue *q, int value) {
    // 큐가 가득 찼으면 삽입을 하지 않고 메시지를 출력합니다.
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    // 큐가 비어 있다면 front를 0으로 설정합니다.
    if (isEmpty(q)) {
        q->front = 0;
    }
    // rear를 증가시킨 후 새로운 값을 큐에 저장합니다.
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = value;
}

// dequeue 함수는 큐에서 요소를 제거하고 반환합니다.
int dequeue(Queue *q) {
    // 큐가 비어 있으면 오류 메시지를 출력하고 -1을 반환합니다.
    if (isEmpty(q)) {
        printf("Queue is Emty!\n");
        return -1;
    }
    int value = q->data[q->front];
    // 제거한 후, front와 rear가 동일하면 큐가 비게 되므로 둘 다 -1로 초기화합니다.
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        // 그렇지 않으면 front를 순환 방식으로 증가시킵니다.
        q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    }
    return value;
}

// display 함수는 큐의 모든 요소를 출력합니다.
void display(Queue *q) {
    // 큐가 비어 있으면 "Queue is empty!" 메시지를 출력합니다.
    if (isEmpty(q)) {
        printf("Queue is Emty!\n");
        return;
    }
    // 순환 방식으로 front부터 rear까지 요소를 출력합니다.
    for(int i = q->front; i != q->rear; i = (i+1) % MAX_QUEUE_SIZE) {
        printf("%d ", q->data[i]);
    }
    printf("%d\n", q->data[q->rear]);
}

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

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

    printf("Queue after enqueuing 10, 20, 30: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    enqueue(&q, 60);
    printf("Queue after enqueuing 70: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Queue after dequeuing: ");
    display(&q);

    return 0;
}

C 코드 컴파일

gcc queue.c -o queue

실행

./queue
---
Queue is full!
Queue after enqueuing 10, 20, 30: 10 20 30 40 50
Dequeued: 10
Queue after dequeuing: 20 30 40 50
Queue after enqueuing 70: 20 30 40 50 60
Dequeued: 20
Queue after dequeuing: 30 40 50 60
Dequeued: 30
Queue after dequeuing: 40 50 60
Dequeued: 40
Queue after dequeuing: 50 60
Dequeued: 50
Queue after dequeuing: 60
Dequeued: 60
Queue after dequeuing: Queue is Emty!

ㅇ