Queue in Linked Structures

생성일: 2021년 10월 15일 오후 9:53

ADT Stack Operation

Transformers

• MakeEmpty
• Enqueue
• Dequeue

Observers

• IsFull
• IsEmpty

(기존의 Queue와 동일한 기능들)

구현

QueType.h

#pragma once
class FullQueue
{};

class EmptyQueue
{};

// StackType.h에서 이미 NodeType 구조체가 정의 되어 있기 때문에 다시 정의할 필요 x

template <class ItemType>
class QueType
{
public:
	QueType();
	~QueType();	//Destructor
	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(ItemType item);
	void Dequeue(ItemType& item);
	void MakeEmpty();

private:
	NodeType<ItemType>* qFront;
	NodeType<ItemType>* qRear;
};

//정의
template <class ItemType>
QueType<ItemType>::QueType()
{
	qFront = nullptr;
	qRear = nullptr;
}

template <class ItemType>
QueType<ItemType>::~QueType()
{
	MakeEmpty();
}

template <class ItemType>
void QueType<ItemType>::MakeEmpty()
{
	NodeType<ItemType>* tempPtr;

	while (qFront != nullptr)
	{
		tempPtr = qFront;
		qFront = qFront->next;
		delete tempPtr;
	}
	qRear = nullptr;
}

template <class ItemType>
bool QueType<ItemType>::IsEmpty() const
{
	return (qFront == nullptr);
}

template <class ItemType>
bool QueType<ItemType>::IsFull() const
{
	//노드를 하나 만들어서 잘 되는지 확인
	NodeType<ItemType>* location;
	try
	{
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std:: bad_alloc exception)
	{
		return true;
	}
}

template <class ItemType>
void QueType<ItemType>::Enqueue(ItemType newItem)
{
	if (IsFull())
		throw FullQueue();
	else
	{
		// 아래 구현 코드들의 순서가 중요하다.
		// 새 노드 만들기 => 비어있는 큐라면 front도 새노드를 가르키게 하기 => 이전의 rear가 가르키는 노드의 next가 새로만든 노드를 가르키게 하기 => rear가 새로만든 노드를 가르키게 하기
		NodeType<ItemType>* newNode;

		newNode = new NodeType<ItemType>;
		newNode->info = newItem;
		newNode->next = nullptr;
		
		if (qRear == nullptr)
			qFront = newNode;
		else
			qRear->next = newNode;
		qRear = newNode;

	}
	
}

template <class ItemType>
void QueType<ItemType>::Dequeue(ItemType& item)
{
	if (IsEmpty())
		throw EmptyQueue();
	else
	{
		NodeType<ItemType>* tempPtr;

		tempPtr = qFront;
		item = qFront->info;
		qFront = qFront->next;

		if (qFront == nullptr)	//노드가 1개 밖에 없었고 이것을 dequeue 했을 때 (empty가 됨)
			qRear = nullptr;
		delete tempPtr;
	}
}

qFront와 qRear가 아이템을 넣고 뺄 때 어떻게 바뀌는지가 중요하다.

그리고 아이템을 넣고 뺄 때 누수되는 메모리가 없도록 코드 순서를 조심하여 작성해야한다.

(delete 할 노드가 있다면 tempPtr로 가르키고 있다가 꼭 delete 해야한다.)

Main.cpp

#include <iostream>
#include "StackType.h"
#include "QueType.h"
using namespace std;

int main()
{
	QueType<int> myQue;

	myQue.Enqueue(1);
	myQue.Enqueue(2);
	myQue.Enqueue(3);

	int number;

	while (!myQue.IsEmpty())
	{
		myQue.Dequeue(number);
		cout << number << endl;
	}

}