数据结构之队列

一：认识队列

队列是一种FIFO(First In First Out)的批量数据存储结构。其特点是：先进先出，类似于排队。
队列的基本属性： 队列内存、队首、队尾、万金油属性：size(当前队列元素个数)
队列的基本操作： 入队、出队、获取队头元素
万金油操作： 判断是否为空、当前队列中元素个数

二：链式队列

链式队列是用链式结构来储存队列中的元素，其实质的链表的表尾法插入

（一）：结点设计

//结点  属性:数据域、指针域
struct Node
{
	int data;
	struct Node* next;
};
//创建节点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

(二)：对列的数据设计：抽象数据类型

//队列    属性： 队头 队尾 万金油属性：size
struct queue
{
	int sizeQueue;
	//链表结构实现队列：结构体指针
	//数组实现队列：数组下标
	struct Node* frontNode;//队头指针指向头结点
	struct Node* tailNode;//队尾指针指向尾结点
};
//表示队列
//描述最初的状态
struct queue* createQueue()
{
	struct queue* lpQueue = (struct queue*)malloc(sizeof(struct queue));
	lpQueue->sizeQueue = 0;
	lpQueue->frontNode = lpQueue->tailNode = NULL;
	return lpQueue;
}

（三）:万金油操作

//万金油函数 
//队列中元素个数
int size(struct queue* lpQueue)
{
	return lpQueue->sizeQueue;
}
//判断队列是否为空
int empty(struct queue* lpQueue)
{
	return lpQueue->sizeQueue == 0;
}

（四）：队列的三个基本操作

//入队操作：无头链表再封装的方式
void push(struct queue* lpQueue, int data)
{
	struct Node* newNode = createNode(data);
	if(lpQueue->sizeQueue==0)
	{
		lpQueue->frontNode = newNode;
		lpQueue->tailNode = newNode;
	}
	else
	{
		//表尾法插入的过程：
		//排队的方式
 		//新的数据要放在原来队尾的后面
		lpQueue->tailNode->next = newNode;
		//队尾的位置要发生改变，队尾要变成新的结点 
		lpQueue->tailNode = newNode;
	}
	lpQueue->sizeQueue++;
}
//出队操作：无头链表的表头法删除
void pop(struct queue* lpQueue)
{
	//删除首先判断是否为NULL
	if (empty(lpQueue))
	{
		printf("队列为空,无法出队\n");
		return;//队列为空,无法出队,结束掉函数
	}
	//先保存下一个结点
	struct Node* nextNode = lpQueue->frontNode->next;
	//然后删除头结点
	free(lpQueue->frontNode);
	//把lpQueue->frontNode指向新的头结点
	lpQueue->frontNode = nextNode;
	lpQueue->sizeQueue--;
}
//获取队头元素
int front(struct queue* lpQueue)
{
	if (lpQueue->sizeQueue == 0)
	{
		printf("队列为NULL,无法出队！\n");
		system("pause");
		exit(0);
	}
	return lpQueue->frontNode->data;
}

(五)：测试代码：

int main()
{
	struct queue* lpQueue = createQueue();
	for (int i = 0; i < 10; i++)
	{
		push(lpQueue, i);
	}
	while (!empty(lpQueue))
	{
		printf("%d\t", front(lpQueue));
		pop(lpQueue);
	}
	printf("\n");
	return 0;
}

运行结果：

三：数组队列

数组队列的队列内存有限，注意在操作过程中避免数组越界。

最大队列容量：#define MAX 10

（一）：队列的设计及创建：

//队列的数据设计
struct queue
{
	int* queueMemory; //队列内存-->数组
	int frontPos;	  //队列首元素下标
	int tailPos;	  //队列尾元素下标
};
//创建队列
struct queue* createQueue()
{
	struct queue* lpQueue = (struct queue*)malloc(sizeof(struct queue));
	//描述最初的状态
	//数组当队列		一级指针变为以为数组		动态内存申请
	lpQueue->queueMemory = (int*)malloc(sizeof(int) * MAX);
	lpQueue->frontPos = lpQueue->tailPos = -1;  //-1为标记作用
	return  lpQueue;
}

（二）：万金油函数：

//万金油函数
//当前队列中元素个数
int size(struct queue* lpQueue)
{
	return lpQueue->tailPos - lpQueue->frontPos;
}
//判断队列是否为NULL
int empty(struct queue* lpQueue)
{
	return lpQueue->frontPos == lpQueue->tailPos;
}

(三)：队列的三个基本操作：

