Circular Queue

Circular Queue 는 원형 큐로 일반적인 선형 큐의 단점을 보완한 방식이다.

선형 큐의 단점은 front가 증가하여 Size 에 도달했을때 다시 빈 공간을 활용할 수 없다는 단점이 있었다.

원형 큐에서는 원형으로 배열 요소를 접근하게 하여 빈 공간에 다시 재 할당할 수 있게 한다.

이런 원형큐의 장점이 있는 반면 결국 한정된 사이즈 안에서만 가능하다는 단점이 존재한다. LinkedList 로 구현하면 이러한 크기제한이 풀리게 된다.

 

원형 큐의 구현은 (rear + 1) % QUEUE_SIZE 의 방식을 사용하게 되는데 결국 rear 과 front 가 계속 증가해도 QUEUE_SIZE 로 나머지를 구하기 때문에 결국 QUEUE_SIZE 에 한정된 요소 안에서 반복되게 된다.

본인은 배열의 0번째를 빈 공간으로하였고 1부터 데이터를 넣었다.

enQueue 와 deQueue 가 될때 마다 rear, front 값이 계속 증가 할 수 있기 때문에 모든 요소에 % QUEUE_SIZE 를 하지 않으면 메모리 할당을 받지 않는 주소에 접근할 수 있다.. 그렇게 되면 당연히 쓰레기값이 무한정나오거나 .. 이상한 루프에 빠질 수 있다. 실수 하지 말기..

 

아래는 이전의 선형 큐에서 나머지 연산자를 활용하여 만들어본 Circular Queue 이다.

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

#define QUEUE_SIZE 10

typedef struct
{
	char data[QUEUE_SIZE];
	int front, rear;
}CircularQueue;

CircularQueue *CreateQueue()
{
	CircularQueue *Q = (CircularQueue *)malloc(sizeof(CircularQueue));
	Q->front = 0;
	Q->rear = 0;

	return Q;
}

bool Empty(CircularQueue *Q)
{
	if (Q->rear == Q->front)
	{
		printf("Queue Buffer is Empty\n");
		return 1;
	}
	else
		return 0;
}

bool Full(CircularQueue *Q)
{
	int a = (Q->rear + 1) % QUEUE_SIZE;
	int b;
	if ((Q->rear+1) % QUEUE_SIZE == Q->front)
	{
		printf("Queue Buffer is Full\n");
		return 1;
	}
	else
		return 0;
}

void PrintQueue(CircularQueue *Q)
{
	if (Empty(Q))
	{
		printf("Print Out\n");
		return;
	}

	int i = (Q->front + 1) % QUEUE_SIZE;
	int j = (Q->rear + 1) % QUEUE_SIZE;
	printf("Queue Print : ");
	while (i != j)
	{
		printf("%3c", Q->data[i]);
		i = (i + 1) % QUEUE_SIZE;
	}
	printf("\n");
}

void enQueue(CircularQueue *Q, char strdata)
{
	if (Full(Q)) return;
		
	Q->rear = (Q->rear + 1) % QUEUE_SIZE;
	Q->data[Q->rear] = strdata;
}

void deQueue(CircularQueue *Q)
{
	if (Empty(Q)) return;
	
	Q->front = (Q->front + 1) % QUEUE_SIZE;
	Q->data[Q->front];
}

int main(void)
{
	CircularQueue *Q = CreateQueue();

	enQueue(Q, 'A');
	enQueue(Q, 'B');
	enQueue(Q, 'C');
	enQueue(Q, 'D');
	PrintQueue(Q);

	enQueue(Q, 'E');
	enQueue(Q, 'F');
	enQueue(Q, 'G');
	enQueue(Q, 'H');
	PrintQueue(Q);

	enQueue(Q, 'I');
	PrintQueue(Q);
	
	enQueue(Q, 'J');
	PrintQueue(Q);

	deQueue(Q);
	deQueue(Q);
	deQueue(Q);
	deQueue(Q);
	deQueue(Q);
	deQueue(Q);
	PrintQueue(Q);

	enQueue(Q, 'A');
	enQueue(Q, 'B');
	enQueue(Q, 'C');
	enQueue(Q, 'D');
	enQueue(Q, 'E');
	enQueue(Q, 'F');
	PrintQueue(Q);

	free(Q);
	getchar();

	return 0;
}

Circular Queue 구현 결과