220413_자료구조_자동 확장 서클 큐(Circle Queue)

//CircleQueueDynamic.h


/*
지난 번에 구현한 서클 큐와 자동 확장 배열 클래스를 응용하여,
용량이 꽉 차면 자동으로 용량을 두 배만큼 늘려 주는 서클 큐를 구현
*/



#pragma once

#include <assert.h>

template <typename T>
class CCircleQueueDynamic
{
public:
	CCircleQueueDynamic()
	{
		m_Size = 0;
		m_Capacity = 4;
		m_Head = 0;
		m_Tail = 0;
		m_Array = new T[m_Capacity + 1];
	}
	~CCircleQueueDynamic()
	{
		delete[] m_Array;
	}

private:
	int m_Size;
	int m_Capacity;
	int m_Head;
	int m_Tail;
	T* m_Array;

public:
	void push(const T& Data)
	{
		//if (full())
		//{
		//	//이후 추가
		//}

		int Tail = (m_Tail + 1) % (m_Capacity + 1);

		//할당 전에)꽉 찼으면 크기가 2배인 새 배열을 할당.
		if (m_Head == Tail)
		{
			m_Capacity *= 2;

			T* newArr = new T[m_Capacity + 1];


			//head는 빈 공간이므로 실제 데이터 범위는
			//m_Size + 1
			for (int i = 0; i < m_Size + 1; ++i)
			{
				newArr[i] = m_Array[m_Head + i];
			}

			//머리와 꼬리 재설정.
			m_Head = 0;
			m_Tail = m_Size;


			//동적할당 해제
			delete[] m_Array;

			//새 배열을 동적할당에 등록.
			m_Array = newArr;
		}

		//꼬리 위치 다시 계산.
		Tail = (m_Tail + 1) % (m_Capacity + 1);

		//데이터 추가
		m_Array[Tail] = Data;

		//꼬리 위치 재설정.
		m_Tail = Tail;

		++m_Size;
	}

	T& front()
	{
		if (empty())
		{
			assert(false);
		}

		return m_Array[m_Head + 1];
	}

	void pop()
	{
		if (empty())
		{
			assert(false);
		}

		int Head = (m_Head + 1) % (m_Capacity + 1);

		m_Head = Head;

		--m_Size;
	}

	bool full()	const
	{
		return (m_Size == m_Capacity);
	}

	bool empty()	const
	{
		return (m_Size == 0);
	}

	int capacity()	const
	{
		return m_Capacity;
	}

	int size() const
	{
		return m_Size;
	}
};

 

 

 

//main.cpp

#include <iostream>

int main()
{
	std::cout << "\n===== 동적할당 배열형 써클큐 확인 =====" << std::endl;

	CCircleQueueDynamic<int> DCQ;

	for (int i = 0; i < 100; ++i)
	{
		DCQ.push(i);
	}

	
	for (int i = 0; i < 99; ++i)
	{
		std::cout << DCQ.front();
		if ((i+1) % 5 != 0)
			std::cout << ", ";
		else
			std::cout << std::endl;
		DCQ.pop();

	}

	while (!DCQ.empty())
	{
		std::cout << DCQ.front() << std::endl;
		DCQ.pop();
	}

	std::cout << "남은 Size: " << DCQ.size() << std::endl;
	std::cout << "현재 Capacity: " << DCQ.capacity() << std::endl;

	return 0;
}

 

 

 

 

 

 

<참고자료>

* 자동 확장 배열: https://hyrule.tistory.com/47

220411_자동 확장 배열(Array) 구현 및 실행

* 써클 큐: https://hyrule.tistory.com/52

220413_자료구조_배열형 큐(써클 큐, Circle Queue) 구현 및 실행