큐(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;
}큐의 특성 요약
링크드 리스트로 구현된 큐는 다음과 같은 장점과 단점을 갖습니다.
| 장점 | 단점 |
|---|---|
| 메모리 사용의 효율성 | 포인터 사용으로 인한 오버헤드 |
| 동적 크기 조절 가능 | 삽입 및 삭제 연산의 복잡성 |
이처럼 링크드 리스트를 사용하면 동적 메모리 할당이 가능하여 큐의 크기를 유연하게 조절할 수 있지만, 각 노드마다 포인터를 유지해야 해서 메모리 오버헤드가 발생할 수 있습니다.
