원형 큐 (circular queue)

일반적인 큐, 버퍼의 형태와 같이 FIFO의 구조를 가지고 있다. (First In First Out)

입력부와 출력부를 담당하는 Front와 Rear변수도 동일하다. 다만 원형 큐의 경우 일반적인 선형 큐의 문제점을 보완한다.

 

선형적인 큐의 경우 구조상 Dequeue를 할때마다 front가 앞으로 진행되면서 front가 진행된 공간이 활용되지 못하게된다. 이는 굉장히 비효율적인데 원형큐의 경우 큐가 다찼을 경우 혹은 배열이 모두 비워졌을경우, rear를 전체 배열 크기로 %(모듈러)연산을 하여, 다시 처음부터 회귀하여 공간을 활용한다. 

 원형큐에서도 오버플로우 발생 시 오버라이트(배열 제일 첫번째 원소를 덮어쓰며 회귀)를 허용하는 경우와 허용하지 않는 경우가 있는데 이는 원형큐의 용도에 따라 다르다. 

 

선형 큐 

원형 큐  https://www.programiz.com/dsa/

 

원형 큐를 만들때 주의할 점은 다음과 같다.

 

*Queue의 front와 rear는 모두 -1에서 시작한다.

 (추후 큐의 원소가 있는지 없는지는 front가 0인지, -1인지로 구분.

*Enqueue 함수에서는 실행 전 Queue의 Full여부를 확인한다

*Dequeue 함수에서는 실행 전 Queue의 Empty여부를 확인한다.

 

예제코드

 

#include <iostream>
#define SIZE 5
#include <stdio.h>
using namespace std;


struct Queue {
	int Arr[SIZE];
	int front = -1;
	int rear = -1;
};

bool IsFull(Queue* queue)
{
	if (queue->front == 0 && queue->rear == SIZE - 1)
	{
		cout << "Queue Is full!" << endl;
		return true;
	}
	return false;

}


void Enqueue(Queue* queue, int data)
{
	bool FullCheck = IsFull(queue);

	if (FullCheck == false)
	{
		if (queue->front == -1) // When Queue is Empty
		{
			queue->front = 0;
		}
		queue->rear = (queue->rear+1) % SIZE;       //Initialize 'rear' by Modular
		queue->Arr[queue->rear] = data;
		cout << "Enqueue" << endl;
	}

	return;;

	
}

bool IsEmpty(Queue* queue)
{
	if (queue->front ==-1)
	{
		cout << "Queue Is Empty!" << endl;
		return true;
	}
	else
		return false;
}

void Dequeue(Queue* queue)
{
	bool EmptyCheck = IsEmpty(queue);
	if (EmptyCheck == false)
	{
		int data = queue->Arr[queue->front];
		if (queue->front == queue->rear)   //After dequeue, Queue Is Empty. Initialize Queue
		{
			queue->front = -1;
			queue->rear = -1;
		}
		else
		{
			queue->front = (queue->front + 1) % SIZE;
		}
		cout << data << endl;

	}

}

void main()
{
	Queue* queue = new Queue;
	Dequeue(queue);
	Enqueue(queue, 3);
	Enqueue(queue, 4);
	Enqueue(queue, 5);
	Enqueue(queue, 5);
	Enqueue(queue, 5);
	Enqueue(queue, 5);


	Dequeue(queue);

}