[자료구조] 큐 - 02 . 순환큐

[순환큐]

[배열로 큐를 구현했을때 문제점]

=>큐를 배열로 구현해야 한다면 ? 전단을 제거 후 나머지 요소를 한칸씩 앞으로 옮기는 비용이 들 것이다 . 

 

 

[해결과 문제]

=>전단을 가리키는 변수를 도입하여 배열 내의 요소를 옮기는 대신 변경된 전단의 위치만 관리한다 .

=>후단을 가리키는 변수 역시 도입하여 변경되는 후단의 위치를 관리한다 . (후단의 위치는 실제 후단의 위치 +1)

=>해당 방식 역시 제거 연산을 할 수록 큐의 가용 용량이 줄어드는 문제가 있다.

 

[순환큐]

=>배열의 마지막 요소가 후단이었을때 , 데이터를 삽입하면 후단은 배열의 첫번째 요소로 변경시킨다 .

이렇게 시작과 끝을 연결해서 순환하도록 고안된 큐를 "순환큐"라고 한다.

=>그러나 이렇게 끝난다면 비어있는 상태 , 가득 찬 상태를 구분 못 할 것이다 .

[해결]

=>큐 배열을 생성시 실제 용량보다 1 크게 만들어 전단 , 후단 사이를 비우는 것이다 .

=>비어있다면 전단,후단은 같은 곳을 가리키고 큐가 가득 차 있다면 후단이 전단보다 1 작은 값을 가진다.

[순환큐 기본 연산 구현]

[순환큐의 선언]

=>순환큐의 노드는 다음과 같은 구조체로 표현된다 .

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}Node;

 

=>순환큐는 다음과 같은 구조체로 표현된다 .

typedef struct tagCircularQueue
{
	int Capacity;	//용량
    int Front;		//전단의 인덱스
    int Rear;		//후단의 인덱스
    Node * Nodes	//노드 배열
}CircularQueue;

[순환큐의 생성]

=>Capacity에는 배열의 크기 , 즉 큐의 용량이 저장되는데 해당 값은 실제 용량보다 1 작다

(공백/포화 상태의 구분을 위한 더미노드가 있기때문)

=>Front 는 전단 / Rear는 후단의 위치를 가리키며 해당 값은 실제 메모리 주소가 아닌 배열 내의 인덱스이다 .

(Rear는 실제 후단보다 1 더 큰 값을 가진다)

void CQ_CreateQueue(CircularQueue** Queue , int Capacity)
{
	//큐를 자유 저장소에 생성
    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
    //입력된 Capacity +1 만큼의 노드를 자유 저장소에 생성
    (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));
    
    (*Queue)->Capacity  = Capacity;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

[순환큐의 삭제]

=>배열을 자유 저장소에서 제거 후 순환 큐를 제거

void CQ_DestroyQueue(CircularQueue * Queue)
{
    free(Queue->Nodes);
    free(Queue);
}

[ 삽입 연산 (Enqueue) ]

=>Rear값이 Capacity과 같다면 배열의 끝에 도달 했다는 뜻이다 .

void CQ_Enqueue( CircularQueue * Queue , ElementType Data )
{
	int Position =0;
    
    //배열의 끝까지 후단이 도달했다면
    if(Queue->Rear==Queue->Capacity)
    {
    	Position = Queue->Rear;
        Queue->Rear=0;
    }
    else
    {
    	Position=Queue->Rear++;
    }
    Queue - > Node[Position] = Data;
}

[ 제거 연산 (Dequeue) ]

=>Front 값이 Capacity과 같다면 배열의 끝에 도달 했다는 뜻이다 .

ElementType CQ_Dequeue ( CircularQueue* Queue)
{
	int Position = Queue -> Front;
    
    //배열에 끝에 도달 했다면
    if(Queue->Front == Queue -> Capacity)
    {
    	Queue -> Front =0 ;
    }
    else
    {
    	Queue -> Front++;
    }
    
    return Queue->Modes[Position].Data;
}

[ 공백 상태 확인 ]

=>전단 , 후단의 값이 같으면 공백 상태이다

int CQ_IsEMpty(CircularQueue * Queue)
{
	return (Queue->Front == Queue -> Rear );
}

[ 포화 상태 확인 ]

