C++ 링크드 리스트를 이용한 큐 구현 (Single Linked List Queue C++)

FILO(LILO)구조

구현한 함수(다형성을 위해 템플릿 사용)

void Enqueue(T _value); 

 T Dequeue(); 가장 먼져 들어간 값을 반환하고 큐에서 지움

bool empty(); 비어있는지 확인하는 함수

 

/* 싱글링크드 리스트를 이용해 실제 사용되는 자료구조 큐와 동일하게 구현 - 2019/12/23 xtar.tistory */

#include <iostream>
using namespace std;

template <typename T>
class Node
{
public:
	T value;
	Node* next;

	Node() :value(0), next(nullptr) {};
	~Node() {};
};

template <typename T>
class Queue
{
public:
	Queue() :head(nullptr), tail(nullptr), size(0) {};
	~Queue() {};

	void Enqueue(T _vaule);
	T Dequeue();
	bool empty();

private:
	Node<T>* head;
	Node<T>* tail;
	int size;
};

int main()
{
	Queue<int> queue;
	queue.Enqueue(1);
	queue.Enqueue(2);
	queue.Enqueue(3);
	queue.Enqueue(4);
	queue.Enqueue(5);

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

template<typename T>
void Queue<T>::Enqueue(T _vaule)
{
	Node<T>* newNode = new Node<T>;
	newNode->value = _vaule;
	size++;
	
	if (head == nullptr)
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = tail->next;
	}
		
}

template<typename T>
T Queue<T>::Dequeue()
{
	size--;
	if (empty())
		return -1;
	else
	{
		Node<T>* ptr = head;
		T vaule = head->value;

		if (head == tail)
		{
			head =nullptr;
			tail= nullptr;
			delete(head);
		}
		else
		{
			ptr = ptr->next;
			delete(head);
			head = ptr;
		}
		return vaule;
	}
}

template<typename T>
bool Queue<T>::empty()
{
	if (tail == nullptr)
		return true;
	else
		return false;
}