[자료구조] 원형 큐 (Circular Queue) 응용 - 오름차순으로 큐에 데이터 삽입하기

 

 

data.txt

 

30
50
10
40
20

 

 

// 원형큐 응용 - 큐의 데이터를 오름차순으로 정렬하고 출력하기
// 숫자가 낮은 순서대로 저장

#include <stdio.h>

#define MAX_QUEUE_SIZE 100

typedef struct {
	int nPriority; // 큐의 요소 값 (낮은 순대로 저장하기 위함)
}QueueObject;

QueueObject queue[MAX_QUEUE_SIZE]; // 원형 큐를 배열리스트로 선언
int front, rear;

// initialize
void init_queue() { front = rear = 0; }

// isEmpty
int isEmpty() { return(front == rear); }

// isFull
int isFull() { return ((rear + 1) % MAX_QUEUE_SIZE == front); }

// queue에 priority에 따라서 add하는 함수 
void addq(int item, int nItems) // item: 추가하려는 priority, nItems: 데이터 개수
{
	int i;
	if (isFull())printf("queue is full \n");

	// 기존에 있는 큐에 있는 데이터와 수를 비교하여 어디에 넣을지 결정함
	if (nItems == 0)
		queue[nItems++].nPriority = item; // 0번째 인덱스에 추가
	else {
		// 루프를 돌며 내 위치를 찾는다 (내가 nPriority보다 작다면 삽입)
		// 뒤에서부터 반복문 돌며 비교
		for (i = nItems - 1;i >= 0;i--) {
			if (item < queue[i].nPriority) // 새로 들어온 item 보다 queue 데이터가 더 큰 경우에
				queue[i + 1].nPriority = queue[i].nPriority; // 하나 뒤로 밀어줌
			else
				break;
		}
		queue[i + 1].nPriority = item;
	}
	rear = (rear + 1) % MAX_QUEUE_SIZE;
}

QueueObject deleteq() {
	if (isEmpty()) {
		printf("queue is empty \n");
		return;
	}
	else {
		front = (front + 1) % MAX_QUEUE_SIZE;
		return queue[front];
	}
}

int main() {
	FILE* fp;
	int temp;
	QueueObject sstemp; // 임시변수
	int i, nCount; // 파일의 데이터 개수 cnt

	init_queue();
	nCount = 1;
	
	fp = fopen("data.txt", "rt");
	while (!feof(fp)) {
		fscanf(fp, "%d", &temp);
		addq(temp, nCount);
		nCount++;
	}

	for (i = 0;i < nCount - 1;i++) { // 1부터 카운트되었으므로 (nCount-1)까지
		sstemp = deleteq();
		printf("%d -> ", sstemp.nPriority);
	}
	printf("\n");

	fclose(fp);
	return 0;
}