以链表为基础实现链式队列
如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。
需要注意的点：
- 遍历队列需要备份地址
- 出队需要考虑空列表、列表中只有一个数据的情况
以下是我的代码：
/********************************************************************* file name: linkqueue.c* author : Dazz* date : 2024/04/26* function : 以单向链表（带头结点）为基础实现链式队列,把头结点作为队首，实现头删，把尾结点作为队尾，实现尾插入* note : None** CopyRight (c) 2024-202x Dazz_24@163.com All Right Reseverd** *****************************************************************/#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>// 指的是链式队列中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;// 构造记录链式队列结点linkrqueuenode各项参数（指针域next+数据域data)
typedef struct LinkrQueueNode
{DataType_t data; // 数据域struct LinkrQueueNode *next; // 指针域
} LinkrQueueNode_t;// 构造记录链式队列linkrqueue各项参数(队列的队头+队尾)的结构体
typedef struct LinkrQueue
{LinkrQueueNode_t *Rear; // 队首，记录头结点地址LinkrQueueNode_t *Front; // 队尾，记录尾结点地址} LinkrQueue_t;/******************************************************** name : Linkqueue_Create* function : 创建一个链式队列，并对其初始化* argument ：None* retval : 链式队列记录者的地址* author : Dazz* date : 2024/4/26* note : None** *******************************************************/
LinkrQueue_t *LinkQueue_Create(void)
{// 创建记录链式队列的结构体，并对其初始化LinkrQueue_t *record = (LinkrQueue_t *)calloc(1, sizeof(LinkrQueue_t));// 判断链式队列的记录者是否申请成功if (NULL == record){printf("The link queue application failed!\n");exit(-1); // 程序异常终止}// 对链式队列的记录者进行初始化record->Front = NULL;record->Rear = NULL;return record;
}/******************************************************** name : Linkqueue_Create* function : 判断链式队列是否为空* argument ：None* retval : 队链为空返回1，否则返回0* author : Dazz* date : 2024/4/26* note : None** *******************************************************/
bool LinkQueue_IsEmpty(LinkrQueue_t *record)
{return ((record->Front == NULL) && (record->Rear == NULL)) ? true : false;
}/******************************************************** name : LinkQueueNode_Create* function : 创建一个新的结点，并对该结点进行初始化（数据域 + 指针域）* argument* @data :需要传入结点中的数据** retval : 新结点的地址* author : Dazz* date : 2024/4/26* note : None** *******************************************************/
LinkrQueueNode_t *LinkQueueNode_Create(DataType_t data)
{// 创建新的结点LinkrQueueNode_t *New = (LinkrQueueNode_t *)calloc(1, sizeof(LinkrQueueNode_t));// 判断是否创建成功if (NULL == New){printf("The new node creation failed\n");return;}// 对新结点初始化New->next = NULL;New->data = data;return New;
}/******************************************************** name : Linkqueue_Enqueue* function : 将结点入队* argument* @record :链式队列记录者的地址* @data ：结点数据域里的数据** retval : 成功返回1，否则为0* author : Dazz* date : 2024/4/26* note : None** *******************************************************/
bool Linkqueue_Enqueue(LinkrQueue_t *record, DataType_t data)
{// 创建新结点LinkrQueueNode_t *New = LinkQueueNode_Create(data);// 判断新结点是否创建成功if (NULL == New)return false;if (LinkQueue_IsEmpty(record)) // 链队为空的情况{record->Front = New; // 链队记录者的Front指向新结点record->Rear = New; // 链队记录者的Rear指向新结点}else // 链队不为空的情况{record->Rear->next = New; // 将尾结点的指针域指向新结点record->Rear = New; // 将管理者的Rear指向新结点}return true;
}/******************************************************** name : PrintfAllNodes* function : 遍历链队，打印每个结点中的数据* argument* @record :记录者的地址** retval : None* author : Dazz* date : 2024/4/24* note : None** *******************************************************/
void PrintfAllNodes(LinkrQueue_t *record)
{// 判断队列是否为空，如为空，直接退出if (LinkQueue_IsEmpty(record)){printf("The queue is empty\n");return;}// 对记录者的rear进行备份LinkrQueueNode_t *temp = record->Front;// 用循环遍历链队while (temp->next != NULL){printf("%d\n", temp->data);temp = temp->next;}printf("%d\n", temp->data);
}/******************************************************** name : LinkQueue_Dequeue* function : 将链队出队* argument* @record :记录者的地址** retval : 出队的数据* author : Dazz* date : 2024/4/24* note : None** *******************************************************/
DataType_t LinkQueue_Dequeue(LinkrQueue_t *record)
{// 定义变量记录要出队的数据DataType_t temp = 0;// 判断链队是否为空if (LinkQueue_IsEmpty(record)){printf("The queue is empty and cannot be dequeued\n");return;}// 队列只有一个结点的情况else if (NULL == record->Front->next){temp = record->Front->data; // 对要出队的数据进行备份LinkrQueueNode_t *temp = record->Front; // 对要出队的地址进行备份record->Front = NULL; // 重新把记录器的Front指向NULLrecord->Rear = NULL; // 重新把记录器的Rear指向NULLfree(temp); // 释放要出队的结点}else{// 队列不为空的情况,数据需从队首出队temp = record->Front->data; // 对要出队的数据进行备份LinkrQueueNode_t *nodetemp = record->Front; // 对要出队的地址进行备份record->Front = nodetemp->next; // 将记录者的Front指向出队结点的后面的结点nodetemp->next = NULL; // 将要出对的结点的指针域指向NULLfree(nodetemp); // 释放要出队的结点}return temp;
}int main()
{LinkrQueue_t *record = LinkQueue_Create();// Linkqueue_Enqueue(record, 555);// Linkqueue_Enqueue(record, 666);// Linkqueue_Enqueue(record, 777);Linkqueue_Enqueue(record, 888);// LinkQueue_Dequeue(record);// LinkQueue_Dequeue(record);// LinkQueue_Dequeue(record);int a = LinkQueue_Dequeue(record);printf("a= %d\n", a);PrintfAllNodes(record);return 0;
}
