[자료구조] 큐(Queue)/ 템플릿 / C++

큐(Queue 클래스)에서 관리하는 데이터는 Node 클래스로 구성되어있다.

 

작성된건 링크드 큐이기도 한데, 순환큐도 있다.

 

순환큐는 배열에서 사용되서 new와 같은 연산이 없고, 고정배열이라 빠르나, 사이즈 제한이 있다.

 

어느정도 정해진 수만큼의 큐를 만든다면 순환큐도 좋다.

 

template <typename T>
class Node {
public:
	T mdata; //노드 값 변수
	Node* NextNode; //해당 노드의 다음 노드 

	Node(T _data)
		:mdata(_data) {};
	~Node() {};
};

template <typename T> class Queue {
public:
	Queue() :
		mhead(nullptr), mtail(nullptr) {}; //기본값 초기화
	~Queue() {};

	void Enqueue(T _NewData); 
	T Dequeue();
	bool IsEmpty(); 

	T Check() const; //현재 뽑히는 값 확인

private:
	Node<T>* mhead;  //앞쪽 노드
	Node<T>* mtail; //뒤쪽 노드

};

template <typename T>
T Queue<T>::Check() const
{
	return mhead->mdata; //현재 head value값 확인
}

template<typename T>
void Queue<T>::Enqueue(const T& _NewData) 
{
	Node<T>* newNode = new Node<T>(_NewData); 

	if (IsEmpty() == true ) //헤드가 비었다면, 
	{
		mhead = newNode; 
		mtail = newNode;
	}	
	else
	{
		mtail->NextNode = newNode; //꼬리노드의 다음 = 추가 된 노드
		mtail = newNode; //꼬리노드 = 추가된 노드
	}
}//end of Add

template<typename T>
T Queue<T>::Dequeue()
{
	if (IsEmpty()) //노드가 비어 있다면
		return -1;

	T curData = mhead->mdata; //헤드데이터 값
	mhead = mhead->NextNode; //헤드노드  변경


	return curData;  //뽑은 값 출력	  
}//end of Remove

template<typename T> bool Queue<T>::IsEmpty()
{
	return mhead == nullptr; //비었는지 확인
}

 

 

#include <iostream>
using namespace std;


int main() {
	Queue<int> queue;
	cout << queue.Dequeue() << endl;
	queue.Enqueue(3);
	queue.Enqueue(5);
	queue.Enqueue(7);
	queue.Enqueue(9);
	queue.Enqueue(12);
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	cout << "다음으로 나오는 값은 : " << queue.Check() << "입니다." << endl;
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	cout << queue.Dequeue() << endl;
	return 0;
}//end of main

 

-1은 값이 없을때 출력으로 했다.