[자료구조] 환형 큐(Circular Queue) [C++]

환형큐(Circular Queue)의 개념

우선 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO구조를 가진 자료구조이다. 하지만 큐는 배열로 구현했을경우 메모리 낭비가 생긴다. 이를 보완하기 위해 생긴것이 환형큐 이다.

 

큐(Queue)설명 -  2020/07/12 - [프로그래밍/자료구조] - [자료구조]큐 Queue

[자료구조]큐 Queue

환형큐는 '(index + 1) % 배열사이즈' 를 이용하여 배열의 범위를 벗어나지 않게 하여 낭비되는 메모리를 재사용하는 자료구조 이다.

 

큐에서는 꽉 찬 상태를 rear가 배열 사이즈를 넘었는지 확인했었고, 비어있는 상태를 front와 rear가 같은 곳을 가리키는지를 확인했었다. 하지만 환형 큐에서는 비어있는 상태는 front와 rear가 같은 곳에 있는지 확인하는 것이고, 꽉 차있는 상태는 rear가 front 바로 뒤에 있는지 확인하는 것이다. 이렇게 되면 한 칸을 빈 공간으로 두어 완충지대로 사용하여야 한다. 그렇지 않으면 비어있는 상황이고 꽉 차 있는 상황을 알 수 없기 때문이다.

 

환형큐(Circular Queue) 기본 구조

1. 초기상태

front와 rear모두 0을 초기값으로 가진다.

2-1. EnQueue

Enqueue하여 데이터가 삽입되고 rear가 1 증가한다.

2-2 Enqueue

2-3. Enqueue

2-4 7번째 Enqueue

이렇게 되면 위에서 설명한대로 가득 차 있는 상태가 된다. 7번 인덱스는 완충지대 역할을 하고, 비어있는 공간으로 남게 된다.

3-1 Dequeue

데이터를 삭제하고 Front가 앞으로 이동하여 한칸의 공간이 남게 된다. 이때 Enqueue하면 7번인덱스에는 데이터가 추가되고, Rear는 0을 가르키며 다시 꽉 찬 상태가 되는것이다.

 

3-2 Enqueue

환형큐(Circular Queue)구현

#include <iostream>

using namespace std;

#define SIZE 10

int list[SIZE];
int front = 0;
int rear = 0;

void Enqueue(int);
int Dequeue();

int main()
{
	cout << "(1) Enqueue. (2) Dequeue (3) Print (4) Exit" << endl;
	int menu;
	cin >> menu;

	while (menu != 4)
	{
		switch (menu)
		{
		case 1:
		{
			int temp;
			cout << "Enter a enqueue value:";
			cin >> temp;

			Enqueue(temp);
		}
		break;
		case 2:
		{
			cout << Dequeue() << "is dequeued" << endl;
		}
		break;
		case 3:
		{
			int idx = front;
			while (rear != idx)
			{
				cout << "[" << idx + 1 << "]" << list[idx] << " ";
				idx = (idx + 1) % SIZE;
			}
			cout << endl;
		}
		break;
		default:
			cout << "Wrong Input!" << endl;
		}

		cout << "(1) Enqueue. (2) Dequeue (3) Print (4) Exit" << endl;
		cin >> menu;
	}



}

void Enqueue(int val)
{
	if (front == (rear + 1) % SIZE)
		return;

	list[rear++] = val;
	rear %= SIZE;
}

int Dequeue()
{
	if (rear == front)
		return -1;

	int r = list[front];
	front = (front + 1) % SIZE;
	return r;
}