队列的链式存储

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
//节点结构体
struct node
{
	//只维护指针域
	node* next;
};
//队列结构体
struct queue
{
	//头节点
	node pheader;
	//队列的长度
	int size;
	//记录链表尾部的指针
	node* ptail;
};
//隐藏queue结构体，不让用户改变结构体内部的属性-----class类里面的private私有属性
typedef void* linkQueue;
//队列的初始化
linkQueue init_queue()
{
	//把队列的结构体开辟到堆区
	queue* myqueue = (queue*)malloc(sizeof(queue));
	if (myqueue == NULL)
	{
		return NULL;
	}
	//初始化操作
	myqueue->pheader.next = NULL;
	myqueue->ptail = &myqueue->pheader;
	myqueue->size = 0;
	return myqueue;
}
//入队：从队尾插入
void push_queue(linkQueue que, void* data)
{
	if (que == NULL)
		return;
	if (data == NULL)
		return;
	queue* myqueue = (queue*)que;
	//用一个新节点来接收用户输入数据的指针域接口
	node* newNode = (node*)data;
	//尾插
	myqueue->ptail->next = newNode;
	newNode->next = NULL;
	myqueue->ptail = newNode;
	//更新长度
	myqueue->size  ;
}
//出队：头删
void pop_queue(linkQueue que)
{
	if (que == NULL)
	{
		return;
	}

	queue* myqueue = (queue*)que;

	if (myqueue->size == 0)
	{
		return;
	}


	//这里有一个特殊情况是只有一个有效节点时进行删除操作，尾节点的位置应该要改变，重新指回头节点
	if (myqueue->size == 1)
	{
		myqueue->pheader.next = NULL;
		myqueue->ptail = &myqueue->pheader;
		myqueue->size--;
		return;
	}


	//保存住第一个节点的位置
	node* firstNode = myqueue->pheader.next;
	myqueue->pheader.next = firstNode->next;
	//free操作不需要，因为不清楚用户的数据开辟在堆区还是栈区
	//更新长度
	myqueue->size--;
}
//返回队列的大小
int size_queue(linkQueue que)
{
	if (que == NULL)
		return -1;
	queue* myqueue = (queue*)que;
	return myqueue->size;
}
//判断队列是否为空
bool empty_queue(linkQueue que)
{
	if (que == NULL)
		return true;
	queue* myqueue = (queue*)que;
	if (myqueue->size == 0)
		return true;
	return false;
}
//返回队头的元素
linkQueue top_queue(linkQueue que)
{
	if (que == NULL)
		return NULL;
	queue* myqueue = (queue*)que;
	return myqueue->pheader.next;
}
//返回队尾的元素
linkQueue back_queue(linkQueue que)
{
	if (que == NULL)
		return NULL;
	queue* myqueue = (queue*)que;
	return myqueue->ptail;
}
//销毁队列
void destory_queue(linkQueue que)
{
	if (que == NULL)
		return;
	free(que);
	que = NULL;
}

//测试------------------------------------------------
struct person
{
	//指针域接口
	void* next;
	char name[32];
	int age;
};
void test()
{
	person p1 = { NULL, "大忽悠",19 };
	person p2 = { NULL,"like",18 };
	person p3 = { NULL, "小朋友",19 };
	//初始化队列
	linkQueue myqueue = init_queue();
	printf("队列的链式存储:n");
	//入队
	push_queue(myqueue, &p1);
	push_queue(myqueue, &p2);
	push_queue(myqueue, &p3);
	//返回队列的大小
	printf("队列的大小：%dn", size_queue(myqueue));
	//遍历
	while (empty_queue(myqueue) == false)
	{
		//访问队头
		person* pFront = (person*)top_queue(myqueue);
		printf("对头元素: %st%dn", pFront->name, pFront->age);
		//访问队尾
		person* pBack = (person*)back_queue(myqueue);
		printf("对尾元素: %st%dn", pBack->name, pBack->age);
		//出队
		pop_queue(myqueue);
	}
	//销毁队列
	destory_queue(myqueue);
	//返回队列的大小
	printf("队列的大小：%dn", size_queue(myqueue));
}
int main()
{
	test();
	return 0;
}

存储 队列

0 人点赞