//Queue.h
#pragma once
#include <assert.h>
/*
* 큐: 선입 선출(FIFO), 선착순
- 정말 다양한 방식으로 구현이 가능하다.
- 리스트 기반의 구현 방식, 배열 기반의 구현 방식을 베이스로
- 양방향으로 추가 가능한 큐라던지,
배열 기반의 큐인데, 한정된 배열 공간을 재활용해가며 사용할 수 있는
써클 큐라던지로 사용이 가능하다.
*/
//노드는 스택에서 구현했던 방식과 동일하다.
template <typename T>
class CQueueNode
{
template <typename T>
friend class CQueue;
private:
CQueueNode() :
m_Next(nullptr)
{
}
~CQueueNode()
{
}
private:
T m_Data;
CQueueNode<T>* m_Next;
};
//큐는 스택보다 변수가 하나 더 필요하다.
//뺄 때는 처음 노드에서 빼야 하고 넣을 때는 끝 노드에 넣어야 하기 때문이다.
template <typename T>
class CQueue
{
public:
CQueue()
{
m_First = nullptr;
m_Last = nullptr;
m_Size = 0;
}
~CQueue()
{
NODE* Node = m_First;
while (Node)
{
NODE* Next = m_First->m_Next;
delete Node;
Node = Next;
}
}
private:
typedef CQueueNode<T> NODE;
private:
NODE* m_First;
NODE* m_Last;
int m_Size;
public:
void push(const T& Data)
{
//새 노드 만들어 주고
NODE* Node = new NODE;
//노드에 데이터 넣어 주고
Node->m_Data = Data;
//만약 처음 추가한 값이 아니라면(이미 큐에 값을 넣은 적이 있다면)
//만약 처음 넣은 값이라면(m_Last가 nullptr이면)
if (!m_Last)
{
m_First = Node;
}
else
{
//주소 연결 해 주고
m_Last->m_Next = Node;
}
//마지막 주소를 Node로 변경해 주고
m_Last = Node;
//사이즈를 늘려 주고
++m_Size;
}
T& front()
{
if (empty())
{
assert(false);
}
return m_First->m_Data;
}
//큐이므로 pop -> 앞에것 추출
void pop()
{
if (empty())
{
assert(false);
}
//첫 번째 노드를 임시 변수에 저장하고
NODE* Node = m_First;
//다음 노드가 이제 첫 번째 노드가 됨
m_First = m_First->m_Next;
//노드 삭제
delete Node;
//사이즈 감소
--m_Size;
//큐에서는 추가로 다 지웠을 경우에 대한 예외 처리도 필요하다.(다시 초기화)
if (m_Size == 0)
{
m_First = nullptr;
m_Last = nullptr;
}
}
int size() const
{
return m_Size;
}
bool empty() const
{
return 0 == m_Size;
}
};
//main.cpp
#include <iostream>
#include "Queue.h"
int main()
{
std::cout << "\n====== 리스트형 큐 확인 =====" << std::endl;
CQueue<int> queue;
for (int i = 0; i < 10; ++i)
{
queue.push(i);
}
while (!queue.empty())
{
std::cout << queue.front() << std::endl;
queue.pop();
}
std::cout << "남은 Size: " << queue.size() << std::endl;
return 0;
}
