원형큐 (Circular Queue)

원형큐 (Circular Queue)

선형큐에서 삽입과 삭제를 하다보면 rear가 배열의 끝에 도달하게되는데 이때 더이상 삽입이 불가능해진다.

따라서 이럴때는 배열의 요소들을 왼쪽으로 이동시켜줘야하는 불편함이 있다.

이를 해결하기 위해 고안된 것이 바로 원형큐 (Circular Queue)이다.

원형큐는 배열의 끝과 처음이 이어져있다고 생각하면 된다.

front가 -1로 초기화되는 선형큐와는 다르게

front와 rear가 처음에는 모두 0으로 시작하고 따라서 공백 검사 알고리즘도 if(front==rear)이다.

포화 검사 알고리즘은 선형큐와 같다. if(rear==MAX_SIZE_QUEUE-1)이다.

다음은 원형큐의 삽입, 삭제 알고리즘이다.

삽입 알고리즘

• enqueue(Q,x):
  • rear<-(rear+1) % MAX_QUEUE_SIZE;
  • Q[rear]<-x;

삭제 알고리즘

• dequeue(Q):
  • front<-(front+1) % MAX_QUEUE_SIZE;
  • return Q[front];

먼저 삽입이나 삭제를 하기전에 front와 rear를 원형 회전시켜서 하나 증가시키고 증가된 위치에 데이터를 삽입, 삭제한다.

  

    
    
    
    
  
front<-(front+1) % MAX_QUEUE_SIZE;
rear<-(rear+1) % MAX_QUEUE_SIZE;

위 식에서 사용되는 나머지 연산자 %를 이용하여 원형 회전시킬 수 있다.

식에 따라 front와 rear값은 (MAX_QUEUE_SIZE-1)에서 하나 증가되면 0으로 바뀌는것을 확인 할 수 있다.

원형큐의 구현

front는 첫 번째 요소 하나 앞, rear는 마지막 요소를 가리킨다.

삽입 시에는 rear를 먼저 하나 증가하고 -> 증가된 위치에 삽입을 한다.

삭제 시에는 front를 먼저 하나 증가하고 -> 증가된 위치에서 데이터를 꺼내온다.

공백 상태 검출은 front와 rear가 같으면 TRUE

포화 상태 검출은 (rear+1) % MAX_QUEUE_SIZE가 front와 같으면 포화 상태라고 판단한다. (보통 둘다 0)

  

    
    
    
    
  
#include <stdio.h>
#include <stdlib.h>

// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
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->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("%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("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
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)
{
	QueueType queue;
	int element;

	init_queue(&queue);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&queue))
	{
		printf("정수를 입력하시오: ");
		scanf("%d", &element);
		enqueue(&queue, element);
		queue_print(&queue);
	}
	printf("큐는 포화상태입니다.\n\n");

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&queue))
	{
		element = dequeue(&queue);
		printf("꺼내진 정수: %d \n", element);
		queue_print(&queue);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}