//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;
}
