circular_queue.c - Examples

  1// circular_queue.c
  2// 원형 큐(Circular Queue) 구현
  3// 배열의 앞부분 재사용으로 공간 효율성 향상
  4
  5#include <stdio.h>
  6#include <stdbool.h>
  7
  8#define MAX_SIZE 5
  9
 10// 원형 큐 구조체
 11typedef struct {
 12    int data[MAX_SIZE];
 13    int front;  // 첫 번째 요소 위치
 14    int rear;   // 마지막 요소 위치
 15    int count;  // 현재 요소 개수
 16} CircularQueue;
 17
 18// 큐 초기화
 19void queue_init(CircularQueue *q) {
 20    q->front = 0;
 21    q->rear = -1;
 22    q->count = 0;
 23}
 24
 25// 비어있는지 확인
 26bool queue_isEmpty(CircularQueue *q) {
 27    return q->count == 0;
 28}
 29
 30// 가득 찼는지 확인
 31bool queue_isFull(CircularQueue *q) {
 32    return q->count == MAX_SIZE;
 33}
 34
 35// Enqueue - 뒤에 요소 추가 (O(1))
 36bool queue_enqueue(CircularQueue *q, int value) {
 37    if (queue_isFull(q)) {
 38        printf("Queue is full!\n");
 39        return false;
 40    }
 41
 42    q->rear = (q->rear + 1) % MAX_SIZE;  // 원형으로 순환
 43    q->data[q->rear] = value;
 44    q->count++;
 45    return true;
 46}
 47
 48// Dequeue - 앞에서 요소 제거 (O(1))
 49bool queue_dequeue(CircularQueue *q, int *value) {
 50    if (queue_isEmpty(q)) {
 51        printf("Queue is empty!\n");
 52        return false;
 53    }
 54
 55    *value = q->data[q->front];
 56    q->front = (q->front + 1) % MAX_SIZE;  // 원형으로 순환
 57    q->count--;
 58    return true;
 59}
 60
 61// Front - 앞의 값 확인 (제거 안함)
 62bool queue_front(CircularQueue *q, int *value) {
 63    if (queue_isEmpty(q)) {
 64        return false;
 65    }
 66    *value = q->data[q->front];
 67    return true;
 68}
 69
 70// Rear - 뒤의 값 확인
 71bool queue_rear(CircularQueue *q, int *value) {
 72    if (queue_isEmpty(q)) {
 73        return false;
 74    }
 75    *value = q->data[q->rear];
 76    return true;
 77}
 78
 79// 큐 출력 (front부터 rear까지)
 80void queue_print(CircularQueue *q) {
 81    printf("Queue (count=%d): [", q->count);
 82    if (!queue_isEmpty(q)) {
 83        int i = q->front;
 84        for (int c = 0; c < q->count; c++) {
 85            printf("%d", q->data[i]);
 86            if (c < q->count - 1) printf(", ");
 87            i = (i + 1) % MAX_SIZE;
 88        }
 89    }
 90    printf("] (front=%d, rear=%d)\n", q->front, q->rear);
 91}
 92
 93// 배열 상태 시각화 (디버깅용)
 94void queue_visualize(CircularQueue *q) {
 95    printf("배열 상태: [");
 96    for (int i = 0; i < MAX_SIZE; i++) {
 97        if (q->count > 0) {
 98            int start = q->front;
 99            int end = q->rear;
100            bool inRange = false;
101
102            // 원형 큐에서 i가 유효 범위인지 확인
103            if (start <= end) {
104                inRange = (i >= start && i <= end);
105            } else {
106                inRange = (i >= start || i <= end);
107            }
108
109            if (inRange) {
110                printf("%d", q->data[i]);
111            } else {
112                printf("-");
113            }
114        } else {
115            printf("-");
116        }
117        if (i < MAX_SIZE - 1) printf(" ");
118    }
119    printf("]\n");
120
121    // front와 rear 위치 표시
122    printf("           ");
123    for (int i = 0; i < MAX_SIZE; i++) {
124        if (i == q->front && i == q->rear && q->count > 0) {
125            printf("FR");
126        } else if (i == q->front && q->count > 0) {
127            printf("F ");
128        } else if (i == q->rear && q->count > 0) {
129            printf("R ");
130        } else {
131            printf("  ");
132        }
133    }
134    printf("\n");
135}
136
137// 큐 크기 반환
138int queue_size(CircularQueue *q) {
139    return q->count;
140}
141
142// 테스트 코드
143int main(void) {
144    CircularQueue q;
145    queue_init(&q);
146
147    printf("=== 원형 큐 테스트 ===\n\n");
148
149    // Enqueue 테스트 (큐를 가득 채움)
150    printf("[ 1단계: Enqueue 5개 (큐 가득 채우기) ]\n");
151    for (int i = 1; i <= 5; i++) {
152        printf("Enqueue %d -> ", i * 10);
153        queue_enqueue(&q, i * 10);
154        queue_print(&q);
155        queue_visualize(&q);
156        printf("\n");
157    }
158
159    // Full 상태에서 추가 시도
160    printf("[ 2단계: Full 상태에서 Enqueue 시도 ]\n");
161    printf("Enqueue 60 -> ");
162    queue_enqueue(&q, 60);
163    printf("\n");
164
165    // Dequeue 2개
166    int value;
167    printf("[ 3단계: Dequeue 2개 ]\n");
168    for (int i = 0; i < 2; i++) {
169        queue_dequeue(&q, &value);
170        printf("Dequeued: %d -> ", value);
171        queue_print(&q);
172        queue_visualize(&q);
173        printf("\n");
174    }
175
176    // 다시 Enqueue (원형 특성 확인)
177    printf("[ 4단계: 다시 Enqueue 2개 (원형 순환 확인) ]\n");
178    for (int i = 6; i <= 7; i++) {
179        printf("Enqueue %d -> ", i * 10);
180        queue_enqueue(&q, i * 10);
181        queue_print(&q);
182        queue_visualize(&q);
183        printf("\n");
184    }
185
186    // Front와 Rear 확인
187    printf("[ 5단계: Front/Rear 확인 ]\n");
188    int front_val, rear_val;
189    if (queue_front(&q, &front_val) && queue_rear(&q, &rear_val)) {
190        printf("Front 값: %d, Rear 값: %d\n", front_val, rear_val);
191    }
192    printf("\n");
193
194    // 모든 요소 Dequeue
195    printf("[ 6단계: 모든 요소 Dequeue ]\n");
196    while (queue_dequeue(&q, &value)) {
197        printf("Dequeued: %d -> ", value);
198        queue_print(&q);
199    }
200
201    // Empty 상태에서 제거 시도
202    printf("\n[ 7단계: Empty 상태에서 Dequeue 시도 ]\n");
203    printf("Dequeue -> ");
204    queue_dequeue(&q, &value);
205
206    return 0;
207}