연결 큐(Linked Queue)는 연결 리스트(Linked List)의 동적 메모리 할당 특성과 큐의 선입선출(FIFO, First-In-First-Out) 원칙이 결합된 효율적인 자료구조입니다. 고정된 크기를 가지는 배열 기반의 큐와 달리, 메모리가 허용하는 한 자유롭게 확장할 수 있다는 장점이 있습니다.

1. 연결 큐의 구조 정의

연결 큐를 구현하기 위해서는 데이터를 저장하는 개별 단위인 '노드'와, 이 노드들의 시작(Front)과 끝(Rear)을 관리하는 '컨트롤러' 구조체가 필요합니다.

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

// 큐의 각 데이터를 담을 노드 구조체
typedef struct Node {
    int data;
    struct Node* next;
} QNode;

// 큐의 앞과 뒤를 가리키는 포인터를 관리하는 구조체
typedef struct {
    QNode* front;
    QNode* rear;
} LinkedQueue;

// 큐 초기화: 더미 노드를 활용하여 연산의 편의성 제공
LinkedQueue* initQueue() {
    LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    QNode* dummyNode = (QNode*)malloc(sizeof(QNode));
    
    dummyNode->next = NULL;
    queue->front = dummyNode;
    queue->rear = dummyNode;
    
    return queue;
}

2. 핵심 연산 구현

연결 큐의 핵심인 삽입(Push)과 삭제(Pop) 연산을 구현합니다. 삽입은 Rear 포인터를 통해 이루어지며, 삭제는 Front 포인터를 통해 진행됩니다.

// 데이터 삽입 (Enqueue)
void push(LinkedQueue* q, int val) {
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = val;
    newNode->next = NULL;

    // 현재의 tail 뒤에 새 노드 연결 후 tail 이동
    q->rear->next = newNode;
    q->rear = newNode;
}

// 데이터 추출 및 삭제 (Dequeue)
int pop(LinkedQueue* q) {
    if (q->front == q->rear) {
        printf("에러: 큐가 비어 있습니다.\n");
        return -1;
    }

    QNode* targetNode = q->front->next;
    int extractedData = targetNode->data;

    // 프론트 포인터의 다음 연결을 변경
    q->front->next = targetNode->next;

    // 만약 마지막 노드를 삭제한 것이라면 rear를 다시 front로 설정
    if (q->rear == targetNode) {
        q->rear = q->front;
    }

    free(targetNode);
    return extractedData;
}

// 큐 전체 데이터 출력
void printQueue(LinkedQueue* q) {
    QNode* current = q->front->next;
    printf("Queue elements: ");
    while (current != NULL) {
        printf("[%d] ", current->data);
        current = current->next;
    }
    printf("\n");
}

3. 알고리즘 검증 및 테스트

작성한 연결 큐가 의도한 대로 동작하는지 테스트 함수를 통해 확인합니다. 연속적인 데이터 삽입 후 추출 시의 포인터 변화와 예외 상황 처리를 점검합니다.

void runQueueTest() {
    LinkedQueue* myQueue = initQueue();

    // 데이터 삽입 테스트
    push(myQueue, 100);
    push(myQueue, 200);
    push(myQueue, 300);
    printQueue(myQueue);

    // 데이터 추출 테스트
    printf("Pop: %d\n", pop(myQueue));
    printf("Pop: %d\n", pop(myQueue));
    printf("Pop: %d\n", pop(myQueue));
    
    // 비어있는 상태에서의 추출 시도
    printf("Pop from empty: %d\n", pop(myQueue));

    // 재삽입 후 출력
    push(myQueue, 500);
    printQueue(myQueue);
    
    // 메모리 해제 (실제 운영 코드에서는 전체 노드 순회하며 free 필요)
}

int main() {
    runQueueTest();
    return 0;
}

연결 큐의 구현에서 가장 중요한 포인트는 rear 포인터의 관리입니다. 특히 노드를 삭제할 때 큐가 완전히 비게 된다면, rear 포인터가 가리키던 노드가 메모리에서 해제되므로 이를 반드시 front(더미 노드)로 다시 향하게 처리해야 포인터 오류를 방지할 수 있습니다.