数据结构（C语言）链式队列

链式队列

链式队列，带头节点，队头为第一个数据节点，队尾在最后一个数据节点
头节点为一个队头指针、一个队尾指针，增加队尾指针可让入队时间复杂度为O(1)

由三个文件 lqueue.h、lqueue.cpp、main.cpp组成

lqueue.h头文件

#pragma once

typedef struct LPNode//数据节点
{
	int data;//数据域
	struct LPNode* next;//后继指针
}LPNode;

typedef struct HNode//链式队列的头节点
{
	struct LPNode* front;//队头指针,指向第一个数据节点
	struct LPNode* rear;//队尾指针,指向最后一个数据节点
}HNode, * PLQueue;

//初始化
void InitQueue(PLQueue pq);

//入队
bool Push(PLQueue pq, int val);

//获取队头元素的值,但不删除
bool  GetTop(PLQueue pq, int* rtval);

//获取队头元素的值,并且删除
bool  Pop(PLQueue pq, int* rtval);

//判空
bool IsEmpty(PLQueue pq);

//获取队列中有效数据的个数
int GetLength(PLQueue pq);

//销毁
void Destroy(PLQueue pq);

lqueue.cpp文件

#include "lqueue.h"
#include 
#include 
//初始化
void InitQueue(PLQueue pq)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return;
	}
	pq->front = NULL;
	pq->rear = NULL;
}

//入队
bool Push(PLQueue pq, int val)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return false;
	}
	LPNode* p = (LPNode*)malloc(sizeof(LPNode));
	p->data = val;
	p->next = NULL;
	if (IsEmpty(pq))
	{
		pq->front = p;
		pq->rear = p;
	}
	else
	{
		pq->rear->next = p;//将p插入到队尾
		pq->rear = p;//队尾指针指向新节点
	}

	return true;
}

//获取队头元素的值,但不删除
bool  GetTop(PLQueue pq, int* rtval)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return false;
	}
	if (IsEmpty(pq))
	{
		return false;
	}
	*rtval = pq->front->data;
	return true;
}

//获取队头元素的值,并且删除
bool  Pop(PLQueue pq, int* rtval)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return false;
	}
	if (IsEmpty(pq))
	{
		return false;
	}
	LPNode* p = pq->front;
	*rtval = p->data;
	pq->front = p->next;
	free(p);

	if (pq->front == NULL)//删除了最后一个节点
	{
		pq->rear = NULL;
	}
	return true;
}

//判空
bool IsEmpty(PLQueue pq)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return false;
	}
	return pq->front == NULL;
}

//获取队列中有效数据的个数
int GetLength(PLQueue pq)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return -1;
	}
	int count = 0;
	for (LPNode* p = pq->front; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

//销毁
void Destroy(PLQueue pq)
{
	assert(pq != NULL);
	if (pq == NULL)
	{
		return;
	}
	LPNode* p;
	while (pq->front != NULL)
	{
		p = pq->front;
		pq->front = p->next;
		free(p);
	}
	pq->rear = NULL;
}

main.cpp文件

#include"lqueue.h"
#include
int main()
{
	HNode q;
	InitQueue(&q);
	
	for (int i = 0; i < 10; i++)
	{
		Push(&q, i);
	}
	int val;
	while (!IsEmpty(&q))
	{
		Pop(&q, &val);
		printf("%d  ", val);
	}
	Destroy(&q);

	return 0;
}