우선순위 큐.txt [5 KB]
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #include <stdio.h> #include <stdlib.h> #include <time.h> // 요소 타입 typedef struct { int id; int arrival_time; int service_time; int priority; // 우선순위 추가 } element; // 큐 타입 #define MAX_QUEUE_SIZE 100 typedef struct { element data[MAX_QUEUE_SIZE]; int front, rear; } QueueType; // 오류 함수 void error(char* message) { fprintf(stderr, "%s\n", message); exit(1); } // 공백 상태 검출 함수 void init_queue(QueueType* q) { q->front = q->rear = 0; } // 공백 상태 검출 함수 int is_empty(QueueType* q) { return (q->front == q->rear); } // 포화 상태 검출 함수 int is_full(QueueType* q) { return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front); } // 원형큐 출력 함수 void queue_print(QueueType* q) { printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear); if (!is_empty(q)) { int i = q->front; do { i = (i + 1) % (MAX_QUEUE_SIZE); printf("ID=%d, Arrival=%d, Service=%d, Priority=%d | ", q->data[i].id, q->data[i].arrival_time, q->data[i].service_time, q->data[i].priority); if (i == q->rear) break; } while (i != q->front); } printf("\n"); } // 삽입 함수 (우선순위 기반) void enqueue(QueueType* q, element item) { if (is_full(q)) error("큐가 포화상태입니다"); // 새로운 rear 위치를 저장 int new_rear = (q->rear + 1) % MAX_QUEUE_SIZE; // 우선순위에 따라 적절한 위치에 삽입 int i = q->rear; // 현재 rear 위치 // 우선순위에 따라 적절한 위치를 찾아 이동 while (i != q->front && q->data[i % MAX_QUEUE_SIZE].priority < item.priority) { // 현재 위치를 한 칸 뒤로 이동 q->data[new_rear] = q->data[i % MAX_QUEUE_SIZE]; new_rear = i; // 이동한 위치를 새 rear로 설정 i = (i - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; // i를 한 칸 뒤로 이동 (원형 큐) } // 적절한 위치에 새 항목 삽입 q->data[new_rear] = item; q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; // rear를 업데이트 } // 삭제 함수 element dequeue(QueueType* q) { if (is_empty(q)) error("큐가 공백상태입니다"); q->front = (q->front + 1) % MAX_QUEUE_SIZE; return q->data[q->front]; } // 삭제 함수 element peek(QueueType* q) { if (is_empty(q)) error("큐가 공백상태입니다"); return q->data[(q->front + 1) % MAX_QUEUE_SIZE]; } int main(void) { int minutes = 60; int total_wait = 0; int total_customers = 0; int service_time = 0; int service_customer; QueueType queue; init_queue(&queue); srand(time(NULL)); for (int clock = 0; clock < minutes; clock++) { printf("시각=%d\n", clock); if ((rand() % 10) < 7) { element customer; customer.id = total_customers++; customer.arrival_time = clock; customer.service_time = rand() % 8 + 1; customer.priority = rand() % 10; // 랜덤으로 우선순위 설정 enqueue(&queue, customer); printf("\t고객 %2d이 %2d분 입장 업무시간=%2d분 (우선순위=%d)\n", customer.id, customer.arrival_time, customer.service_time, customer.priority); } if (service_time > 0) { printf("\t\t\t\t\t\t\t 고객 %2d 업무처리중 \n", service_customer); service_time--; } else { if (!is_empty(&queue)) { element customer = dequeue(&queue); service_customer = customer.id; service_time = customer.service_time; printf("\t고객 %2d이 %2d분 시작 대기시간=%2d분\n", customer.id, clock, clock - customer.arrival_time); total_wait += clock - customer.arrival_time; } } } printf("전체 대기 시간=%d분\n", total_wait); if (total_customers > 0) { printf("전체 고객 수=%d, 평균 대기 시간=%.2f분\n", total_customers, (float)total_wait / total_customers); } else { printf("고객이 없습니다.\n"); } return 0; } | cs |
자료구조 실습게시판