원형 큐 Circular Queue

지난 포스트에서 배열을 이용해 큐를 이동하던 중에 원소 이동의 문제로 인해 구현이 실패했었습니다. 그래서 이번엔 순차 자료구조로 그 문제를 해결할 수 있는 방법인 원형 큐를 소개하려고합니다.

---

1. 원형 큐

지난번에 원소 삭제에서 삭제하고 배열 내부의 원소를 하나씩 앞으로 이동하면 큐가 구현되지만 원소 이동이라는 작업이 오버헤드를 일으켜 구현도 사용도 어렵다고 했었습니다. 그래서 나온개념이 배열 내부의 원소가 아닌 front와 rear를 움직이자! 해서 등장한 자료구조가 원형 큐입니다.

이처럼 기존의 리스트같은 구조를 다음과 같이 동그랗게 말은 구조입니다. (실제로 물리적으로는 동그랗지 않습니다)

자세한 것은 구현하면서 살펴보도록 하겠습니다.

 

 

2. 원형 큐 구현

2-1. 큐 생성

큐 생성입니다. 그동안 했던 생성과정과 똑같고 단, front와 rear를 0으로 초기화 해야합니다. 그 이유는 잠시후 인큐에서 설명드리겠습니다.

typedef struct {
	element queue[CIRCULAR_QUEUE_SIZE];
	int front;
	int rear;
}QueueType;

QueueType* createQueue() {
	QueueType* CQ;

	CQ = (QueueType*)malloc(sizeof(QueueType));
	CQ->front = 0;
	CQ->rear = 0;

	return CQ;
}

 

2-2. 인큐

인큐에 들어가기 앞에서 원형 큐의 구조를 설명드리겠습니다. 원형 큐와 일반 큐의 다른점은 front와 rear가 인큐와 디큐에 따라서 이동한다는 점입니다.

위 그림처럼 front와 rear가 인덱스를 나타내는 것은 똑같으나 디큐하면 front+1이 되고, 인큐하면 rear가 +1이 됩니다. 이렇게 되어서 배열 인덱스의 끝에 도달하면 다시 0으로 돌아가는데 이 0으로 돌아가는 연산에는 mod(나머지 연산)을 이용합니다. 물론 if문을 통해서 해결해도 되지만 if문같은 제어문은 실행속도에 영향을 미치기 때문에 mod연산을 이용하는 것이 좋습니다.

예를 들어 위의 큐의 크기는 5입니다. rear가 3번째 칸에 있으므로 인덱스는 2입니다. 그래서 다음 인큐를 위해 (2+1)mod 5를 이용해서 3이란 결과를 얻게 되고 다음 삽입 위치 인덱스는 3이 되게 됩니다. 프론트도 마찬가지 입니다. 이처럼 front와 rear가 마치 빙글빙글 돌면서 구성하고 있기 때문에 마치 원형 같은 구조를 가져 원형 큐라고 이름을 붙였습니다.

만약 큐의 크기 마지막 인덱스인 4라면, (4+1)mod 5 = 0 이라는 연산을 가지고 인덱스 0으로 돌아가게 됩니다. 이해 되셨나요? 그럼 구현을 해보도록 하겠습니다.

void enQueue(QueueType* CQ, element elem) {
	if (isFull(CQ)) {
		return;
	}
	else {
    		//mod연산시 0~스택 크기 -1 사이 값이 나오게 됩니다.
    		//이는 배열의 인덱스와 동일합니다.
		CQ->rear = (CQ->rear + 1) % CIRCULAR_QUEUE_SIZE;
		CQ->queue[CQ->rear] = elem;
	}
}

CQ->rear = (CQ->rear + 1) % CIRCULAR_QUEUE_SIZE;

이 부분이 삽입 위치와 rear를 결정하는 구간입니다. rear에 1을 더하고 스택의 크기로 나눈 나머지 값을 이용합니다.

 

2-3. 디큐

void deQueue(QueueType* CQ) {
	if (isEmpty(CQ)) {
		exit(1);
	}
	else {
		CQ->front = (CQ->front + 1) % CIRCULAR_QUEUE_SIZE;
	}
}

front도 마찬가지로 mod연산을 이용해서 위치를 결정합니다. 원소 삭제는 실제로 이루어 지진 않고 나중에 덮어씌우는 방식으로 구현했습니다.

 

2-4. 피크

element peek(QueueType* CQ) {
	if (isEmpty(CQ)) {
		exit(1);
	}
	else {
		return CQ->queue[CQ->front + 1] % CIRCULAR_QUEUE_SIZE;
	}
}

마찬가지로 피크도 front값을 반환하면 되는데 똑같이 mod 연산을 통해 front의 위치를 찾고 해당 인덱스의 요소 값을 반환합니다.

---

원형 큐는 오버헤드가 큰 연산 대신 간편하게 해결할 수 있는 방식이었습니다. 어려운것 같지만 잠깐만 생각해본다면 전혀 어렵지 않음을 알 수 있습니다.

 

https://github.com/Bam-j/DataStructure/blob/main/DataStructure/CircularQueue.c

GitHub - Bam-j/DataStructure: 블로그와 함께 가는 자료구조