=>전단이 후단 앞에 위치한다면 후단과 전단의 차가 큐의 용량과 동일한지 확인한다

=>전단이 후단 뒤에 위치한다면 Rear +1 한 값이 Front와 같은지 확인한다 .

int CQ_IsFull(CirculatQueue * Queue)
{
    if(Queue->Front < Queue -> Rear)
    {
    	return Queue->Rear - Queue ->Front ==Queue-> Capacity
    }
    else
    {
    	return (Queue->Rear+1) == Queue->Front
    }
	
}

[순환큐 예제 프로그램]

[CQ.H]

#ifndef CQ
#define CQ

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

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}Node;

typedef struct tagCircularQueue
{
	int Capacity;
	int Front;
	int Rear;
	Node* Nodes;
}CircularQueue;

//생성
void CQ_CreateQueue(CircularQueue ** Queue , int Capacity);
//삭제
void CQ_DestroyQueue(CircularQueue* Queue);
//삽입
void CQ_Enqueue(CircularQueue* Queue, ElementType Data);
//제거
ElementType CQ_Dequeue(CircularQueue* Queue);
//비었는지
bool CQ_isEmpty(CircularQueue* Queue);
//사이즈
int CQ_GetSize(CircularQueue* Queue);
//가득 찼는지
bool CQ_isFull(CircularQueue* Queue);



#endif // !CQ

[CQ.cpp]

#include "CQ.h"
//생성
void CQ_CreateQueue(CircularQueue** Queue, int Capacity)
{
	(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
	(*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1));
	(*Queue)->Capacity = Capacity;
	(*Queue)->Front = 0;
	(*Queue)->Rear = 0;
}
//삭제
void CQ_DestroyQueue(CircularQueue* Queue)
{
	free(Queue->Nodes);
	free(Queue);
}
//삽입
void CQ_Enqueue(CircularQueue* Queue, ElementType Data)
{
	int Position = 0;
	if (Queue->Rear == Queue->Capacity)
	{
		Position = Queue->Rear;
		Queue->Rear = 0;
	}
	else
	{
		Position = Queue->Rear++;
	}
	Queue->Nodes[Position].Data = Data;
}
//제거
ElementType CQ_Dequeue(CircularQueue* Queue)
{
	int Position = Queue->Front;
	if (Queue->Front == Queue->Capacity)
	{
		Queue->Front = 0;
	}
	else
	{
		Queue->Front++;
	}
	return Queue->Nodes[Position].Data;
}
//비었는지
bool CQ_isEmpty(CircularQueue* Queue)
{
	return Queue->Front == Queue->Rear;
}
//사이즈
int CQ_GetSize(CircularQueue* Queue)
{
	if (Queue->Front <= Queue->Rear)
	{
		return Queue->Rear - Queue->Front;
	}
	else
	{
		return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
	}
}
//가득 찼는지
bool CQ_isFull(CircularQueue* Queue)
{
	if (Queue->Front < Queue->Rear)
	{
		return Queue->Rear - Queue->Front == Queue->Capacity;
	}
	else
	{
		return (Queue->Rear + 1) == Queue->Front;
	}
}

[test.cpp]

#include "CQ.h"

int main(void)
{
	int i;
	CircularQueue* Queue;

	CQ_CreateQueue(&Queue, 10);

	CQ_Enqueue(Queue, 1);
	CQ_Enqueue(Queue, 2);
	CQ_Enqueue(Queue, 3);
	CQ_Enqueue(Queue, 4);

	for (i = 0; i < 3; i++)
	{
		printf("Deque : %d ,", CQ_Dequeue(Queue));
		printf("Front : %d , Rear : %d\n", Queue->Front, Queue->Rear);
	}

	i = 100;

	while (CQ_isFull(Queue)==false)
	{
		CQ_Enqueue(Queue, i++);
	}

	printf("Capacity : %d , Size : %d\n\n", Queue->Capacity, CQ_GetSize(Queue));

	while (!CQ_isEmpty(Queue))
	{
		printf("Deque : %d ,", CQ_Dequeue(Queue));
		printf("Front : %d , Rear : %d\n", Queue->Front, Queue->Rear);
	}

	CQ_DestroyQueue(Queue);
	return 0;

}