linked_queue.c - Examples

  1// linked_queue.c
  2// 연결 리스트 기반 큐 구현
  3// 동적 메모리 할당으로 크기 제한 없음
  4
  5#include <stdio.h>
  6#include <stdlib.h>
  7#include <stdbool.h>
  8
  9// 노드 구조체
 10typedef struct Node {
 11    int data;
 12    struct Node *next;
 13} Node;
 14
 15// 큐 구조체
 16typedef struct {
 17    Node *front;  // 첫 번째 노드 (제거 위치)
 18    Node *rear;   // 마지막 노드 (삽입 위치)
 19    int size;
 20} LinkedQueue;
 21
 22// 큐 생성
 23LinkedQueue* lqueue_create(void) {
 24    LinkedQueue *q = malloc(sizeof(LinkedQueue));
 25    if (q) {
 26        q->front = NULL;
 27        q->rear = NULL;
 28        q->size = 0;
 29    }
 30    return q;
 31}
 32
 33// 큐 해제 (모든 메모리 해제)
 34void lqueue_destroy(LinkedQueue *q) {
 35    Node *current = q->front;
 36    while (current) {
 37        Node *next = current->next;
 38        free(current);
 39        current = next;
 40    }
 41    free(q);
 42}
 43
 44// 비어있는지 확인
 45bool lqueue_isEmpty(LinkedQueue *q) {
 46    return q->front == NULL;
 47}
 48
 49// Enqueue - 뒤에 요소 추가 (O(1))
 50bool lqueue_enqueue(LinkedQueue *q, int value) {
 51    Node *node = malloc(sizeof(Node));
 52    if (!node) {
 53        printf("메모리 할당 실패!\n");
 54        return false;
 55    }
 56
 57    node->data = value;
 58    node->next = NULL;
 59
 60    // 큐가 비어있으면 front와 rear 모두 새 노드를 가리킴
 61    if (q->rear == NULL) {
 62        q->front = q->rear = node;
 63    } else {
 64        // 기존 rear 뒤에 새 노드 추가
 65        q->rear->next = node;
 66        q->rear = node;
 67    }
 68    q->size++;
 69    return true;
 70}
 71
 72// Dequeue - 앞에서 요소 제거 (O(1))
 73bool lqueue_dequeue(LinkedQueue *q, int *value) {
 74    if (lqueue_isEmpty(q)) {
 75        printf("Queue is empty!\n");
 76        return false;
 77    }
 78
 79    Node *node = q->front;
 80    *value = node->data;
 81    q->front = node->next;
 82
 83    // 마지막 노드를 제거한 경우 rear도 NULL로 설정
 84    if (q->front == NULL) {
 85        q->rear = NULL;
 86    }
 87
 88    free(node);
 89    q->size--;
 90    return true;
 91}
 92
 93// Front - 앞의 값 확인 (제거 안함)
 94bool lqueue_front(LinkedQueue *q, int *value) {
 95    if (lqueue_isEmpty(q)) {
 96        return false;
 97    }
 98    *value = q->front->data;
 99    return true;
100}
101
102// Rear - 뒤의 값 확인
103bool lqueue_rear(LinkedQueue *q, int *value) {
104    if (lqueue_isEmpty(q)) {
105        return false;
106    }
107    *value = q->rear->data;
108    return true;
109}
110
111// 큐 출력 (front부터 rear까지)
112void lqueue_print(LinkedQueue *q) {
113    printf("Queue (size=%d): front -> ", q->size);
114    Node *current = q->front;
115    while (current) {
116        printf("%d ", current->data);
117        current = current->next;
118    }
119    printf("<- rear\n");
120}
121
122// 큐 크기 반환
123int lqueue_size(LinkedQueue *q) {
124    return q->size;
125}
126
127// 모든 요소 출력 후 큐 초기화
128void lqueue_clear(LinkedQueue *q) {
129    int value;
130    while (lqueue_dequeue(q, &value)) {
131        // 단순히 모든 요소 제거
132    }
133}
134
135// 테스트 코드
136int main(void) {
137    LinkedQueue *q = lqueue_create();
138    if (!q) {
139        printf("큐 생성 실패!\n");
140        return 1;
141    }
142
143    printf("=== 연결 리스트 기반 큐 테스트 ===\n\n");
144
145    // Enqueue 테스트
146    printf("[ 1단계: Enqueue 5개 ]\n");
147    for (int i = 1; i <= 5; i++) {
148        printf("Enqueue %d -> ", i * 10);
149        lqueue_enqueue(q, i * 10);
150        lqueue_print(q);
151    }
152
153    // Front/Rear 확인
154    printf("\n[ 2단계: Front/Rear 확인 ]\n");
155    int front_val, rear_val;
156    if (lqueue_front(q, &front_val) && lqueue_rear(q, &rear_val)) {
157        printf("Front 값: %d (먼저 들어온 값)\n", front_val);
158        printf("Rear 값: %d (나중에 들어온 값)\n", rear_val);
159        lqueue_print(q);
160    }
161
162    // Dequeue 테스트
163    printf("\n[ 3단계: Dequeue 2개 ]\n");
164    int value;
165    for (int i = 0; i < 2; i++) {
166        if (lqueue_dequeue(q, &value)) {
167            printf("Dequeued: %d -> ", value);
168            lqueue_print(q);
169        }
170    }
171
172    // 추가 Enqueue
173    printf("\n[ 4단계: Enqueue 2개 더 ]\n");
174    for (int i = 6; i <= 7; i++) {
175        printf("Enqueue %d -> ", i * 10);
176        lqueue_enqueue(q, i * 10);
177        lqueue_print(q);
178    }
179
180    // 모든 요소 Dequeue
181    printf("\n[ 5단계: 모든 요소 Dequeue ]\n");
182    while (lqueue_dequeue(q, &value)) {
183        printf("Dequeued: %d -> ", value);
184        lqueue_print(q);
185    }
186
187    // Empty 상태에서 제거 시도
188    printf("\n[ 6단계: Empty 상태에서 Dequeue 시도 ]\n");
189    printf("Dequeue -> ");
190    lqueue_dequeue(q, &value);
191
192    // 대량 삽입 테스트
193    printf("\n[ 7단계: 대량 삽입 테스트 ]\n");
194    printf("10000개 요소 삽입 중...\n");
195    for (int i = 0; i < 10000; i++) {
196        lqueue_enqueue(q, i);
197    }
198    printf("삽입 완료! 현재 크기: %d\n", lqueue_size(q));
199
200    // 대량 제거 테스트
201    printf("\n처음 5개 요소 확인:\n");
202    for (int i = 0; i < 5; i++) {
203        lqueue_dequeue(q, &value);
204        printf("  Dequeued: %d\n", value);
205    }
206
207    // 메모리 정리
208    printf("\n메모리 해제 중...\n");
209    lqueue_destroy(q);
210    printf("큐 해제 완료!\n");
211
212    return 0;
213}