以链表为基础实现链式队列

以链表为基础实现链式队列

如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//对输入类型进行重新定义
typedef int DataType_t;

//构建链表结构体
typedef struct Linkedqueue
{
	DataType_t data;
	struct Linkedqueue* next;

}LinkQue;


//创建一个空链表，空链表应该有一个头结点，对链表进行初始化
LinkQue* LinkQue_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	LinkQue* Head = (LinkQue*)calloc(1, sizeof(LinkQue));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.对头结点进行初始化，头结点是不存储有效内容的！！！
	Head->next = NULL;

	//3.把头结点的地址返回即可
	return Head;
}


//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
LinkQue* LinkQue_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	LinkQue* New = (LinkQue*)calloc(1, sizeof(LinkQue));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.对新结点的数据域和指针域进行初始化
	New->data = data;
	New->next = NULL;

	return New;
}




//入队

bool LinkQue_Enqueue(LinkQue* Head, DataType_t data)
{
	//1、创建新的节点，并对新节点进行初始化
	LinkQue* New = LinkQue_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}

	//2.判断链表是否为空，如果为空，则直接插入即可
	if (NULL == Head->next)
	{
		Head->next = New;
		return true;
	}

	//3.如果链表为非空，则把新结点插入到链表的尾部
	LinkQue* Current = Head->next;
	while (NULL != Current->next)
	{
		Current = Current->next;
	}
	Current->next = New;
	return true;
}



//出队
bool LinkQue_Dequeue(LinkQue* Head)
{
	//1.判断链表是否为空，如果为空，则直接插入即可
	if (NULL == Head->next)
	{
		perror("can not delete because list is empty\n");
		return false;
	}
	else
	{
		//2.判断链表不为空，找出第一个数据
		LinkQue* Current = Head->next;
		Head->next = (Head->next)->next;
		printf("出队值为%d\n", Current->data);
		free(Current);
		return true;
	}

}


//遍历队列
void LinkQue_Print(LinkQue* Head)
{
	//对链表的头文件的地址进行备份
	LinkQue* Phead = Head->next;

	//首结点
	while (Head->next)
	{

		//输出头结点的直接后继的数据域
		printf("data = %d\n", Phead->data);
		//把头的直接后继作为新的头结点
		Phead = Phead->next;


	}
}


int main(int argc, char const* argv[])
{
	//创建头节点
	LinkQue* Head = LinkQue_Create();

	//入队
	LinkQue_Enqueue(Head, 5);

	//出队
	LinkQue_Dequeue(Head);


	//遍历打印
	LinkQue_Print(Head);
	return 0;
}