220413_자료구조_리스트형 큐 구현 및 실행

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