원형 큐(Circular Queue)

  스택 

순차 자료구조를 사용한 큐는 데이터를 인출할 때마다 모든 데이터를 이동시켜야 하는 오버헤드가 발생한다. 이를 방지하기 위한 자료구조가 원형 큐이다.

 

원형 큐는 기본적으로 시작 지점과 끝 지점을 연결해 계속해서 이어질 수 있도록 만든 것으로 논리적 구조는 다음과 같다.

 

이때 데이터를 삽입하는 위치와 인출하는 위치는 다음과 같다.

• 삽인 위치 front = (front + 1) % n
• 삭제 위치 rear = (rear + 1) % n

 

  큐 구현 준비 

큐는 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다.

 

구현에 필요한 메서드 및 속성은 다음과 같다.

• 생성자
  • CircularQueue() 비어있고 기본 초기 용량을 가지는 인스턴스 생성
  • CircularQueue(CircularQueue&) 다른 CircularQueue 데이터로 인스턴스 생성
  • CircularQueue(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성
• 속성 
  
  • Count CircularQueue에 포함된 데이터의 개수
• 메서드 
  • Enqueue(data) CircularQueue의 끝 부분에 데이터를 저장
  • Peek() CircularQueue의 시작 부분의 데이터를 제거하지 않고 반환
  • Dequeue() CircularQueue의 시작 부분의 데이터를 제거하고 반환
  • Clear() 저장되어 있는 모든 데이터 삭제
  • Contains(data) 데이터가 저장되어 있는지 여부 확인

 

원형 큐 구현

CircularQueue를 구현한다.

 

CircularQueue.h

#pragma once
#include <xutility>
#include <iostream>

class CircularQueue
{
public:
#pragma region 생성자
	CircularQueue(size_t capacity = 10);
	CircularQueue(const CircularQueue& other);
#pragma endregion

#pragma region 속성
	const size_t Capacity() { return m_capacity; }
	const size_t Count() { return m_count; }
	int& Item(size_t index) {
		if (index >= m_count)
		{
			throw std::out_of_range("index");
		}
		return m_items[index];
	}
#pragma endregion

#pragma region 메서드
	void Enqueue(int value);

	int Peek();
	int Dequeue();
	void Clear();

	bool Contains(int value);
#pragma endregion

#pragma region Class Util
	bool IsNeedToResize();
	void Resize();
#pragma endregion

private:
#pragma region 변수
	size_t m_capacity;
	size_t m_count;
	int* m_items;

	size_t m_front;
	size_t m_rear;
#pragma endregion
};

 

생성자 구현

기본 생성자와 Stack을 인자로 받는 복사 생성자를 구현한다.

 

Queue.cpp

/// <summary>
/// 비어있고 초기 용량을 가지는 CircularQueue를 생성한다.
/// </summary>
/// <param name="capacity">생성할 공간의 크기(기본: 10)</param>
CircularQueue::CircularQueue(size_t capacity)
	: m_capacity(capacity), m_count(0), m_front(0), m_rear(0)
{
	if (capacity < 0)
	{
		throw std::out_of_range("capacity");
	}
	m_items = new int[m_capacity] {0};
}

/// <summary>
/// 다른 CircularQueue와 동일한 값을 가지는 CircularQueue를 생성한다.
/// </summary>
/// <param name="other">기준이 될 CircularQueue</param>
CircularQueue::CircularQueue(const CircularQueue& other)
	: CircularQueue(other.m_capacity)
{
	m_count = other.m_count;
	for (size_t i = 0; i < m_capacity; i++)
	{
		m_items[i] = other.m_items[i];
	}

	m_front = other.m_front;
	m_rear = other.m_rear;
}

 

데이터 삽입 메서드 구현

데이터 삽입 연산에 필요한 메서드들을 구현한다.

 

CircularQueue.cpp

/// <summary>
/// CircularQueue의 끝 부분에 값을 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void CircularQueue::Enqueue(int value)
{
	if (IsNeedToResize())
	{
		Resize();
	}

	m_items[m_front++] = value;
	m_count++;

	m_front = m_front % (m_capacity + 1);
}

/// <summary>
/// CircularQueue에 count만큼의 값을 삽입할 수 있는지 확인한다.
/// </summary>
/// <returns>삽입 가능 여부</returns>
bool CircularQueue::IsNeedToResize()
{
	return m_capacity < m_count + 1;
}

/// <summary>
/// 데이터 삽입 시 공간이 부족한 경우 공간을 2배로 늘려준다.
/// </summary>
void CircularQueue::Resize()
{
	int* newItems{ new int[m_capacity * 2]{ 0 } };
	for (size_t i = 0; i < m_count; i++)
	{
		newItems[i] = m_items[m_rear++];
		m_rear = m_rear % (m_capacity + 1);
	}

	m_capacity *= 2;
	m_rear = 0;
	m_front = m_count;

	delete[] m_items;
	m_items = newItems;
}

 

데이터 인출 메서드 구현

데이터 인출 연산에 필요한 메서드들을 구현한다.

 

CircularQueue.cpp

/// <summary>
/// CircularQueue의 시작 부분을 제거하지 않고 반환한다.
/// </summary>
/// <returns>시작 부분에 있는 값</returns>
int CircularQueue::Peek()
{
	if (m_count <= 0)
	{
		throw std::out_of_range("empty");
	}

	return m_items[m_rear];
}

/// <summary>
/// CircularQueue의 시작 부분의 값을 제거한 뒤 반환한다.
/// </summary>
/// <returns>시작 부분에 있던 값</returns>
int CircularQueue::Dequeue()
{
	if (m_count <= 0)
	{
		throw std::out_of_range("empty");
	}

	int data{ m_items[m_rear++] };
	m_rear = m_rear % (m_capacity + 1);
	m_count--;

	return data;
}

/// <summary>
/// CircularQueue의 모든 값을 제거한다.
/// </summary>
void CircularQueue::Clear()
{
	m_front = m_rear = m_count = 0;
}

 

기능 메서드 구현

자료구조를 효율적으로 사용하기 위한 기능 메서드를 구현한다.

 

CircularQueue.cpp

/// <summary>
/// CircularQueue에 지정한 값이 존재하는지 확인한다.
/// </summary>
/// <param name="value">CircularQueue에서 찾을 값</param>
/// <returns>값의 존재 여부</returns>
bool CircularQueue::Contains(int value)
{
	for (size_t i = 0, j = m_rear; i < m_count; i++)
	{
		if (m_items[j] == value)
		{
			return true;
		}

		j = (j + 1) % (m_capacity + 1);
	}
	return false;
}

 

참고문헌

Microsoft MSDN.Queue 클래스 (System.Collections)