티스토리 뷰
Data Structure(자료 구조)를 주제로 한 일곱번째 포스팅은 원형큐와 선형큐를 이용하여 자료를 구성하고 이때 처리시간을 비교하는 실험을 해보겠습니다.
"선형큐와 원형큐를 구현하고 같은 양의 데이터에 있어 처리시간을 비교하여라"
두 형식의 큐를 직접 구현하여 MAX_QUEUE_SIZE를 10, 100, 200, 400, 800, 1000으로 변환하며
처리시간을 실험해 봤습니다.
실험 결과 원형큐의 경우가 선형큐에 비해 확실히 시간이 절약되었고 결과는 다음 차트와 같습니다.
크기가 더욱 커지게 된다면 소요되는 시간 더욱 차이가 날것으로 예상됩니다.
프로그램소스)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_QUEUE_SIZE 1000
/*typedef struct {
int id;
int arrival_time;
int service_time;
}element;
*/
typedef int element;
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->rear = -1;
q->front = -1;*/
q->front = q->rear = 0;
}
int is_empty(QueueType* q)
{
/*if (q->front == q->rear)
return 1;
else
return 0;*/
return(q->front == q->rear);
}
int is_full(QueueType* q)
{
/*if (q->rear == MAX_QUEUE_SIZE - 1)
return 1;
else
return 0;
*/
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
void queue_print(QueueType* q)
{
/*
for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
if (i <= q->front || i > q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
*/
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("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i!=q->front);
}
printf("\n");
}
void enqueue(QueueType* q, element item)
{
if (is_full(q)){
error("큐가 포화된 상태");
//return;
}
//q->data[++(q->rear)] = item;
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
int dequeue(QueueType* q)
{
if (is_empty(q)) {
error("큐가 공백");
// return -1;
}
q->front = (q->front+1) % MAX_QUEUE_SIZE;
//int item = q->data[++(q->front)];
//return item;
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)
{
clock_t start, stop;
double duration;
start = clock(); //측정 시작
int item = 0;
int a, b, c;
int x = 0;
QueueType q;
init_queue(&q);
for (a = 0; a < MAX_QUEUE_SIZE-1; a++)
{
enqueue(&q, x); queue_print(&q);
x = x + 10;
}
for (b = MAX_QUEUE_SIZE-1; b > 0; b--) {
item = dequeue(&q); queue_print(&q);
}
stop = clock(); //측정종료
duration = (double)(stop - start) / CLOCKS_PER_SEC;
printf("수행시간은 %f초 입니다.\n", duration);
return 0;
}
/*
int main(void)
{
clock_t start, stop;
double duration;
start = clock(); //측정 시작
int item = 0;
int a, b, c;
int x = 0;
QueueType q;
init_queue(&q);
for (a = 0; a < MAX_QUEUE_SIZE; a++)
{
enqueue(&q, x); queue_print(&q);
x = x + 10;
for (b = MAX_QUEUE_SIZE ; b > 0 / 2; b--) {
item = dequeue(&q); queue_print(&q);
}
stop = clock(); //측정종료
duration = (double)(stop - start) / CLOCKS_PER_SEC;
printf("수행시간은 %f초 입니다.\n", duration);
return 0;
}
*/
결과 콘솔)
'Development > Data Structure' 카테고리의 다른 글
| Data Structure - 노드와 연결리스트의 이해(3) (0) | 2021.02.18 |
|---|---|
| Data Structure - 노드와 연결리스트의 이해(2) (0) | 2021.02.17 |
| Data Structure - 노드와 연결리스트의 이해(1) (0) | 2021.02.17 |
| Data Structure - 스택을 이용한 미로 표현 (0) | 2021.02.17 |
| Data Structure - 희소행렬, 전치행렬 (0) | 2021.02.17 |