//入队操作：队尾往后移动就可以了
void push(struct queue* lpQueue, int data)
{
	//用数组时注意下标溢出问题
	if (lpQueue->tailPos == MAX - 1)
	{
		printf("队满无法入队！\n");
		return;
	}
	lpQueue->queueMemory[++lpQueue->tailPos] = data;
}
//出队操作：队首往后移动,（伪删除）
void pop(struct queue* lpQueue)
{
	if (empty(lpQueue))
	{
		printf("队为NULL,无法出队！\n");
		return;
	}
	else lpQueue->frontPos++;
}
//获取队首元素
int front(struct queue* lpQueue)
{
	if (empty(lpQueue))
	{
		printf("队为NULL,无法获取队首元素！\n");
		system("pause");
		exit(0);
	}
	else
	{
		int frontIndex = lpQueue->frontPos + 1;
		return lpQueue->queueMemory[frontIndex];
	}
}

(四)：测试代码

int main()
{
	struct queue* lpQueue = createQueue();
	for (int i = 0; i < 10; i++)
	{
		push(lpQueue, i);
	}
	while (!empty(lpQueue))
	{
		printf("%d\t", front(lpQueue));
		pop(lpQueue);
	}
	system("pause");
	return 0;
}

运行结果：

四：循环对列设计

https://blog.csdn.net/weixin_44795839/article/details/103323722

五：优先队列

在进行短作业优先法、任务分配等调度问题时用到优先队列
优先队列的数据有两部分组成：数据本身 + 权值

//短作业优先法    优先队列
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
/*
	优先对列： 多了一个优先权
	优先权--->数字，代表任务量,权重
*/
//数据由两部分组成：数据本身 + 权值（关键字）
struct data
{
	int priority;		//权值
	int element;		//数据本身
};
//优先队列
struct priQueue
{
	int sizeQueue;				//队列当前元素
	struct data queue[MAX];		//队列容量
};
//创建优先队列
struct priQueue* createQueue()
{
	struct priQueue* lpQueue = (struct priQueue*)malloc(sizeof(struct priQueue));
	lpQueue->sizeQueue = 0;
	//数组的初始化
	memset(lpQueue->queue, 0, sizeof(struct data) * MAX);
	return lpQueue;
}

//万金油函数
int empty(struct priQueue* lpQueue)
{
	return lpQueue->sizeQueue == 0;
}
int size(struct priQueue* lpQueue)
{
	return lpQueue->sizeQueue;
}


//入队操作：从文件中读出来，入队
void push(struct priQueue* lpQueue, struct data curData)
{
	if (lpQueue->sizeQueue == MAX)
	{
		printf("队列已满，无法入队\n");
		return;
	}
	else
	{
		lpQueue->queue[lpQueue->sizeQueue] = curData;
		lpQueue->sizeQueue++;
	}
}
//出队操作
void pop(struct priQueue* lpQueue, struct data* popData)//将出队元素保存到popData中去
{
	if (empty(lpQueue))
	{
		printf("队列为NULL,无法出队！\n");
		return;
	}
	else
	{
		struct data minData = lpQueue->queue[0];   //假设第一个是最小的
		int minIndex = 0;		//记录下标
		for (int i = 1; i < lpQueue->sizeQueue; i++)
		{
			if (lpQueue->queue[i].priority < minData.priority)//比较权值
			{
				minData = lpQueue->queue[i];
				minIndex = i;
			}
		}
		*popData = lpQueue->queue[minIndex];
		//注意：不能写为：popData = &lpQueue->queue[minIndex];
		//否则后面的伪删除使得minIndex后元素整体前移。数据和下标对应发生变化造成错误。
		//调整对列，做伪删除
		for (int i = minIndex; i < lpQueue->sizeQueue; i++)
		{
			lpQueue->queue[i] = lpQueue->queue[i + 1];
		}
		lpQueue->sizeQueue--;
	}
}
int main()
{
	struct priQueue* lpQueue = createQueue();
	struct data readData;
	FILE* fp = fopen("task.txt", "r");
	if (fp == NULL)
	{
		printf("文件打开失败!\n");
		return 0;
	}
	while (fscanf(fp, "%d %d\n", &readData.element, &readData.priority) != EOF)
	{
		push(lpQueue, readData);
	}
	fclose(fp);//关闭文件指针

	int workIndex = 1;//序号
	printf("\t序号\t编号\t工作量\n");
	while (!empty(lpQueue))
	{
		pop(lpQueue, &readData);//按工作量从小到大进行出队
		printf("\t%d\t%d\t%d\n", workIndex, readData.element, readData.priority);
		workIndex++;
	}
	system("pause");
	return 0;
}