数据结构
链式队列
以链表为基础实现链式队列
1.思路：
如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。
2.图示：
3.代码：
/*****************************************************************************************************************
*
* file name : LinkedQueue.c
* author : [email protected]
* data : 2024/04/26
* function : 以链表为基础实现链式队列的接口程序
* note : None
*
* CopyRight (c) 2024 [email protected] All Right Reseverd
*
* ****************************************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//指的是链式队列中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录链式队列LinkedQueue的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedQueue
{
DataType_t data; //结点的数据域
struct LinkedQueue *next; //结点的指针域
}LQueue_t;
/*****************************************************************************************************************
*
* func name : LQueue_Create
* function : 创建一个空链式队列，空链式队列应该有一个队列头结点，对链式队列进行初始化
* argument : None
* retval : LQueue_t
* note : None
* author : [email protected]
* data : 2024/04/26
*
*
* ****************************************************************************************************************/
//创建一个空链式队列，空链式队列应该有一个队列头结点，对链式队列进行初始化
LQueue_t * LQueue_Create(void)
{
//1.创建一个队列头结点并对队列头结点申请内存
LQueue_t *Head = (LQueue_t *)calloc(1,sizeof(LQueue_t));
if (NULL == Head)
{
perror("Calloc memory for HeadQueue is Failed");
exit(-1);
}
//2.对队列头结点进行初始化，队列头结点是不存储有效内容的！！！
Head->next = NULL;
//3.把队列头结点的地址返回即可
return Head;
}
/*****************************************************************************************************************
*
* func name : LQueue_NewNode
* function : 创建新的队列结点，并对新队列结点进行初始化
* argument :
* @data
* retval : LQueue_t
* note : None
* author : [email protected]
* data : 2024/04/26
*
*
* ****************************************************************************************************************/
//创建新的队列结点，并对新队列结点进行初始化
LQueue_t * LQueue_NewNode(DataType_t data)
{
//1.创建一个新队列结点并对新队列结点申请内存
LQueue_t *New = (LQueue_t *)calloc(1,sizeof(LQueue_t));
if (NULL == New)
{
perror("Calloc memory for NewNodeQueue is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
/*****************************************************************************************************************
*
* func name : LQueue_Enqueue
* function : 对链式队列进行尾部插入操作，称为入队
* argument :
* @data
* @Head
* retval : bool
* note : None
* author : [email protected]
* data : 2024/04/26
*
*
* ****************************************************************************************************************/
//入队（尾插）
bool LQueue_Enqueue(LQueue_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LQueue_t *New = LQueue_NewNode(data);
if (NULL == New)
{
printf("can not insert new node for Queue\n");
return false;
}
//2.判断链表是否为空，如果为空，则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
//3.如果链表为非空，则把新结点插入到链表的尾部
while (Head->next)
{
Head = Head->next;
}
Head->next = New; //把尾结点的next指针指向新节点
return true;
}
/*****************************************************************************************************************
*
* func name : LQueue_Dequeue
* function : 对链式队列进行头部删除操作，称为出队
* argument :
* @Head
* retval : DataType_t
* note : None
* author : [email protected]
* data : 2024/04/26
*
*
* ****************************************************************************************************************/
//出队（头删）
DataType_t LQueue_Dequeue(LQueue_t *Head)
{
DataType_t temp = 0;
//1.判断当前链式队列是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkedqueue is empty!\n");
return -1;
}
//2.如果当前链式队列为非空，则删除当前链式队列的头结点
LQueue_t *Phead = Head->next; //备份头结点地址
Head->next = Head->next->next; //把头结点的next指针指向首结点的直接后继
Phead->next = NULL; //把首结点的next指针指向NULL
temp = Phead->data; //出队首结点的数据域
return temp;
}
/*****************************************************************************************************************
*
* func name : LQueue_Print
* function : 遍历链式队列的元素
* argument :
* @Head
* retval : void
* note : None
* author : [email protected]
* data : 2024/04/26
*
*
* ****************************************************************************************************************/
//遍历链式队列的元素
void LQueue_Print(LQueue_t *Head)
{
//对链式队列的头文件的地址进行备份
LQueue_t *Phead = Head;
//判断头结点的next指针是否指向NULL，若next指针指向NULL则退出
while(Phead->next)
{
//把队列头结点的直接后继作为新的队列头结点
Phead = Phead->next;
//输出队列现在头结点的数据域
printf("%d->",Phead->data);
}
}
int main(int argc, char const *argv[])
{
LQueue_t *Head = LQueue_Create();
//入队
LQueue_Enqueue(Head,1);
LQueue_Enqueue(Head,20);
LQueue_Enqueue(Head,3);
LQueue_Enqueue(Head,5);
LQueue_Enqueue(Head,85);
LQueue_Print(Head);
printf("\n");
printf("\n");
//出队
printf("%d\n",LQueue_Dequeue(Head));
printf("%d\n",LQueue_Dequeue(Head));
printf("\n");
//遍历
LQueue_Print(Head);
printf("\n");
return 0;
}
4.结果验证：
