#include<iostream>
#include<iomanip>
using namespace std;
const int MAX = 10;
typedef struct node    //priority queue node
{
	int no;        //任务编号
	int priority;   //优先级
}PQNode;
class PQueue    //优先级队列类
{
private:
	PQNode *base;
	int size;     //队列大小
public:
	//构造函数 
	PQueue();
	//析构函数 
	~PQueue();
	//获取队列大小 
	int getSize()
	{return size;}  
	//判断队列是否为空 
	bool empty()
	{return size == 0;}
	//清空
	void clear()
	{size = 0;}
	//重载运算符<
	bool friend operator<(PQNode node1, PQNode node2);
	//入队
	bool push(PQNode);
	//出队
	bool pop(PQNode&);
	//查找
	bool find(PQNode&);
	//遍历 
	void queueTraverse(); 
};
PQueue::PQueue()
{
	base = new PQNode[MAX];
	size = 0;
}
PQueue::~PQueue()
{
	delete[]base;
}
bool operator<(PQNode node1, PQNode node2)
{
	return node1.priority < node2.priority;
}
bool PQueue::push(PQNode node)
{
	int i;
	for (i=0; i < size; i++)
	{
		if (node.no == base[i].no)  //对于已存在的任务编号更新优先级 
		{
			base[i].priority = node.priority;
			break;
		}
	}
	if (i < size || (i == size && size < MAX))
	{
		if (i == size)
		base[size++] = node;
		return true;
	}
	//已无空间存放新节点 
	return false;
}
bool PQueue::pop(PQNode &node)
{
	if (size == 0)
		return false;
	int index = 0;
	for (int i = 1; i < size; i++)
	{
		if (base[i] < base[index])  //若是没有重载<，则这里必须写成base[i].priority<base[index].priority
			index = i;
	}
	node = base[index];
	/*
	出队后，index位置该如何填补？
	方法多种：
	一、index后的元素依次前移
	二、直接用最后一个元素填到index位置
	建议使用第一种 
	*/
	size--;
	for (int i = index; i < size; i++)
		base[i] = base[i + 1];
	return true;
}
bool PQueue::find(PQNode &node)
{
	if (size == 0)
		return false;
	int index = 0;
	for (int i = 1; i < size; i++)
	{
		if (base[i] < base[index])
			index = i;
	}
	node = base[index];
	return true;
}
void PQueue::queueTraverse()
{
	if(!empty())
	{
		int i=0;
		cout<<"编号"<<" "<<"优先级"<<endl;
		while (i < size)
		{
			cout<<setw(4)<<base[i].no<<setw(4)<<base[i].priority<<endl;
			i++;
		}
	}
}

int main()
{
	cout<<"******优先级队列演练******"<<endl;
	PQueue pqueue;
	cout<<"队列目前的状态是";
	pqueue.empty()?cout<<"空！"<<endl:cout<<"非空！"<<endl;
	PQNode node;
	cout<<"输入任务号和优先级(一组一行)，输入0 0结束"<<endl;
	while(cin>>node.no>>node.priority && node.no && node.priority)
		pqueue.push(node);
	cout<<"打印队列"<<endl;
	pqueue.queueTraverse();
	cout.setf(ios::left);
	cout<<"查找优先级最高的"<<endl;
	pqueue.find(node)?cout<<"编号是"<<setw(4)<<node.no<<"优先级是"<<setw(4)<<node.priority<<endl:cout<<"空队列，无法查找！"<<endl;
	cout<<"队列清空"<<endl;
	pqueue.clear();
	cout<<"队列目前的状态是";
	pqueue.empty()?cout<<"空！"<<endl:cout<<"非空！"<<endl;	 
	system("pause");
	return 0;
}