Priority Queue

생성일: 2021년 11월 23일 오후 11:39

PQType.h

#pragma once
#include "Heap.h"

class FullPQ{};
class EmptyPQ{};

template <class ItemType>
class PQType
{
public:
	PQType(int); //동적할당할 사이즈 받아오기
	~PQType();
	void MakeEmpty();
	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(ItemType newItem);
	void Dequeue(ItemType& item);

private:
	int length;
	HeapType<ItemType> items;
	int maxItems;

};

template <class ItemType>
PQType<ItemType>::PQType(int max)
{
	maxItems = max;
	items.elements = new ItemType[max]; //heap에서 Array를 동적할당 함
	length = 0;
}

template <class ItemType>
PQType<ItemType>::~PQType()
{
	delete[] items.elements;
}

template <class ItemType>
void PQType<ItemType>::MakeEmpty()
{
	length = 0;
}

template <class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
	if (length == 0)
		throw EmptyPQ();
	else
	{
		item = items.elements[0];
		items.elements[0] = items.elements[length - 1];
		length--;
		items.ReheapDown(0, length - 1); // 여기서 length - 1은 rightmost element
	}
}

template <class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
	if (length == maxItems)
		throw FullPQ();
	else
	{
		length++; //꼭 먼저 해줘야 함 why? 이걸 뒤에 하면 바로 밑줄의 items.elements[length-1] 이 이미 있는 마지막 노드에 접근해서 덮어 써버림
		items.elements[length - 1] = newItem;
		items.ReheapUp(0, length - 1);
	}
}

template <class ItemType>
bool PQType<ItemType>::IsFull() const
{
	return length == maxItems;
}

template <class ItemType>
bool PQType<ItemType>::IsEmpty() const
{
	return length == 0;
}

Main.cpp

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

int main()
{
	PQType<int> pq(5);
	pq.Enqueue(4);
	pq.Enqueue(1);
	pq.Enqueue(2);
	pq.Enqueue(5);
	pq.Enqueue(3);

	int item;
	pq.Dequeue(item);
	cout << item << endl;
	pq.Dequeue(item);
	cout << item << endl;
}