[자료구조] ep6-2) 원형 큐(Circular Queue)

※ 리스트에 기초한 큐는 ep6) 큐를 보도록 하자

https://claremont.tistory.com/entry/ep6-%ED%81%90Queue

ep6) 큐(Queue)

 

 

 

 

배열로 선형 큐를 구현하면 공간 낭비, 공간의 재사용 불가 등의 문제가 발생한다

그래서 보통은 원형 큐를 사용한다

ㅇ원형 큐(Circular Queue): 선형 큐의 문제점을 보완하기 위한 자료구조

환형 큐라고도 한다

f: front, r: rear

 

빈 큐를 만원 큐로부터 차별하기 위해 '한 개의 빈 방'을 둔다

 

 

 

 

 

문제) 배열로 구성된 원형 큐를 위한 삽입, 삭제 프로그램을 작성하시오.

◦ 주요 전략 : 본 문제의 원형 큐에서는 포화 상태(즉, 만원 상태)와 공백 상태(즉, 빈 상태)를

구분하기 위해 한 자리를 비워둠.

• -  front, rear, 배열의 초기값은 0
• -  삽입 시 rear 값을 하나 증가시킨 후 원소를 큐에 삽입(출력 예시 1 참고)
• -  삭제 시 front 값을 하나 증가시킨 후 front가 가리키는 원소를 삭제
• -  front = rear면 공백 상태로 정의하고, front가 rear보다 하나 앞에 있으면 포화 상태로 정의함

※ 주의 : 교안에서 제시하는 전략에서는 front와 rear가 각각 큐의 맨 앞과 맨 뒤의 원소 위치를 직접 가리키는 방식으로 정의되어 있으나 위 전략은 front가 맨 앞 원소 위치보다 한 셀 앞 위치를 가리키는 방식으로 정의되었다. 교안의 방식으로 변경하여 작성해도 무방하지만, 이 경우 초기 상태에서 맨 처음 삽입되는 위치는 0번이 아니고, 1번이 되어야 함(그렇지 않으면 본 문제의 입출력 예시와 다른 결과가 나올 수 있음).

 

 

 

◦ 입출력 형식:

1) 첫 번째 라인: 양의 정수 q (원형 큐의 크기)

※ q 값에는 제한이 없다. 또한, 동적 할당을 사용할 것.

2) 두 번째 라인: 양의 정수 n (명령의 개수)

3) 세 번째 이후 라인: n개의 명령이 차례로 입력됨.

※ 명령의 종류는 I(삽입), D(삭제), P(출력)

- I 10 : 원형 큐에 원소 10을 삽입(큐 원소는 양의 정수).

- D : 원형 큐에서 원소를 삭제한 후 해당 배열 원소 값을 0으로 치환.

- P : 배열원소 전체를 차례로 화면에 출력(입출력 예시 참조).

※ overflow 발생 시(즉, 포화 상태에서 삽입을 시도한 경우), 화면에 overflow와 배열원소들을 모두 출력하고 프로그램 종료.

※ underflow 발생 시(즉, 공백 상태에서 삭제를 시도한 경우), 화면에 underflow를 출력하고 프로그램 종료.

 

test case

 

 

 

 

(전체코드)

// 주요 전략: 본 문제의 원형 큐에서는 포화 상태와 빈 상태를 구분하기 위해 한 자리를 비워둠
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable:4996)

void initQueue(int* circularQueue);
void enqueue(int* circularQueue, int e);
int dequeue(int* circularQueue);
void print(int* circularQueue);

int g_N; // 원형 큐의 크기
int g_front;
int g_rear;
int g_isError;

int main() {
	int* circularQueue;
	int n; // 입력의 개수
	char cmd;
	int e;

	scanf("%d", &g_N);
	circularQueue = (int*)malloc(g_N * sizeof(int));
	initQueue(circularQueue);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf(" %c", &cmd);
		if (cmd == 'I') {
			scanf(" %d", &e);
			enqueue(circularQueue, e);
		} 
		else if (cmd == 'D') {
			dequeue(circularQueue);
		} 
		else if (cmd == 'P') {
			print(circularQueue);
		}

		if (g_isError == 1) {
			return 0;
		}
	}

	free(circularQueue);
	return 0;
}

void initQueue(int* circularQueue) { // 0으로 모두 초기화
	for (int i = 0; i < g_N; i++) {
		circularQueue[i] = 0;
	}
	g_front = 0;
	g_rear = 0;
	g_isError = 0;
}

void enqueue(int* circularQueue, int e) {
	if (g_front % g_N == (g_rear + 1) % g_N) {
		printf("overflow");
		print(circularQueue);
		g_isError = 1;
		return;
	}
	circularQueue[++g_rear % g_N] = e;
}

int dequeue(int* circularQueue) {
	if (g_front % g_N == g_rear % g_N) {
		printf("underflow");
		g_isError = 1;
		return 0;
	}
	int e = circularQueue[g_front % g_N];
	circularQueue[++g_front % g_N] = 0;
	return e;
}

void print(int* circularQueue) {
	for (int i = 0; i < g_N; i++) {
		printf(" %d", circularQueue[i]);
	}
	printf("\n");
}

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)