//優先級隊列類
#include <assert.h>
#include <iostream>
using namespace std;
const int DefaultPQSize = 50; //優先級隊列數組的默認長度
template <class T>
class PQueue { //優先級隊列的類定義
public:
	PQueue(int sz = DefaultPQSize); //構造函數
	~PQueue() {delete[] pqelements;} //析構函數
	bool Insert(const T& x); //將新元素x插入到隊尾
	bool RemoveMin(T& x); //將隊頭元素刪去
	bool getFront(T& x) const; //讀取隊頭(具最小優先權)的值
	void makeEmpty() {count = 0;} //置優先級隊列為空
	bool IsEmpty() const //判隊列空否
	{return (count == 0) ? true : false;}
	bool IsFull() const//判隊列滿否
	{return (count == maxSize) ? true : false; }
	int getSize() const {return count;} //求優先級隊列中元素個數
protected:
	T *pqelements; //優先級隊列數組
	int count; //當前元素個數(長度)
	int maxSize; //隊列最大可容納元素個數
	void adjust(); //隊列調整
};

template <class T>
PQueue<T>::PQueue(int sz) : maxSize(sz), count(0) {
	//構造函數：建立一個最大具有maxSize個元素的空優先級隊列。
	pqelements = new T[maxSize]; //創建隊列空間
	assert ( pqelements != NULL ); //斷言: 動態存儲分配成功與否
};

template <class T>
bool PQueue<T>::Insert(const T& x) {
	//若優先級隊列不滿, 則將元素x插入到該隊列的隊尾, 否則出錯處理。
	if (count == maxSize) return false; //隊列滿則函數返回
	pqelements[count] = x; count++; //插入x到隊尾
	adjust(); //按優先權進行調整
	return true;
};

template <class T>
void PQueue<T>::adjust() {
	//將隊尾元素按其優先權大小調整到適當位置，保持所有元素按優先權從小到大有序。
	T item = pqelements[count-1];
	for (int j = count-2; j >= 0; j--)
		if (pqelements[j] <= item ) break;
	//發現有比item更小或相等的pqelements[j] 跳出循環
		else
		{
			pqelements[j+1] = pqelements[j];
			//比item大的元素pqelements[j]后移
			pqelements[j+1] = item; //插入到適當位置
		}
};

template <class T>
bool PQueue<T>::RemoveMin(T& x) {
	//若優先級隊列不空則函數返回該隊列具最大優先權(值最小)元素的值, 同時將該元素刪除。
	if (count == 0) return false; //若隊列空, 函數返回false
	x = pqelements[0];
	for (int i = 1; i < count; i++) pqelements[i-1] = pqelements[i];
	count--; //優先級隊列元素個數減一
	return true; //刪除成功,返回true
};

template <class T>
bool PQueue<T>::getFront(T& x) const{
	//若優先級隊列不空則函數返回隊列具最小優先權元素的值。
	if (count == 0) return false; //若隊列空, 函數返回
	else {
		x=pqelements[0]; //返回具最小優先權元素的值
		return true;
	}
};