[자료구조] Linked Allocation - Queue

Queue도 마찬가지로, 미리 할당되어 고정된 배열로 구현하는 것이 아니라, Enqueue를 할 때마다 필요한 만큼의 메모리를 할당받을 수 있도록 구현할 수 있음.

FIFO: first in, first out

• qFront: 가장 먼저 들어왔으며, 가장 먼저 나가는 노드
• qRear: 가장 나중에 들어왔으며, 가장 나중에 나가는 노드

---

Array-based vs. Linked-list-based 방법의 메모리 비교

각 80 bytes 크기의 string을 저장하는 Queue이며, index는 2 bytes, pointer는 4 bytes라고 가정한다면

Array-based

Queue의 배열의 사이즈를 100으로 설정하면

• Total memory
  = (80 bytes * 101 slots) + (2 bytes * 2 indexes)
  = 8084bytes

Linked-list-based

• Total memory
  = 80 bytes + 4 bytes
  = 84 bytes (한 노드당!)

조금 저하된 시간복잡도를 감수하고서라도 Linked list로 구현하는 이유는, 메모리 절약 효과를 보기 위해서이다.
그러나 Linked list로 구현할 경우, Queue에 들어가는 아이템이 97개, 즉 일정 개수 이상이 될 경우 메모리 절약 효과를 보지 못한다!

이는 Queue에 들어가는 item의 size가 작을수록 심해짐. (ex. 80 bytes의 string -> 2 bytes의 short int)

---

구현

DynamicAllocQueueType.h

#pragma once
#include "NodeType.h"

template<class ItemType>
class QueType
{
public:
	QueType();
	~QueType();
	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(ItemType item);
	void Dequeue(ItemType& item);
	void MakeEmpty();
private:
	NodeType<ItemType>* qFront;
	NodeType<ItemType>* qRear;
};

DynamicAllocQueueType.cpp

#include "DynamicAllocQueueType.h"
#include <stdexcept>

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

template<class ItemType>
QueType<ItemType>::~QueType()
{
	ItemType tempItem;
	while (!IsEmpty()) Dequeue(tempItem);
}

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

template<class ItemType>
bool QueType<ItemType>::IsFull() const
{
	NodeType<ItemType>* location;
	try
	{
		// 새로운 Node를 받는 것이 가능함 => false
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception)
	{
		// Node를 받으려 해도 안 받아질 때 => true
		return true;
	}
}

스택과 달리, 포인터가 두 개이기 때문에 Dequeue와 Enqueue를 신중히 해야 한다.

• Queue가 비어 있지 않을 때의 Enqueue

1. qRear가 가리키는 노드의 Next를 바꿈
2. qRear가 가리키는 노드를 바꿈
   

• Queue가 비어 있을 때의 Enqueue

1. qFront와 qRear 모두 새로운 노드를 가리키도록 함.
   

• Queue에 Dequeue

1. qFront가 가리키는 노드를 Next로 바꿈
2. 이때, 기존 Queue에 아이템이 하나만 존재하여 qFront=nullptr이 되면, qRear=nullptr로 바꿈.

template<class ItemType>
void QueType<ItemType>::Dequeue(ItemType& item)
{
	NodeType<ItemType>* tempPtr;

	tempPtr = qFront;
	item = qFront->info;
	qFront = qFront->next;
	if (qFront == nullptr) qRear = nullptr;
	delete tempPtr;
}

template<class ItemType>
void QueType<ItemType>::Enqueue(ItemType item)
{
	NodeType<ItemType>* ptr;

	ptr = new NodeType<ItemType>;
	ptr->info = item;
	ptr->next = nullptr;

	if (qRear == nullptr) qFront = ptr; // queue가 비어 있다면
	else qRear->next = ptr;

	qRear = ptr;
}