队列
原理介绍：
队列（Queue）和栈类似，相同点是都属于线性结构，不同点是栈遵循“后进先出”原则，而队列遵循“*先进先出*”的原则，也被称为“FIFO”结构，就是“First Input First Output”
数据结构中的队列的两端都允许操作，只不过要求数据只能从队列的一端插入，从队列的另一端删除，可以把队列理解为一根水管，水管有进水口和出水口。一般把允许数据插入的一端称为队尾（Tail或者Rear），一般把允许删除数据的一端称为队头队首（Head或者Front）。
图示一：
图示二：
- 把允许数据插入的一端称为队尾（允许数据插入到队列的操作称为入队，英文enqueue）
- 把允许删除数据的一端称为队头（允许数据从队列删除的操作称为出队，英文dequeue）
代码实现“队列”：
循环队列：以数组为基础
如果以数组为基础，一般会把队列设置为循环队列，循环队列也被称为“环形缓冲区”，因为如果队列中的元素出队，则需要把该元素的后继元素整体向前移动，这是时间复杂度为O(n)的操作。如果数据出队之后不去移动后继元素又会导致数组的空间被浪费。
为了解决该问题，可以把队列设置为循环队列，在移动数据的时候只需要移一次即可，所以时间复杂度就是O(1)。如下图所示：
！！！注意：为了区分循环队列空间是否存满，需要预留一个空间用于辨别，即：
队列‘满’：（队尾下标+1）%容量 == 队首下标
队列‘空’： 队尾下标 == 队首下标
当队首和队尾下标均从0开始时，后续进行入队和出队操作时，需要先赋值再改下标
代码实现过程：
为了方便管理循环队列，所以用户可以构造一个结构体类型作为管理结构体，用于存储队列相关的重要信息（容量、队首下标、队尾下标、堆内存首地址）。因为队列可以从两端对数据进行操作，所以需要设置两个变量用于存储下标，来区分队头队尾。
//指的是循环队列中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录循环队列CircularQueue各项参数(循环队列的首地址 + 循环队列的容量 + 循环队列队尾下标+队首下标)的结构体
typedef struct CircularQueue
{
DataType_t * Addr; //记录循环队列首地址
unsigned int Size; //记录循环队列的容量
int Rear; //循环队列队尾下标
int Front; //循环队列队首下标
}CirQueue_t;
-
创建空的循环队列，并对管理结构体进行初始化：容量、队尾下标、队首下标、首地址
//创建循环队列并对循环队列进行初始化 CirQueue_t * CirQueue_Create(unsigned int size) { //1.利用calloc为循环队列的管理结构体申请一块堆内存 CirQueue_t *Manager = (CirQueue_t *)calloc(1,sizeof(CirQueue_t)); if(NULL == Manager) { perror("calloc memory for manager is failed"); exit(-1); //程序异常终止 } //2.利用calloc为所有元素申请堆内存 Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t)); if (NULL == Manager->Addr) { perror("calloc memory for element is failed"); free(Manager); exit(-1); //程序异常终止 } //3.对管理循环队列的结构体进行初始化（循环队列容量 + 队尾下标+队首下标） Manager->Size = size; //对循环队列中的容量进行初始化 Manager->Rear = 0; //队尾下标初值为0 Manager->Front = 0; //队首下标初值为0 return Manager; } -
把需要插入到循环队列的元素按照“先进先出”进行入队，此时需要从队列队尾入队。
//入队 bool CirQueue_Enqueue(CirQueue_t *Manager, DataType_t Data) { //1.判断循环队列是否已满 if ( CirQueue_IsFull(Manager) ) { printf("CirQueue is Full!\n"); return false; } //2.如果循环队列有空闲空间，则把新元素添加到循环队列尾部 Manager->Addr[Manager->Rear] = Data; //防止队尾下标越界,即超过循环队列的容量 Manager->Rear = (Manager->Rear+1) % Manager->Size; return true; } -
把需要插入到循环队列的元素按照“先进先出”进行出队，此时需要从队列队首出队!
//出队 DataType_t CirQueue_Dequeue(CirQueue_t *Manager) { DataType_t temp =0; //1.判断循环队列是否为空 if ( CirQueue_IsEmpty(Manager) ) { printf("CirQueue is Empty!\n"); return false; } //2.把元素从队首出队，并备份到变量temp temp = Manager->Addr[Manager->Front]; //防止队首下标越界 Manager->Front = (Manager->Front+1) % Manager->Size; return temp; } -
对循环队列进行元素出队和元素入队时，需要对循环队列元素数量进行分析(满 or 空)
//判断循环队列是否已满 bool CirQueue_IsFull(CirQueue_t *Manager) { return ( (Manager->Rear + 1) % Manager->Size == Manager->Front ) ? true : false; } //判断循环队列是否为空 bool CirQueue_IsEmpty(CirQueue_t *Manager) { return (Manager->Front == Manager->Rear) ? true : false; }循环队列代码完整展示：
/******************************************************************************************************** * * * 该程序实现循环队列元素的增删改查，目的是提高设计程序的逻辑思维，另外为了提高可移植性，所以循环队列中元素 * 的数据类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型。 * * 另外，为了方便管理循环队列,所以用户设计SeqList_t结构体，该结构体中包含三个成员：地址+容量+有效元素的下标 * * * * Copyright (c) 2023-2024 [email protected] All right Reserved * ******************************************************************************************************/ #include <stdio.h> #include <stdbool.h> #include <stdlib.h> //指的是循环队列中的元素的数据类型，用户可以根据需要进行修改 typedef int DataType_t; //构造记录循环队列CircularQueue各项参数(循环队列的首地址 + 循环队列的容量 + 循环队列队尾下标+队首下标)的结构体 typedef struct CircularQueue { DataType_t * Addr; //记录循环队列首地址 unsigned int Size; //记录循环队列的容量 int Rear; //循环队列队尾下标 int Front; //循环队列队首下标 }CirQueue_t; //创建循环队列并对循环队列进行初始化 CirQueue_t * CirQueue_Create(unsigned int size) { //1.利用calloc为循环队列的管理结构体申请一块堆内存 CirQueue_t *Manager = (CirQueue_t *)calloc(1,sizeof(CirQueue_t)); if(NULL == Manager) { perror("calloc memory for manager is failed"); exit(-1); //程序异常终止 } //2.利用calloc为所有元素申请堆内存 Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t)); if (NULL == Manager->Addr) { perror("calloc memory for element is failed"); free(Manager); exit(-1); //程序异常终止 } //3.对管理循环队列的结构体进行初始化（循环队列容量 + 队尾下标+队首下标） Manager->Size = size; //对循环队列中的容量进行初始化 Manager->Rear = 0; //队尾下标初值为0 Manager->Front = 0; //队首下标初值为0 return Manager; } //判断循环队列是否已满 bool CirQueue_IsFull(CirQueue_t *Manager) { return ( (Manager->Rear + 1) % Manager->Size == Manager->Front ) ? true : false; } //入队 bool CirQueue_Enqueue(CirQueue_t *Manager, DataType_t Data) { //1.判断循环队列是否已满 if ( CirQueue_IsFull(Manager) ) { printf("CirQueue is Full!\n"); return false; } //2.如果循环队列有空闲空间，则把新元素添加到循环队列尾部 Manager->Addr[Manager->Rear] = Data; //防止队尾下标越界 Manager->Rear = (Manager->Rear+1) % Manager->Size; return true; } //判断循环队列是否为空 bool CirQueue_IsEmpty(CirQueue_t *Manager) { return (Manager->Front == Manager->Rear) ? true : false; } //出队 DataType_t CirQueue_Dequeue(CirQueue_t *Manager) { DataType_t temp =0; //1.判断循环队列是否为空 if ( CirQueue_IsEmpty(Manager) ) { printf("CirQueue is Empty!\n"); return false; } //2.把元素从队首出队，并备份到变量temp temp = Manager->Addr[Manager->Front]; //防止队首下标越界 Manager->Front = (Manager->Front+1) % Manager->Size; return temp; } int main(int argc, char const *argv[]) { return 0; }
链式队列：以链表为基础
如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。 且使用链式队列时，不用考虑队列的容量大小。
代码实现过程：
为了方便管理链式队列，所以用户可以构造一个结构体类型作为管理结构体，用于存储队列相关的重要信息（数据域+指针域）。因为链式队列不需要考虑大小问题，所欲不需要定义容量变量。
//指的是链式队列中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录链式队列LinkQueue各项参数(节点中存储数据 + 当前节点的直接后继地址)的结构体
typedef struct LinkQueue
{
DataType_t data; //记录节点中存储数据
struct LinkQueue *next; //记录当前节点的直接后继地址
}LkQueue_t;
-
创建空的链式队列，并对管理结构体进行初始化：数据域+指针域
/******************************************************************** * * name : LkQueue_Create * function : 创建链式队列队首，并完成对队首的初始化 * argument : * none * retval : 调用成功返回创建成功的队首地址 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ LkQueue_t *LkQueue_Create(void) { //为队首申请堆空间，并完成错误处理 LkQueue_t *Front = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); if(Front == NULL) { perror("Calloc memory for Front is Failed!"); exit(-1); } //对队首初始化 Front->next = NULL; //返回队首地址 return Front; } -
在创建新的节点，用于存储需要存入链式队列的元素。
/******************************************************************** * * name : LkQueue_NewNode * function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域） * argument : * @data 新节点需要存储的数据 * * retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ LkQueue_t *LkQueue_NewNode(DataType_t data) { // 1.创建一个新结点并对新结点申请内存 LkQueue_t *New = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); if (NULL == New) { perror("Calloc memory for NewNode is Failed"); return NULL; } // 2.对新结点的数据域和指针域进行初始化 New->data = data; New->next = NULL; return New; } -
把需要插入到链式队列的元素按照“先进先出”进行入队，此时需要从队列队尾入队，即进行单链表的尾插操作。
/******************************************************************** * * name : LkQueue_EnQueue * function : 将新节点尾插进链式队列中，即完成入队操作 * argument : * @Front 链式队列的队首 * @data 新节点的数据域需要存储的数据 * * retval : 调用成功输出"插入成功"，否则输出"插入失败" * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_EnQueue(LkQueue_t *Front, DataType_t data) { // 定义一个循环指针变量PFront LkQueue_t *PFront = Front->next; // 调用函数创立一个新节点,并完成对应的错误处理 LkQueue_t *New = LkQueue_NewNode(data); if (New == NULL) { printf("EnQueue is fail!\n"); return; } // 进行判断，排除空链表的情况 if (Front->next == NULL) { Front->next = New; printf("EnQueue of %d is success!\n", New->data); return; } // 先遍历得到尾结点在插入 // 1.遍历至尾结点，将尾结点的next更换为新节点 while (PFront->next != NULL) { PFront = PFront->next; } // 跳出while循环时，PFront极为尾节点; PFront->next = New; printf("EnQueue of %d is success!\n", New->data); return; } -
把需要插入到循环队列的元素按照“先进先出”进行出队，此时需要从队列队首出队,即进行单链表的头删操作。
/******************************************************************** * * name : LkQueue_DeQueue * function : 删除链表的首节点，并保持链表的连续性 即完成链式队列的出队操作 * argument : * @Front 链式队列队首 * * retval : 调用成功后删除链式队列的首节点 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_DeQueue(LkQueue_t *Front) { // 对链式队列的队首的地址进行备份 LkQueue_t *PFront = Front->next; // 判断当前链表是否为空，为空则直接退出 if (Front->next == NULL) { printf("current linkequeue is empty!\n"); return; } // 1.将首节点更换 Front->next = Front->next->next; // 2.将备份与链表节点断开 PFront->next = NULL; // 3.释放掉原首节点 free(PFront); printf("DeQueue is success!\n"); return; } -
对链式队列中存储的元素进行遍历输出操作，观察是否符合队列的“先进先出”特点
/******************************************************************** * * name : LkQueue_Print * function : 遍历输出链式队列中所有节点的数据域 * argument : * @Front 链式队列队首 * * retval : 调用成功输出链表中所有节点的数据域的值 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_Print(LkQueue_t *Front) { // 对链式队列的队首的地址进行备份 LkQueue_t *PFront = Front; // 判断当前链表是否为空，为空则直接退出 if (Front->next == NULL) { printf("current linkeflist is empty!\n"); return; } // 从首结点开始遍历 while (PFront->next) { // 把队首的直接后继作为新的首节点 PFront = PFront->next; // 输出队首的直接后继的数据域 printf("%d->", PFront->data); // 判断是否到达尾结点，尾结点的next指针是指向首结点的地址 if (PFront->next == NULL) { break; } } return; }链式队列代码完整展示：
/******************************************************************* * * file name: LinkQueue.c * author : [email protected] * date : 2024/04/26 * function : 该案例是掌握链式队列的相关功能实现 * note : None * * CopyRight (c) 2023-2024 [email protected] All Right Reseverd * * *****************************************************************/ #include <stdio.h> #include <stdlib.h> //指的是链式队列中的元素的数据类型，用户可以根据需要进行修改 typedef int DataType_t; //构造记录链式队列LinkQueue各项参数(节点中存储数据 + 当前节点的直接后继地址)的结构体 typedef struct LinkQueue { DataType_t data; //记录节点中存储数据 struct LinkQueue *next; //记录当前节点的直接后继地址 }LkQueue_t; /******************************************************************** * * name : LkQueue_Create * function : 创建链式队列队首，并完成对队首的初始化 * argument : * none * retval : 调用成功返回创建成功的队首地址 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ LkQueue_t *LkQueue_Create(void) { //为队首申请堆空间，并完成错误处理 LkQueue_t *Front = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); if(Front == NULL) { perror("Calloc memory for Front is Failed!"); exit(-1); } //对队首初始化 Front->next = NULL; //返回队首地址 return Front; } /******************************************************************** * * name : LkQueue_NewNode * function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域） * argument : * @data 新节点需要存储的数据 * * retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ LkQueue_t *LkQueue_NewNode(DataType_t data) { // 1.创建一个新结点并对新结点申请内存 LkQueue_t *New = (LkQueue_t *)calloc(1, sizeof(LkQueue_t)); if (NULL == New) { perror("Calloc memory for NewNode is Failed"); return NULL; } // 2.对新结点的数据域和指针域进行初始化 New->data = data; New->next = NULL; return New; } /******************************************************************** * * name : LkQueue_EnQueue * function : 将新节点尾插进链式队列中，即完成入队操作 * argument : * @Front 链式队列的队首 * @data 新节点的数据域需要存储的数据 * * retval : 调用成功输出"插入成功"，否则输出"插入失败" * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_EnQueue(LkQueue_t *Front, DataType_t data) { // 定义一个循环指针变量PFront LkQueue_t *PFront = Front->next; // 调用函数创立一个新节点,并完成对应的错误处理 LkQueue_t *New = LkQueue_NewNode(data); if (New == NULL) { printf("EnQueue is fail!\n"); return; } // 进行判断，排除空链表的情况 if (Front->next == NULL) { Front->next = New; printf("EnQueue of %d is success!\n", New->data); return; } // 先遍历得到尾结点在插入 // 1.遍历至尾结点，将尾结点的next更换为新节点 while (PFront->next != NULL) { PFront = PFront->next; } // 跳出while循环时，PFront极为尾节点; PFront->next = New; printf("EnQueue of %d is success!\n", New->data); return; } /******************************************************************** * * name : LkQueue_DeQueue * function : 删除链表的首节点，并保持链表的连续性 即完成链式队列的出队操作 * argument : * @Front 链式队列队首 * * retval : 调用成功后删除链式队列的首节点 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_DeQueue(LkQueue_t *Front) { // 对链式队列的队首的地址进行备份 LkQueue_t *PFront = Front->next; // 判断当前链表是否为空，为空则直接退出 if (Front->next == NULL) { printf("current linkequeue is empty!\n"); return; } // 1.将首节点更换 Front->next = Front->next->next; // 2.将备份与链表节点断开 PFront->next = NULL; // 3.释放掉原首节点 free(PFront); printf("DeQueue is success!\n"); return; } /******************************************************************** * * name : LkQueue_Print * function : 遍历输出链式队列中所有节点的数据域 * argument : * @Front 链式队列队首 * * retval : 调用成功输出链表中所有节点的数据域的值 * author : [email protected] * date : 2024/04/26 * note : none * * *****************************************************************/ void LkQueue_Print(LkQueue_t *Front) { // 对链式队列的队首的地址进行备份 LkQueue_t *PFront = Front; // 判断当前链表是否为空，为空则直接退出 if (Front->next == NULL) { printf("current linkeflist is empty!\n"); return; } // 从首结点开始遍历 while (PFront->next) { // 把队首的直接后继作为新的首节点 PFront = PFront->next; // 输出队首的直接后继的数据域 printf("%d->", PFront->data); // 判断是否到达尾结点，尾结点的next指针是指向首结点的地址 if (PFront->next == NULL) { break; } } return; } int main() { //创建链式队列的队首节点 LkQueue_t *Front = LkQueue_Create(); //入队： LkQueue_EnQueue(Front,10); LkQueue_EnQueue(Front,20); LkQueue_EnQueue(Front,30); printf("\n"); //遍历输出 LkQueue_Print(Front); printf("\n"); //出队： LkQueue_DeQueue(Front); LkQueue_DeQueue(Front); printf("\n"); //遍历输出 LkQueue_Print(Front); printf("\n"); LkQueue_DeQueue(Front); LkQueue_DeQueue(Front); return 0; }
结果验证：
学习经验：
队列和栈的代码实现都是基于顺序表与链表的，只是队列和栈有着自己不同的特点，前者是“先进先出”，后者是“后进先出”。甚至可以说这二者是顺序表和链表的简化版。但是算法没有绝对的优势，只有在特定环境下的适合性的高低。
标签：队列,队首,链式,next,Manager,LkQueue,Front From： https://www.cnblogs.com/fly-home/p/18160838