数据结构：链式队列

目录

        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类型取别名为Elemtype
 
typedef 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");
}