원형 큐 (배열로 구현)

원형 큐 기본 설명

선형 큐의 단점을 되새겨 보면 dequeue() 함수를 실행함으로서 발생하는 사용할 수 없는 공간들이 생겼었다. 즉 그 공간들을 재활용할 수 있는 코드를 구현하지 않는 이상 메모리 누수가 생긴 것이다. 그래서 이런 단점을 보완한 것이 원형 큐이다. 

 

이를 구현한 방법은 예시로 enqueue() 함수를 보이겠다.

void enqueue(int data){
    if(full())
    {
        printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
        return;
    }
    else
    {
         rear = (rear+1)%MAX;
         queue[rear]=data;
    }
}

위의 함수를 보면 큐가 포화상태가 아닐 시, rear은 rear+1의 MAX로 나눈 나머지 값이 대입된다. dequeue() 함수도 이와 마찬가지로 front=(front+1)%MAX로 표현한다. 이것이 의미하는 바는 rear와 front 둘다 각자 위치가 아닌 1 증가된 위치에서 데이터를 삽입, 제거하겠다는 뜻이다.

 

하나씩 증가하면서 %MAX로 나눈 나머지 값이 올라가다 보면, 결국 나머지가 0으로 돌아오게 돼있다. 그러면, 선형 큐와 달리 메모리 누수가 일어나지 않고 계속 빈 공간을 채우면서 돌아가면서 쓸 수 있는 것이다. 물론 여기서 구현한 예는 포화 상태와 공백 상태를 구분하기 위해 front가 rear보다 하나 앞에 위치할때 포화 상태로 지정했으므로 빈 공간이 하나 생기긴 한다. 다른 방식으로 구현하면 이 공간을 채울 수 있지만, 더 많은 코드를 써야해서 귀찮기 때문에 우린 이 방식을 계속 쓸 것이다.

원형 큐의 동작 상태 코드

#include <stdio.h>
#include <string.h>
#define MAX 5

int front;
int rear;
int queue[MAX];
 
void init_queue() //선형 큐와의 차이점: front와 rear을 0으로 초기화한다.
{
    rear = 0;
    front = 0;
}

int empty(void){
    return (front==rear); //front와 rear가 같으면 큐는 비어있는 상태 
}
int full(void){
    return ((rear+1)%MAX==front); //(rear+1)%MAX가 front와 같으면 큐는 가득차 있는 상태 
}
void enqueue(int data){
    if(full())
    {
        printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
        return;
	}
    else
    {
    	rear = (rear+1)%MAX;
        queue[rear]=data;
    }

}
int dequeue(){
    if(empty())
    	return -1;
    else{
        front = (front+1)%MAX;
        return queue[front];
    }
}
 
int main()
{    
    char Get_Com[10];
	int N,pushnum;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"enqueue")==0)
		{
			scanf("%d",&pushnum);
			enqueue(pushnum);
		}
		else if(strcmp(Get_Com,"dequeue")==0)
			printf("%d\n",dequeue());
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty());
		else if(strcmp(Get_Com,"full")==0)
			printf("%d\n",full());
	}
    return 0;
}