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

//QueueArray.h

#pragma once

#include <assert.h>

/*
* 일반적인 배열로 큐를 만들어버리면 매우 비효율적이다.
큐는 앞에서 데이터를 꺼내고 뒤에 넣는 형식이기 때문에
계속 데이터의 시작점이 뒤로 밀리기 때문이다.

--> 그래서 배열로 큐를 만들 때는 '써클 큐' 방식으로 만든다.

* 구현 방법: '헤드'와 '테일'을 만들어서 사용한다.
데이터를 꺼낼 때는 헤드에서 꺼낸 뒤 헤드를 뒤로 한 칸 밀고,
데이터를 넣을 때는 테일에 넣은 뒤 테일을 뒤로 한 칸 민다.

* 배열의 끝에 갔을 경우, 다시 앞으로 되돌아 올 수 있어야 한다. 
예를 들어 크기가 6인 배열일 경우, 6번째 칸(인덱스 5)에 다다르면
다시 0으로 돌아가야 한다
--> 구현 방법 : 나머지 연산자(%) -> 6 나머지는 1~5까지만 나오기 때문.  

* 주의)서클 큐에는 헤드 테일이 한 바퀴를 돌아 다시 만났는지
확인해야 하는 빈 공간이 하나 필요하다.
--> 그러므로 길이가 6인 배열에서 실제 데이터를 넣을 수 있는 공간은 5개이다.
--> 헤드를 빈 공간으로 하고, 실제 데이터는 헤더 + 1부터 들어가도록 할 것임.

* 서클 큐를 만들 때 원하는 사이즈만큼의 배열을 할당하는 방법
	- 비타입 템플릿 인자를 사용한다
	- template <typename T, int SIZE = 100> 
	- 함수의 디폴트 인자와 비슷한 기능이라고 보면 된다.
	- 실제 클래스를 사용할 때는
	- CCircleQueue<int>: SIZE = 기본값(100)
	- CCircleQueue<int, 200>: SIZE = 200
*/


template <typename T, int SIZE = 100>
class CQueueArray
{
public:
	CQueueArray()
	{
		m_Size = 0;
		m_Head = 0;
		m_Tail = 0;
	}
	~CQueueArray()
	{
	}

private:
	//+1을 해 준 이유는 Head와 Tail이 만나는 빈공간
	//하나를 위해서이다.
	T	m_Array[SIZE + 1];
	int m_Size;
	int m_Head;
	int m_Tail;

public:
	//tail에 데이터를 추가
	void push(const T& Data)
	{

		//꼬리 위치를 계산.
		int Tail = (m_Tail + 1) % (SIZE + 1);

		//꽉 찼을때 예외처리
		if (Tail == m_Head)
		{
			return;
		}

		//꼬리 위치에 데이터 삽입
		m_Array[Tail] = Data;

		//새로운 꼬리 위치 등록
		m_Tail = Tail;

		//사이즈 증가
		++m_Size;
	}


	//값을 읽기
	T& front()
	{
		if (empty())
		{
			assert(false);
		}

		int Head = (m_Head + 1) % (SIZE + 1);
	
		//값을 반환
		return m_Array[Head];
	}


	//값을 꺼내고 데이터를 삭제하기
	//Head 인덱스는 비어있는 공간으로 취급하고,
	//실제 데이터는 그 뒤부터 존재하므로
	//먼저 Head 인덱스를 옮겨 주고 값을 불러와도 문제가 없다.
	void pop()
	{
		if (empty())
		{
			assert(false);
		}

		//헤더 위치를 구하고 변경
		m_Head = (m_Head + 1) % (SIZE + 1);

		--m_Size;
	}


	int size() const
	{
		return m_Size;
	}

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

	int Capacity() const
	{
		return SIZE;
	}

	//써클큐가 다 찼는지 확인용
	bool full()
	{
		return (m_Size == SIZE);
	}
};

 

 

 

 

//main.cpp

#include "QueueArray.h"

int main()
{
	std::cout << "\n===== 배열형 써클큐 확인 =====" << std::endl;
	CQueueArray<int> CQ;

	for (int i = 0; i < 10; ++i)
	{
		CQ.push(i);
		
	}

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

	std::cout << "남은 Size: " << CQ.size() << std::endl;
    
    return 0;
    
}