큐(queue)는 데이터가 먼저 들어간 것이 먼저 나오는 특성을 가진 자료구조입니다. C언어에서 링크드 리스트를 사용하여 큐를 구현하는 방법과 메모리 레이아웃을 그림으로 함께 설명하겠습니다.

링크드 리스트로 큐 구현하기

 링크드 리스트로 큐를 구현하면 동적 메모리 할당을 통해 유연하게 크기를 조절할 수 있습니다. 아래는 큐의 기본 동작인 삽입(enqueue)과 삭제(dequeue)에 대해 단계별로 설명합니다.

큐 노드 정의하기

 큐 노드를 정의하는 구조체를 설계합니다. 이 구조체는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.

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

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

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

삽입 함수 구현하기 (Enqueue)

 새로운 데이터를 큐에 추가하는 함수입니다.

void enqueue(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("메모리 할당 오류\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("%d 삽입\n", value);
}

삭제 함수 구현하기 (Dequeue)

 큐에서 가장 먼저 추가된 데이터를 제거하는 함수입니다.

int dequeue() {
    if (front == NULL) {
        printf("큐가 비어 있습니다\n");
        return -1;
    }
    int value = front->data;
    Node* temp = front;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
    printf("%d 제거\n", value);
    return value;
}

메모리 레이아웃

 링크드 리스트 형태의 큐를 시각적으로 이해하기 위해 메모리 레이아웃을 그림으로 표현해보겠습니다. 아래 예제는 10, 20, 30을 순서대로 삽입한 후 10을 제거하는 과정입니다.

초기 상태 (빈 큐):

front -> NULL
rear  -> NULL

10 삽입 후:

front -> [10|NULL]
rear  -> [10|NULL]

20 삽입 후:

front -> [10|next] -> [20|NULL]
rear  -> [20|NULL]

30 삽입 후:

front -> [10|next] -> [20|next] -> [30|NULL]
rear  -> [30|NULL]

10 제거 후:

front -> [20|next] -> [30|NULL]
rear  -> [30|NULL]

예제 실행 코드

 마지막으로 완전한 프로그램을 작성하여 큐의 삽입 및 삭제 기능을 검증할 수 있습니다.

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue();
    dequeue();
    dequeue();
    return 0;
}

큐의 특성 요약

 링크드 리스트로 구현된 큐는 다음과 같은 장점과 단점을 갖습니다.

장점	단점
메모리 사용의 효율성	포인터 사용으로 인한 오버헤드
동적 크기 조절 가능	삽입 및 삭제 연산의 복잡성

 이처럼 링크드 리스트를 사용하면 동적 메모리 할당이 가능하여 큐의 크기를 유연하게 조절할 수 있지만, 각 노드마다 포인터를 유지해야 해서 메모리 오버헤드가 발생할 수 있습니다.

---