优先队列故事引入

现实生活中，我们在排队干一件事情的时候，总要有个先来后到，但是如果其中一个人是vip，恐怕就可以后来居上了。因此，我们这里用优先队列来模拟这种现实生活中的情况。

优先队列原理

优先队列相比较于普通的队列，入队的顺序并没有发生变化，唯一不一样的是，出队的顺序是根据队列中元素的优先级（priopity）来判断的

优先队列源码实现

#include <iostream>
#define MAX_SIZE 12

using namespace std;

typedef int dataType;
/*********************
这里我选择采用链式存储的方法，
每一个元素包含了数据data，
优先级 priopiry以及指针域
指向下一个元素地址的指针next
***********************/
typedef struct _QNode {
	dataType data;
	int priority;
	_QNode* next;
	
}QNode;

typedef struct {
	int length;
	QNode* front;
	QNode* rear;
}PrQueue;
//初始化优先队列
bool init(PrQueue*& PQ) {
	if (!PQ) return false;
	PQ->front = PQ->rear = NULL;
	PQ->length = 0;
	return true;
}
//判断优先队列是否为空
bool isEmpty(PrQueue*& PQ) {
	if (!PQ) return false;
	if (PQ->front == NULL) return true;
	return false;
}
//判断优先队列是否为满
bool isFull(PrQueue*& PQ) {
	if (!PQ) return false;
	if (PQ->length == MAX_SIZE) return true;
	return false;
}
//入队
bool PqInsert(PrQueue*& PQ,dataType data,int priopity) {
	if (!PQ) return false;
	if (isFull(PQ)) {

		cout << "队列已满了！" << endl;
		return false; 
	}
	QNode* N = NULL;
	N = new QNode;
	N->data = data;
	N->priority = priopity;
	N->next = NULL;
	if (isEmpty(PQ)) {
		PQ->front = PQ->rear = N;
	}
	else {
		PQ->rear->next = N;
		PQ->rear = N;
	}
	PQ->length++;
	return true;
}
/**********************************************************************
************************************************************************
出队算法思路：
设置last和tmp一前一后来遍历整个优先队列，node指向优先级最大节点，因为遍历
双向队列过程中，last会移动，我们用node来记录这个优先级最大节点
设置一个二级指针prev用来指向node的上一个节点的next的地址，这里为什么要设置二级指针？
1.当队列中只有一个元素的时候，此时只有头节点跟一号节点，用二级指针可以直接修改
PQ中的front的值2.当队列中有多个元素的时候，此时prev用来放置node的上一个节点的next的地址，调用
*prev我们可以直接使node上一个节点的next值变为last里的next。
while循环直到tmp == NULL结束，也就是last指向最后一个节点结束
******************************************************************************
*******************************************************************************/
bool PqDelete(PrQueue*& PQ) {
	if (!PQ) return false;
	if (isEmpty(PQ)) return false;
	QNode** prev = NULL, *node = NULL;
	QNode* tmp = NULL, * last = NULL;
	prev = &(PQ->front);
	cout << "第一个节点的优先级是" << (*prev)->priority << endl;
	last = PQ->front;
	tmp = last->next;
	while (tmp) {
		if (tmp->priority > (*prev)->priority) {
			prev = &(last->next);
			node = last;
		}
		last = tmp;
		tmp = last->next;
	}
	tmp = *prev;
	*prev = (*prev)->next;
	delete tmp;
	PQ->length--;
	//删除的是头节点,而且是最后一个元素
	if (PQ->length == 0) {
		PQ->rear = NULL;
	}
	//删除的是尾部节点
	if (node&&node->next == NULL) {
		PQ->rear = node;
	}
	return 1;
}
//干掉优先队列
bool clearPq(PrQueue*& PQ) {
	if (!PQ) return false;
	if (isEmpty(PQ)) return true;
	QNode* N = PQ->front;
	QNode* tmp = NULL;
	while (N) {
		tmp = N;
		N = N->next;
		delete tmp;
	}
	PQ->front = PQ->rear = 0;
	PQ->length = 0;
	return true;
}
//遍历优先队列中所有元素
bool printPq(PrQueue*& PQ) {
	if (!PQ) return false;
	if (isEmpty(PQ)) {
		cout << "优先队列为空!无法打印东西哦." << endl;
		return false;
	}
	QNode* N = NULL;
	N = PQ->front;
	while (N) {
		cout << N->data << "\t" << "优先级:" << N->priority << endl;
		N = N->next;
	}
	return true;
}