数据结构之队列详解(C语言手撕)

03-10 1722阅读

数据结构之队列详解(C语言手撕)

数据结构之队列详解(C语言手撕)

🎉个人名片:

🐼作者简介:一名乐于分享在学习道路上收获的大二在校生

🙈个人主页🎉:GOTXX

🐼个人WeChat:ILXOXVJE

🐼本文由GOTXX原创,首发CSDN🎉🎉🎉

🐵系列专栏:零基础学习C语言----- 数据结构的学习之路----C++的学习之路

🐓每日一句:如果没有特别幸运,那就请特别努力!🎉🎉🎉

————————————————

🎉文章简介:

🎉本篇文章对 用C语言实现队列 等相关知识 学习的相关知识进行分享!🎉

💕如果您觉得文章不错,期待你的一键三连哦,你的鼓励是我创作动力的源泉,让我们一起加

油,一起奔跑,让我们顶峰相见!!!🎉🎉🎉

————————————————

一.队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的性质;

入队列:进行插入操作的一端称为队尾 ;

出队列:进行删除操作的一端称为队头;

数据结构之队列详解(C语言手撕)队列适合用链表来实现,入队列即尾插,出队列即头删,直接改变指针指向即可

如果用数组类实现的话,需要头删,要挪动数据,效率低;

二.队列的实现

数据结构之队列详解(C语言手撕)为了方便,可以存储一个尾指针,这样尾插的时候就不需要去找尾,提高效率;

出队的时候为头删,需要改变头指针的指向,在链表的时候我们是通过二级指针来解决的,这里用一个新的方法;即将队尾指针和队头指针存放到一个结构体中,通过传结构体指针来访问头指针和尾指;同时还可以在结构体中放一个int记录队列中有效数据的个数

typedef int QueueDateType;
typedef struct QueueNode
{
	struct Queue* next;    //指向下一个的位置
	QueueDateType val;      //存储的数据
}QNode;                     //节点的结构体
typedef struct Queue
{
	QNode* plist;      //指向队头的指针
	QNode* tail;       //指向队尾的指针
	int size;           //有效数据的个数
}Que;  

2.1功能函数的实现

队列一般需要这样几个功能:

  1. 初始化队列
  2. 队头入数据
  3. 队尾出数据
  4. 取队头数据
  5. 取队尾数据
  6. 获取队列中有效数据个数
  7. 判断队列是否为空
  8. 队列的销毁

1.初始化队列

void QueInit(Que* pq)
{
	assert(pq);
	pq->plist = pq->tail = NULL;       //先置空处理
	pq->size = 0;
}

2.队头入数据

void QuePush(Que* pq, QueueDateType x)
{
	assert(pq);
	QNode* newnode = (QNode* )malloc(sizeof(QNode));    //创建一个节点
	if (newnode == NULL)
	{
		perror("malloc fail");      //判断
		exit(-1);
	}
	newnode->next = NULL;     //将后节点置空处理
	newnode->val = x;         //赋值
	if (pq->plist == NULL)     //队列为空
	{
		pq->plist= pq->tail = newnode;
	}
	else                        //队列不为空
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;               //有效数据个数++
}

3.队尾出数据

分为两种情况处理:

第一种:队列只有一个数据时,需要处理尾指针

第二种:队列的数据个数大于1时,不需要对尾指针进行处理

void QuePop(Que* pq)
{
	assert(pq);
	assert(pq->size);   //当队列为空时,不出数据
	QNode* tmp = NULL;
	if (pq->size==1)          //当队列的有效数据只有一个时,需要特殊处理
	{                          //因为出队列后,为空列表了,尾指针需要改变
		free(pq->plist);
		pq->plist = pq->tail == NULL;
	}
	else                       //队列不为空,直接头删
	{
		tmp = pq->plist->next;     //先保存下一个节点
		free(pq->plist);            //释放
		pq->plist = tmp;    
	}
	pq->size--;               //有效数据个数--;
}

4.取队头的数据

QueueDateType QueFront(Que* pq)
{
	assert(pq);
	return pq->plist->val;   //直接返回数据
}

5.取队尾的数据

QueueDateType QueBack(Que* pq)
{
	assert(pq);
	return pq->tail->val;    //直接返回数据
}

6.获取队列中有效数据个数

int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

7.判断队列是否为空

bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->plist;
}

8.销毁队列

bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->plist;
}

2.2总代码

#pragma once
#include
#include
#include
#include
typedef int QueueDateType;
typedef struct QueueNode
{
	struct Queue* next;
	QueueDateType val;
}QNode;
typedef struct Queue
{
	QNode* plist;
	QNode* tail;
	int size;
}Que;
void QueInit(Que* pq);
void QueDestory(Que* pq);
void QuePush(Que* pq,QueueDateType x);
void QuePop(Que* pq);
QueueDateType QueFront(Que* pq);
QueueDateType QueBack(Que* pq);
int QueSize(Que* pq);
bool QueEmpty(Que* pq);
#include"Queue.h"
void QueInit(Que* pq)
{
	assert(pq);
	pq->plist = pq->tail = NULL;
	pq->size = 0;
}
void QueDestory(Que* pq)
{
	assert(pq);
	QNode* cur = pq->plist;
	QNode* Next = NULL;
	while (cur)
	{
		Next = cur->next;
		free(cur);
		cur =Next;
	}
	pq->plist = pq->tail == NULL;
}
void QuePush(Que* pq, QueueDateType x)
{
	assert(pq);
	QNode* newnode = (QNode* )malloc(sizeof(QNode));    //创建一个节点
	if (newnode == NULL)
	{
		perror("malloc fail");      //判断
		exit(-1);
	}
	newnode->next = NULL;     //将后节点置空处理
	newnode->val = x;         //赋值
	if (pq->plist == NULL)     //队列为空
	{
		pq->plist= pq->tail = newnode;
	}
	else                        //队列不为空
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;               //有效数据个数++
}
void QuePop(Que* pq)
{
	assert(pq);
	assert(pq->size);   //当队列为空时,不出数据
	QNode* tmp = NULL;
	if (pq->size==1)          //当队列的有效数据只有一个时,需要特殊处理
	{                          //因为出队列后,为空列表了,尾指针需要改变
		free(pq->plist);
		pq->plist = pq->tail == NULL;
	}
	else                       //队列不为空,直接头删
	{
		tmp = pq->plist->next;     //先保存下一个节点
		free(pq->plist);            //释放
		pq->plist = tmp;    
	}
	pq->size--;               //有效数据个数--;
}
QueueDateType QueFront(Que* pq)
{
	assert(pq);
	return pq->plist->val;   //直接返回数据
}
QueueDateType QueBack(Que* pq)
{
	assert(pq);
	return pq->tail->val;    //直接返回数据
}
int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->plist;
}
VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]