[C++] 순환 큐, 원형 큐 구현

1. 이것은 무엇인가?

- 큐는 선입선출의 특징을 가지고 있다. 그 특징을 구현하는데 문제점인 인덱스 변경으로 인한 배열 사용 범위가 애매해지는 것이 있다. 이를 보완하는 순환 큐를 이해해보고자 구현해보았다.

 

2. 순환 큐의 구조

- 순환 큐를 도식화하면 이렇게 생겼다.

- 큐는 선입선출의 특징을 가지고 있어 데이터를 하나 꺼낸다고 한다면, 가장 앞에 있는 인덱스를 비울 수 없기에 그 다음 데이터를 가진 인덱스로 바꿀 것이다.

- 이 때 모든 인덱스를 하나씩 땡겨서 그 빈자리를 채우는 것이 아니라 가리키는 인덱스를 옮기는 것이어서 공간에 대한 애매함이 있다.

- 이를 보완하는 것이 순환 큐인 것이다. 마치 마지막 인덱스의 다음 인덱스는 다시 처음 인덱스인 것으로 논리적으로 구현한 것이다.

- front는 데이터 모음의 가장 처음을 가리키는 인덱스이다. rear는 데이터 모음들의 가장 마지막 인덱스의 그 다음 인덱스이다.

- 여기서 rear가 가리키는 인덱스는 아무 데이터도 저장하지 않는 공간으로 사용할 것이다. 이것으로 Empty 함수와 Full 함수의 조건문을 달리하는 척도로 사용할 것이다.

- 이 front와 rear를 이용해 데이터의 추가, 제거 등을 구현할 것이다.

 

3. 요구 사항

- 순환 큐의 데이터 추가

- 순환 큐의 데이터 제거

- 순환 큐의 데이터 유무 확인

- 순환 큐의 데이터 포화 상태 확인

- 순환 큐의 모든 데이터 출력

 

4. 함수 설명

- 이 순환 큐는 배열 기반으로 구현했다.

 4-1. Empty()

bool CircularQueue::Empty()
{
	bool result = false;
	if (m_front == m_rear) result = true;
	return result;
}

- 순환 큐의 데이터가 없는지 확인하는 함수이다.

- 데이터가 아예 없다면 front와 rear의 값이 같을 것이다. 그럴 경우 true를 반환한다.

 

 4-2. Full()

bool CircularQueue::Full()
{
	bool result = false;
	if (m_front < m_rear)
	{
		result = m_front == (m_rear + 1) % MAX_SIZE;
	}
	else if (m_front > m_rear)
	{
		result = m_front == (m_rear + 1);
	}
	return result;
}

- 순환 큐가 꽉 찼는지 확인하는 함수이다.

- 뒤에 있을 push와 pop 함수로 인해 front와 rear가 가리키는 인덱스가 뒤바뀔 수 있다. 다시 말해 front가 뒤의 인덱스를 가리키고 rear가 앞의 인덱스를 가리킬 수 있다는 것이다.

- rear가 front보다 앞에 있는 경우에는 가장 마지막의 다음 인덱스를 가리키는 rear에 1을 더 할 때, front와 같다면 그것은 데이터가 가득찼다는 의미이니 true를 반환한다.

- front가 rear보다 앞에 있는 경우에는 rear에 1을 더한 값에 배열의 최대 크기의 나머지 연산을 한다. 이 이유는 배열의 최대 크기보다 하나 더 크다면 그것은 첫 인덱스를 의미하기 때문이다. 만약 그 값이 front와 같다면 true를 반환한다.

 

 4-3. Push(int)

void CircularQueue::Push(int data)
{
	if (Full())
	{
		cout << "Full" << endl;
		return;
	}
	m_rear = (m_rear + 1) % MAX_SIZE;
	m_data[m_rear] = data;
}

- 순환 큐의 데이터 추가를 구현한 함수이다.

- 만약 데이터가 꽉찼다면 함수를 종료한다.

- 그것이 아니라면 rear를 최대 배열 크기를 고려한 다음 인덱스를 저장한다.

- 그리고 그 인덱스에 데이터를 저장한다.

 

 4-4. Pop()

int CircularQueue::Pop()
{
	if (Empty())
	{
		cout << "Empty" << endl;
		return 0;
	}
	m_front = (m_front + 1) % MAX_SIZE;
	int data = m_data[m_front];
	m_data[m_front] = NULL;
	return data;
}

- 순환 큐의 데이터 제거를 구현한 함수이다.

- 만약 데이터가 없다면 함수를 종료한다.

- 그것이 아니라면 front에 최대 배열 크기를 고려한 front의 다음 인덱스를 저장한다. 이는 제거할 인덱스를 가리키기 위한 구문이다.

- 그리고 해당 인덱스의 값을 NULL로 대입한다.

- 만약 제거한 데이터가 필요할 경우를 위해 반환하게 구현했다.

 

 4-5. Print()

void CircularQueue::Print()
{
	if (!Empty())
	{
		for (int i = (m_front + 1) % MAX_SIZE; i != m_rear + 1; i = (i + 1) % MAX_SIZE)
		{
			cout << m_data[i] << " ";
		}
	}
	else
	{
		cout << "Empty Queue. Plz input value." << endl;
	}
	cout << endl;
}

- 순환 큐의 출력을 구현한 함수이다.

- 만약 데이터가 없지 않다면 반복문을 수행하여 값을 출력한다.

 

5. 코드

 5-1. Header.h

#pragma once
#include<iostream>
using namespace std;

 5-2. CircularQueue.h

#pragma once
#include"Header.h"

const int MAX_SIZE = 10;

class CircularQueue
{
private:
	int m_data[MAX_SIZE];
	int m_front;
	int m_rear;
public:
	CircularQueue();

	void Print();
	void Push(int);
	int Pop();

	bool Full();
	bool Empty();
};

 5-3. CircularQueue.cpp

#include "CircularQueue.h"

CircularQueue::CircularQueue() : m_front(MAX_SIZE - 1), m_rear(MAX_SIZE - 1)
{
	for (int i = 0; i < MAX_SIZE; i++)
	{
		m_data[i] = 0;
	}
}

void CircularQueue::Print()
{
	if (!Empty())
	{
		for (int i = (m_front + 1) % MAX_SIZE; i != m_rear + 1; i = (i + 1) % MAX_SIZE)
		{
			cout << m_data[i] << " ";
		}
	}
	else
	{
		cout << "Empty Queue. Plz input value." << endl;
	}
	cout << endl;
}

void CircularQueue::Push(int data)
{
	if (Full())
	{
		cout << "Full" << endl;
		return;
	}
	m_rear = (m_rear + 1) % MAX_SIZE;
	m_data[m_rear] = data;
}

int CircularQueue::Pop()
{
	if (Empty())
	{
		cout << "Empty" << endl;
		return 0;
	}
	m_front = (m_front + 1) % MAX_SIZE;
	int temp = m_data[m_front];
	m_data[m_front] = NULL;
	return temp;
}

bool CircularQueue::Full()
{
	bool result = false;
	if (m_front < m_rear)
	{
		result = m_front == (m_rear + 1) % MAX_SIZE;
	}
	else if (m_front > m_rear)
	{
		result = m_front == (m_rear + 1);
	}
	return result;
}

bool CircularQueue::Empty()
{
	bool result = false;
	if (m_front == m_rear) result = true;
	return result;
}