원형 큐 (Circular Queue) 예

// 원형 큐 예
 
#include <stdio.h>
#include <stdlib.h>
 
typedef int element;
typedef struct {
    element *queue;
    int front, rear;
    int size;
} QueueType;
 
 
void init(QueueType *q) {
    q->front = q->rear = 0;
    q->size = 2;        // 원형 큐의 특징 때문에
    q->queue = (element *)malloc(sizeof(element)*q->size);
}
 
int is_full(QueueType *q) {
    return ((q->rear + 1) % q->size == q->front);
}
 
void queueFull(QueueType *q) {        // 포화 상태일 경우, 크기 2배 증가                                                       
    element *data = (element *)malloc(sizeof(element)*q->size);
    int start = (q->front + 1) % q->size;
    int end = (q->rear + 1) % q->size;
    int i, j;
    if (start < end) {
        for (i = start, j = 1; i < end; i++, j++) {
            data[j] = q->queue[i];
        }
    }
    else {
        for (i = start, j = 1; i < q->size; i++, j++) {
            data[j] = q->queue[i];
        }
        for (i = 0; i < end; i++, j++) {
            data[j] = q->queue[i];
        }
    }
    q->front = 0;
    q->rear = g->size - 1;
    free(q->queue);
    q->queue = (element *)malloc(sizeof(element)*q->size * 2);
    for (i = 0; i <= q->rear; i++) {
        q->queue[i] = data[i];
    }
    q->size *= 2;
    free(data);
}
 
void enqueue(QueueType *q, element item) {
    if (is_full(q)) {
        printf("큐가 포화상태입니다. \n");
        queueFull(q);
    }
    q->rear = (q->rear + 1) % q->size;
    q->queue[q->rear] = item;
}
 
element dequeue(QueueType *q) {
    if (is_empty(q)) {
        error("큐가 공백상태입니다.");
    }
    q->front = (q->front + 1) % q->size;
    return q->queue[q->front];
}
 
void printQ(QueueType *q) {        // 큐의 내용을 출력하는 연산
    int i, first, last;
    first = (q->front + 1) % q->size;
    last = (q->rear + 1) % q->size;
    printf(" Circular Queue : [");
    if (first > last) {
        for (i = 0; i < last; i++) {
            printf("%3d", q->queue[i]);
        }
        for (i = last; i < first; i++) {
            printf("%3c", '#');
        }
        for (i = first; i < q->size; i++) {
            printf("%3d", q->queue[i]);
        }
    }
    else if (first < last) {
        for (i = 0; i < first; i++) {
            printf("%3c", '#');
        }
        for (i = first i < last; i++) {
            printf("%3d", q->queue[i]);
        }
        for (i = last; i < q->size; i++) {
            printf("%3c", '#');
        }
    }
    else {        // first == last
        for (i = 0; i < q->size; i++) {
            printf("%3c", '#');
        }
    }
 
    printf(" ] \n");
    printf("Front: %d, Rear: %d\n", q->front, q->rear);
}