【数据结构初阶】--栈和队列(二)

发布于:2025-07-26 ⋅ 阅读:(14) ⋅ 点赞:(0)

🔥个人主页:@草莓熊Lotso

🎬作者简介:C++研发方向学习者

📖个人专栏: 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言:生活是默默的坚持,毅力是永久的享受。

前言: 在上篇博客中我们简单完成了栈这个数据结构的实现,那么这次我们要实现的是队列,队列这个数据结构实现起来也不会很难,还是和之前一样,先部分实现,最后展现全部的代码 


目录

一.队列的概念与结构

二. 队列的入队和出队

入队:

 出队:

 三.队列取队首数据和队尾数据

取队首数据:

取队尾数据 :

 四.队列的有效数据个数和队列的销毁

队列的有效数据个数:

销毁队列:

五.代码展现

Queue.h:

Queue.c:

test.c:


一.队列的概念与结构

--概念:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的特点

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

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

 队列底层结构选型:

队列可以用数组和链表的结构实现,使用链表的结构实现更优一点,如果使用数组的结构,出队列在数组头部出数据,时间复杂度高。虽然使用链表在入队尾插的时候,时间复杂度也高,但我们可以额外定义一个尾结点,这样就可以优化了

结构定义: 

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

二. 队列的入队和出队

--我们实现队列的入队是在队尾操作的,所以我们可以参考链表的尾插,但是这里我们已经定义了一个尾节点了,所以会更简单点

入队:

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newcode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;

	//如果队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newcode;
		//pq->size++;
	}
	else
	{
		pq->ptail->next = newcode;
		pq->ptail = pq->ptail->next;
		//pq->size++;
	}
}

我们入队之前,需要申请一个新的节点,操作起来和链表里面的一样,申请完后先判断链表是不是为空,为空和不为空需要分类讨论,如果为空就直接令头节点和尾节点都为newcode,如果不为空就是在尾节点后链接上新节点,然后尾节点往前走。 

 --在实现出队之前,我们需要考虑到一个队列为空的问题,如果队列为空是不是就不能删了呢,所以我们这里来实现一个判断链表是否为空的接口吧,这个实现起来很简单,就不多说了

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

 出队:

//出队
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//如果队伍中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		//pq->size--||pq->size=0
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		//pq->size--;
	}
}

我们需要注意的是断言结束后,如果队伍只有一个节点,我们直接释放掉后使置为空就行了,如果不止一个节点我们需要先记录下一个节点,再释放,然后让头节点来到下一个节点的位置。


 三.队列取队首数据和队尾数据

取队首数据:

//取队首数据
QDataType QueueHead(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

队首数据不就是头节点的数据吗,直接返回就好了

取队尾数据 :

//取队尾数据
QDataType QueueTail(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

队尾数据不就是头节点的数据吗,直接返回就好了

--实现完前面的接口之后我们可以测试一下看看

 test.c:

#include"Queue.h"

void test1()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	printf("队首是:%d\n",QueueHead(&q));
	printf("队尾是:%d\n",QueueTail(&q));
}

int main()
{
	test1();
}

--测试完成,打印出了队尾和队首数据,退出码为0


 四.队列的有效数据个数和队列的销毁

队列的有效数据个数:

//队列有效数据个数
int QueueSize(Queue* pq)
{
	//如果使用了size记录直接返回就可以了
	//return pq->size;

	//如果没有就遍历
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur=pcur->next;
	}
	return size;
}

这里给大家提供了两种写法,一个是前面定义了size的,一个是没有定义过的,没有定义的我们需要遍历计数,最后再返回就行了。 

销毁队列:

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

遍历队列,每次销毁前存下下一个节点,销毁当前节点后来到下一个节点的位置,最后遍历结束后把pq->phead和pq->ptail都置为空

--这里也可以通过测试文件打印观察数据个数,就不在这里展示了,大家可以直接看一下代码展现里面 


五.代码展现

Queue.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

//队列的初始化
void QueueInit(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);

//队列判空
bool QueueEmpty(Queue* pq);

//出队
void QueuePop(Queue* pq);

//取队首数据
QDataType QueueHead(Queue* pq);

//取队尾数据
QDataType QueueTail(Queue* pq);

//队列有效数据个数
int QueueSize(Queue* pq);

//队列的销毁
void QueueDestory(Queue* pq);

Queue.c:

#include"Queue.h"

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	//pq->size = 0;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newcode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;

	//如果队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newcode;
		//pq->size++;
	}
	else
	{
		pq->ptail->next = newcode;
		pq->ptail = pq->ptail->next;
		//pq->size++;
	}
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//出队
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//如果队伍中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		//pq->size--||pq->size=0
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		//pq->size--;
	}
}

//取队首数据
QDataType QueueHead(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾数据
QDataType QueueTail(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//队列有效数据个数
int QueueSize(Queue* pq)
{
	//如果使用了size记录直接返回就可以了
	//return pq->size;

	//如果没有就遍历
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur=pcur->next;
	}
	return size;
}

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

test.c:

#include"Queue.h"

void test1()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	printf("队首是:%d\n",QueueHead(&q));
	printf("队尾是:%d\n",QueueTail(&q));
	printf("size:%d\n", QueueSize(&q));

	QueueDestory(&q);
}

int main()
{
	test1();
}


往期回顾:

【数据结构初阶】--双向链表(一)

【数据结构初阶】--双向链表(二)

【数据结构初阶】--栈和队列(一)

结语:队列的实现就到此结束了,栈和队列这块的知识点和实现起来都比较快,但是后面的二叉树的难度就上来了,大家一定要先把前面这些搞懂并且实现出来,不然后续会比较吃力的,如果文章对你有帮助的话,欢迎评论,点赞,收藏加关注,感谢大家的支持


网站公告

今日签到

点亮在社区的每一天
去签到