[자료구조] 배열로 구현한 원형 큐(Circular Queue) - C/C++

<큐>

- 선형구조로 자료를 차례대로 저장하고, 가장 먼저 들어간 자료가 가장 먼저 나오는 FIFO(First In First Out, 선입선출)의 특성을 지닌다.

- 자료 반환은 큐의 제일 앞(front)에서만 가능하고 자료 추가는 큐의 제일 끝(rear)에서만 가능하다.

 

--> 선형 큐의 단점 : dequeue가 실행되고 생긴 front 앞의 빈 노드가 있어도, rear가 이동할 오른쪽에 빈 노드가 없으면 overflow현상이 발생한다.

                            = 선형 큐는 메모리 비효율적이다.

--> 선형 큐의 대안으로 원형 큐가 제시되었다.

 

<원형 큐>

- rear의 오른쪽과 front의 왼쪽을 (가상적으로) 연결시켜, rear의 오른쪽으로 front의 왼쪽 빈 노드를 사용할 수 있도록한다.

- rear 노드 이동에 mod 연산자를 이용한다. --> rear = (rear+1) % capacity

 

<원형 큐 자료> * 본 게시물에서의 큐는 배열로 구현하였다.

 

1. 노드 : 자료구조에 저장할 데이터를 가진 각각의 원소들을 구조체 Node로 선언한다.  

typedef struct Node
{
	void *data;
} Node;

 

2. 큐 : 구조체 CQueue을 선언한다.

- 배열의 주소를 가지는 CQarray 노드 포인터가 있다.

- front(자료를 반환하는 큐의 제일 앞), rear(자료를 추가하는 큐의 제일 끝) 인덱스를 저장하는 정수형 변수가 있다.

- 큐의 최대 원소 개수를 나타내는 capacity가 잇다.

typedef struct CQueue
{
	Node *CQarray;
	int front;
	int rear;

	int capacity;
	int datasize;
} CQueue;

 

< 원형 큐 연산 >

1. CreateCQueue: 원하는 자료형의 데이터를 담은 노드를 저장할 수 있는 배열을 capacity 크기만큼 동적으로 생성

  1-1. CircularQueue.c  

void CreateCQueue(CQueue *cqueue, int capacity, int datasize)
{
	int i;

	cqueue->CQarray = (Node *)malloc(sizeof(Node)*capacity);

	for (i = 0; i<capacity; i++)="" {="" (cqueue-="">CQarray + i)->data = malloc(sizeof(datasize));
	}
	cqueue->front = 0;
	cqueue->rear = 0;

	cqueue->capacity = capacity;
	cqueue->datasize = datasize;

	cqueue->isEmpty = isEmpty;
	cqueue->isFull = isFull;
	cqueue->Enqueue = Enqueue;
	cqueue->Dequeue = Dequeue;
	cqueue->DeleteQueue = DeleteQueue;
}

 

2. Enqueue : 큐의 rear 위치에 새로운 노드를 추가 

   Dequeue : 큐의 front 위치에 있는 노드를 제거한 뒤 데이터를 인자에 복사. 성공 여부를 반환

- 원형 큐에서는 변수 rear의 값을 1 증가시키고, 큐의 크기로 나머지 연산을 실시한다. front노 같은 연산으로 계산한다.

   → 배열의 앞부분에 있는 빈 노드를 연속해서 사용할 수 있다.

  2-1. CircularQueue.c

int Enqueue(CQueue *cqueue, void *endata)
{
	if (cqueue->isFull(cqueue))
	{
		return FALSE;
	}
	else
	{
		Node *enNode = cqueue->CQarray + ((cqueue->rear) % (cqueue->capacity));
		memcpy(enNode->data, endata, cqueue->datasize);
		cqueue->rear++;
		return TRUE;
	}
}

int Dequeue(CQueue *cqueue, void *dedata)
{
	if (cqueue->isEmpty(cqueue))
	{
		return FALSE;
	}
	else
	{
		Node *deNode = cqueue->CQarray + ((cqueue->front) % (cqueue->capacity));
		memcpy(dedata, deNode->data, cqueue->datasize);
		cqueue->front++;
		return TRUE;
	}
}

 

3. isFull : 큐가 가득 찼는지 판단

- 큐가 가득 찼을 때, 즉 front와 rear의 차이가 (큐의 크기-1) 와 같으면 TRUE를 반환

  3-1. CircularQueue.c

int isFull(CQueue *cqueue)
{
	if ((cqueue->rear) - (cqueue->front) == (cqueue->capacity) - 1)
		return TRUE;
	else
		return FALSE;
}

 

※ 전체 소스 GitHub : https://github.com/waves123/CircularQueue

 

 

자료구조 더보기

2017/07/20 - [자료구조] - [자료구조] 연결리스트로 구현한 큐(Linked Queue) - C언어

2017/07/02 - [자료구조] - [자료구조] 연결리스트(Linked List) - C언어

2017/07/15 - [자료구조] - [자료구조] 스택(Stack) - C/C++