欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先级队列的实现

程序员文章站 2022-05-04 15:08:16
...

1 优先级队列的实现

优先队列: 它的入队顺序没有变化,但是出队的顺序是根据优先级的高低来决定的。优先级高的优先出队。

优先级队列的实现
优先级队列的实现

代码实现如下:

#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define MaxSize 5 //队列的最大容量

typedef int DataType; //任务队列中元素类型

typedef struct _QNode { //结点结构
	int priority; //每个节点的优先级,0 最低优先级,9 最高优先级,优先级相同,取第一个节点
	DataType data;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr;

typedef struct Queue
{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

//队列初始化,将队列初始化为空队列
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0
}

//判断队列为空
int IsEmpty(LinkQueue* LQ)
{
	if (!LQ) return 0;

	if (LQ->front == NULL)
	{
		return 1;
	}

	return 0;
}

//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;

	if (LQ->length == MaxSize)
	{
		return 1;
	}

	return 0;
}

//入队,将元素 data 插入到队列 LQ 中
int EnterQueue(LinkQueue* LQ, DataType data, int priority) {
	if (!LQ) return 0;

	if (IsFull(LQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}

	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->priority = priority;
	qNode->next = NULL;

	if (IsEmpty(LQ)) {//空队列
		LQ->front = LQ->rear = qNode;
	}
	else {
		LQ->rear->next = qNode;//在队尾插入节点 qNode
		LQ->rear = qNode; //队尾指向新插入的节点
	}

	LQ->length++;

	return 1;
}

//出队,遍历队列,找到队列中优先级最高的元素 data 出队
int DeleteQueue(LinkQueue* LQ, DataType* data) {
	QNode** prev = NULL, * prev_node = NULL;//保存当前已选举的最高优先级节点上一个节点的指针地址。 
	QNode * last = NULL, *tmp = NULL;
	
	if (!LQ || IsEmpty(LQ)) {
		cout << "队列为空!" << endl;
		return 0;
	}

	if (!data) return 0;

	//prev 指向队头 front 指针的地址
	prev = &(LQ->front);
	printf("第一个节点的优先级: %d\n", (*prev)->priority);
	last = LQ->front;
	tmp = last->next;
	while (tmp) {
		if (tmp->priority > (*prev)->priority) {
			printf("抓到个更大优先级的节点[priority: %d]\n",
				tmp->priority);
			prev = &(last->next);
			prev_node = last;
		}

		last = tmp;
		tmp = tmp->next;
	}

	*data = (*prev)->data;
	tmp = *prev;
	*prev = (*prev)->next;
	delete tmp;
	LQ->length--;

	//接下来存在 2 种情况需要分别对待
	//1.删除的是首节点,而且队列长度为零
	if (LQ->length == 0) {
		LQ->rear = NULL;
	}

	//2.删除的是尾部节点
	if (prev_node && prev_node->next == NULL) {
		LQ->rear = prev_node;
	}

	return 1;
}

//打印队列中的各元素
void PrintQueue(LinkQueue* LQ)
{
	QueuePtr tmp;

	if (!LQ) return;

	if (LQ->front == NULL) {
		cout << "队列为空!";
		return;
	}

	tmp = LQ->front;
	while (tmp)
	{
		cout << setw(4) << tmp->data << "[" << tmp->priority << "]";
		tmp = tmp->next;
	}

	cout << endl;
}

//获取队首元素,不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空!" << endl;
		return 0;
	}

	if (!data) return 0;

	*data = LQ->front->data;

	return 1;
}

//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	while (LQ->front) {
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}

	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}

//获取队列中元素的个数
int getLength(LinkQueue* LQ) {
	if (!LQ) return 0;

	return LQ->length;
}

int main()
{
	LinkQueue* LQ = new LinkQueue;
	DataType data = -1;

	//初始化队列
	InitQueue(LQ);

	//入队
	for (int i = 0; i < 5; i++) {
		EnterQueue(LQ, i + 10, i);
	}

	//打印队列中的元素
	printf("队列中的元素(总共%d 个):", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;

	//出队
	for (int i = 0; i < 5; i++) {
		if (DeleteQueue(LQ, &data)) {
			cout << "出队的元素是:" << data << endl;
		}
		else {
			cout << "出队失败!" << endl;
		}
	}

	//打印队列中的元素
	printf("出队五个元素后,队列中剩下的元素[%d]:\n", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;
	ClearQueue(LQ);
	cout << "清空队列!\n";
	PrintQueue(LQ);

	//清理资源
	delete LQ;

	system("pause");
	return 0;
}

参考资料:

  1. C/C++从入门到精通-高级程序员之路【奇牛学院】
相关标签: 所学所思所想