数据结构：链式队列
目录
1.实现思想
2.包含头文件
3.结点设计
4.接口函数实现
实现思想
链式队列，指的是使用链表实现的队列，是一种常见的数据结构。队列遵循先进先出（FIFO）的原则，即最先进入队列的元素将是最先被移除的元素。链式队列通过链表的动态特性来实现队列的插入和删除操作，提供了比静态数组实现的队列更高的灵活性。为了实现链式队列，需要实现以下几点：
1.节点定义： 链式队列由一系列节点组成，每个节点通常包含两个部分：数据部分和指向下一个节点的指针
2.入队：在队列的末尾添加一个新元素。这通常涉及到创建一个新的节点，并将其链接到队尾，然后更新队尾指针
3.出队：移除队列的第一个元素，并返回其数据。这通常涉及到更新队首指针，以及释放被移除节点的内存（如果需要的话）
4.队首和队尾指针： 链式队列需要维护两个指针：队首指针（指向队列的第一个元素）和队尾指针（指向队列的最后一个元素）。这两个指针使得入队和出队操作可以在 O(1) 时间复杂度内完成
5.动态内存管理： 由于链式队列的元素是动态添加的，因此需要使用动态内存分配来创建新的节点。在 C 或 C++ 中，通常通过 malloc 或 new 操作符来完成
6.空队列处理： 需要有一种机制来检测队列是否为空，通常可以通过检查队首指针是否为 NULL 来实现
包含头文件
#include<stdio.h>
#include<stdlib.h>结点设计
typedef int Elemtype; //给int类型取别名为Elemtypetypedef struct LinkNode{Elemtype data;struct LinkNode* next; //定义struct LinkNode类型的指针next指向下一个结点
}QNode,*LNode;typedef struct LiNode{struct LinkNode* rear; //定义struct LinkNode类型的指针rear指向队尾结点struct LinkNode* front; //定义struct LinkNode类型的指针front指向队头结点
};
接口函数实现
/*注：定义存储指向队头结点与指向队尾结点的指针后，在函数中调用两个结构体时，要注意其中的关系，不要因为队头的结点的指针指向的结点地址的再次指向而造成混乱
*/void InitLNode(LiNode &B); //声明函数InitLNode用于初始化链式队列
bool InputLNode(LiNode &B); //声明函数InputLNode用于在队列中输出数据
bool LNodeEmpty(LiNode& B); //声明函数LNodeEmpty用于判断队列是否为空
void InsertLNode(LiNode &B);//声明函数InsertLNode用于在队列中输入数据
bool DestroyQueue(LNode& A);//声明函数DestroyQueue用于销毁队列//在队列中输出数据
bool InputLNode(LiNode &B) { if (LNodeEmpty(B)) {return false;}else{LNode Q = B.front->next; //定义LNode类型的指针变量Q指向头结点的下一个结点printf("输出数据为:%d", Q->data);//输出数据B.front->next = Q->next; if(B.rear == Q){ //判断输出的结点是否为最后一个结点B.rear = B.front; //将其队列置空}return true;}
}//判断队列是否为空
bool LNodeEmpty(LiNode &B){ if(B.front == B.rear){printf("传入的链式队列为空");return true;}else{return false;}
}//在队列中输入数据
void InsertLNode(LiNode &B){ Elemtype i; //定义int类型的变量i接受键盘键入的数据LNode W = (QNode*)malloc(sizeof(QNode));//定义LNode类型w向计算机的堆内申请存储空间printf("请输入要插入的数据");scanf_s("%d", &i);W->data = i;W->next = NULL;B.rear->next = W;B.rear = W; //更新尾结点的指向
}//初始化链式队列
void InitLNode(LiNode &B){ B.front=B.rear=(QNode*)malloc(sizeof(QNode)); B.front->next = NULL; //更新结点中next的指向printf("初始化链式队列成功\n");
}