큐(Queue)의 핵심 개념

큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 선형 자료구조입니다. 가장 먼저 삽입된 데이터가 가장 먼저 제거되는 구조로, 일상생활의 대기 줄과 유사한 메커니즘을 가집니다. 운영체제의 프로세스 스케줄링, 네트워크 패킷 처리, 너비 우선 탐색(BFS) 등 다양한 알고리즘과 시스템 설계에서 필수적으로 사용됩니다.

주요 용어 및 동작

• Front (머리): 데이터가 삭제되는 지점
• Rear (꼬리): 데이터가 삽입되는 지점
• Enqueue (삽입): 큐의 맨 뒤에 새로운 데이터를 추가하는 작업
• Dequeue (삭제): 큐의 맨 앞 데이터를 꺼내고 제거하는 작업

1. 연결 리스트 기반 큐 구현

연결 리스트를 사용하면 메모리를 동적으로 할당하므로 큐의 크기를 미리 정할 필요가 없으며, 데이터 이동 시 발생하는 오버헤드가 적습니다.

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

typedef int Element;

// 노드 구조체 정의
typedef struct LinkedNode {
    Element data;
    struct LinkedNode* next;
} LinkedNode;

// 큐 관리 구조체
typedef struct {
    LinkedNode* front;
    LinkedNode* rear;
    int count;
} LinkedQueue;

// 초기화
void initQueue(LinkedQueue* q) {
    q->front = q->rear = NULL;
    q->count = 0;
}

// 데이터 삽입
void enqueue(LinkedQueue* q, Element val) {
    LinkedNode* newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
    if (!newNode) return;

    newNode->data = val;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->count++;
}

// 데이터 삭제
Element dequeue(LinkedQueue* q) {
    if (q->front == NULL) return -1;

    LinkedNode* temp = q->front;
    Element data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    q->count--;
    return data;
}

// 메모리 해제
void clearQueue(LinkedQueue* q) {
    while (q->front != NULL) {
        dequeue(q);
    }
}

2. 배열 기반 원형 큐(Circular Queue) 구현

일반 배열로 큐를 구현하면 데이터 삭제 시 앞부분의 공간이 낭비되는 '가짜 포화' 현상이 발생합니다. 이를 해결하기 위해 배열의 처음과 끝이 연결된 것처럼 동작하는 원형 큐를 사용합니다.

구현의 특징

• 배열 크기가 N일 때, 실제 저장 용량은 N-1로 설정하여 공백과 포화 상태를 구분합니다.
• 공백 상태: front == rear
• 포화 상태: (rear + 1) % MAX_SIZE == front

#define MAX_SIZE 6

typedef struct {
    int buffer[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

void initCircularQueue(CircularQueue* cq) {
    cq->front = 0;
    cq->rear = 0;
}

bool isFull(CircularQueue* cq) {
    return (cq->rear + 1) % MAX_SIZE == cq->front;
}

bool isEmpty(CircularQueue* cq) {
    return cq->front == cq->rear;
}

bool push(CircularQueue* cq, int val) {
    if (isFull(cq)) return false;
    
    cq->buffer[cq->rear] = val;
    cq->rear = (cq->rear + 1) % MAX_SIZE;
    return true;
}

int pop(CircularQueue* cq) {
    if (isEmpty(cq)) return -1;

    int res = cq->buffer[cq->front];
    cq->front = (cq->front + 1) % MAX_SIZE;
    return res;
}

3. 구현 방식별 장단점 비교

4. 큐의 실제 활용 사례

큐는 순서가 보장되어야 하는 모든 프로그래밍 영역에서 활용됩니다.

• 컴퓨터 시스템: 프린터 출력 대기열, CPU 스케줄링(Round Robin)
• 알리리즘: 그래프의 너비 우선 탐색(BFS) 구현
• 네트워크: 라우터의 데이터 패킷 버퍼링
• 소프트웨어 설계: 비동기 작업을 처리하기 위한 메시지 큐(Message Queue)