자료구조...54

원형 큐 구현 준비

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

 

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

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

 

원형 큐 구현

CircularQueue를 구현한다.

 

CircularQueue.h

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

class CircularQueue
{
public:
#pragma region 생성자
	CircularQueue(int 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

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

	size_t m_front;
	size_t m_rear;
#pragma endregion
};

 

원형 큐 생성자 구현

 

CircularQueue.cpp

/// <summary>
/// 비어있고 초기 용량을 가지는 CircularQueue를 생성한다.
/// </summary>
/// <param name="capacity">생성할 공간의 크기(기본: 10)</param>
CircularQueue::CircularQueue(int 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;
}