优先队列----数据结构

概念

不知道你玩过英雄联盟吗？英雄联盟里面的防御塔会攻击离自己最近的小兵，但是如果有炮车兵在塔内，防御塔会优先攻击炮车（因为炮车的威胁性更大），只有没有兵线在塔内时，防御塔才会攻击英雄。所以你可以得出优先级：距离最近的炮车 > 炮车 > 距离最近的小兵 > 小兵 > 距离最近的英雄 > 英雄。

那什么是优先队列？首先它是一个队列，它的入队顺序没有发生改变，但是出队的顺序是根据优先级的高低来实现的，遍历队列，优先级高的先出队，有多个节点具有最高的优先级，选取遇到的第一个具有最高的优先级的节点。

空队列

插入一个元素

插入第二个元素

删除一个节点

上列情况是最普通的情况（无需多余的操作），显然如果删除的是队列中的最后一个节点，尾指针需要手动移动；如果删除的是队列中的第一个节点，头指针会自动移动。如果删除的队列只有一个节点，那头尾指针需要手动置空。所以总共有 2 种情况需要考虑。

队列的算法实现

队列的结构体定义

其中优先级的高低是自己定义的，你也可以令 0 为最高优先级，优先级数也不只有这 9 个。

#define MAX_SIZE 15
typedef int DateElem;

typedef struct _QNode
{
	int priority; //节点的优先级，9为最高优先级，0为最低优先级，优先级相同的取第一个
	DateElem date;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr; //QueuePtr a; 就定义了一个指向结构体QNode的指针

typedef struct _Queue
{
	int length;    //队列长度
	QueuePtr head; //头指针
	QueuePtr tail; //尾指针
}Queue;

队列的初始化、判空、判满、插入

//队列的初始化，初始化为空队列
void initQueue(Queue* q)
{
	if (!q) //指向队头的指针为空
	{
		return;
	}

	q->head = NULL;
	q->tail = NULL;
	q->length = 0;
}

//判断队列是否为空
bool IsEmpty(Queue* q)
{
	if (!q) return false;

	if (q->head == NULL) //条件用 q->tail == NULL 也行
	{
		return true;
	}

	return false; //不为空
}


//判断队列是否为满
bool IsFull(Queue* q)
{
	if (!q) return false;

	if (q->length >= MAX_SIZE) //也可以用 q->length == MAX_SIZE
	{
		return true;
	}

	return false;
}

//入队
bool enterQueue(Queue* q, DateElem e, int priority)
{
	if (!q || IsFull(q))
	{
		cout << "队列已满" << endl;
		return false;
	}

	QNode* p = new QNode;

	//if (!q) return false; 一般不会生成失败

	p->priority = priority;
	p->date = e;
	p->next = NULL;

	//插入有两种情况
	if (IsEmpty(q)) //空队列
	{
		q->head = p;
		q->tail = p;
	}
	else //队列中已有元素
	{
		q->tail->next = p; //队列中的最后一个节点的next指针指向新加节点
		q->tail = p;	   //更新尾指针
	}

	q->length++;
	return true;
}

出队

唯一与普通队列有较大差别的就是队列的出队，其他的操作变化很小。

//遍历队列
bool popQueue(Queue* q,DateElem *out)
{
	if (!q || IsEmpty(q))
	{
		cout << "队列为空" << endl;
		return false;
	}

	if (!out)
	{
		cout << "无法传递删除节点的值" << endl;
		return false;
	}


	QNode** prev_node_next = NULL; //二级指针，指向优先级最高的节点的前一个节点的next指针
	QNode* prev_node = NULL; //指向优先级最高的节点的前一个节点
	QNode* temp = NULL,*last = NULL; //temp遍历队列，last指向temp指向的前一个节点

	prev_node_next = &(q->head); //最开始指向队头指针（也就是第一个节点的前一个节点的next指针），解引用就是指向第一个节点

	last = q->head; 
	temp = last->next; 

	while (temp != NULL)
	{
		if (temp->priority > (*prev_node_next)->priority)
		{
			cout << "找到了一个更高的优先级：" << temp->priority << endl;
			prev_node_next = &(last->next); //指向temp的前一个节点的next指针
			prev_node = last; //指向temp的前一个节点
		}
		last = temp;
		temp = temp->next;
	}

	*out = (*prev_node_next)->date; //传递出队元素的值
	temp = *prev_node_next;  // temp指向要删除节点
	*prev_node_next = (*prev_node_next)->next; //或者是 prev_node_next = & (*prev_node_next)->next;

	delete temp;
	q->length--;


	//情况一：删除节点后为空队列
	if (q->length == 0)
	{
		q->head = q->tail = NULL;
	}
	//情况二：删除的是尾节点
	else if ( *prev_node_next == NULL && prev_node != NULL)
	{
		q->tail = prev_node;
	}
	//情况三：删除的是首节点，与情况一不同的是删除节点后，队列不为空
	//情况四：普通情况
	//这两种情况遍历结束后的调整中头尾指针就弄好了

	return true;
}

如果你觉得我这里写得不好，嘻嘻，因为明明只需要用一级指针，我偏要用二级指针，这就是我与明明的区别，哈哈，好了不开玩笑，可以看看下图帮助理解。

队列的打印、清空、获取队首元素

//打印队列
bool Print(Queue* q)  
{
	if (!q) return false;

	if (IsEmpty(q))
	{
		cout << "队列为空" << endl;
	}

	QNode* p = q->head;
	cout << "队列中的元素：";
	while (p != NULL)
	{
		printf("%d[优先级%d] ", p->date,p->priority);
		p = p->next;
	}
	cout << endl;
	return true;
}
//清空队列
bool ClearQueue(Queue* q)
{
	if (!q || IsEmpty(q)) return false;

	QNode* temp = q->head, * tmp = NULL;

	while (temp != NULL)
	{
		tmp = temp->next;
		delete temp;
		temp = tmp;
	}

	q->length = 0;
	q->head = NULL;
	q->tail = NULL;
	return true;
}

//获取队头
bool GetHead(Queue* sq, DateElem* date)
{
	if (!date || !sq || IsEmpty(sq))return false;

	*date = sq->head->date; 
	return true;

}

主函数测试代码

int main(void)
{
	Queue* q = new Queue;
	DateElem e = -1;
	initQueue(q);

	for (int i = 0; i < 10; i++)
	{
		enterQueue(q, i + 2, i);
	}

	printf("队列中有%d个元素\n", q->length);

	Print(q);

	for (int i = 0; i < 5; i++)
	{
		if (popQueue(q, &e))
		{
			cout << "出队的元素是：" << e << endl;
		}
		else
		{
			cout << "出队失败" << endl;
		}
	}

	cout << "出队后，";
	Print(q);

	cout << "清空队列后，";
	ClearQueue(q);
	Print(q);

	//清理资源
	delete q;

	return 0;
}

运行结果：