프로그래밍 기초/자료구조
원형 큐(Circular Queue)
niamdank
2021. 1. 8. 11:56
스택
순차 자료구조를 사용한 큐는 데이터를 인출할 때마다 모든 데이터를 이동시켜야 하는 오버헤드가 발생한다. 이를 방지하기 위한 자료구조가 원형 큐이다.
원형 큐는 기본적으로 시작 지점과 끝 지점을 연결해 계속해서 이어질 수 있도록 만든 것으로 논리적 구조는 다음과 같다.
이때 데이터를 삽입하는 위치와 인출하는 위치는 다음과 같다.
- 삽인 위치 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;
}