深入了解队列:探索FIFO数据结构及队列

发布时间:2023年12月26日

之前介绍了栈:探索栈数据结构:深入了解其实用与实现(c语言实现栈)

那就快马加鞭来进行队列内容的梳理。队列和栈有着截然不同的工作方式,队列遵循先进先出(FIFO)的原则,在许多场景下都表现出强大的效率和实用性

源码可以来我的github进行查找:Nerosts/just-a-try: 学习c语言的过程、真 (github.com)



1.队列的概念及结构

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

入队列:进行插入操作。此端称为队尾

出队列:进行删除操作。此段称为队头

请添加图片描述

假设入队:A B C D

那么出队:A B C D


2.队列的实现

队列也可以数组和链表的结构实现,使用链表的结构来实现更适合一些,因为使用数组的结构,出队列这个操作在数组头上出数据(届时会需要全体移动),效率会比较低

2.1项目文件规划

请添加图片描述

  • 头文件Queue.h:用来基础准备(常量定义,typedef),链表表的基本框架,函数的声明
  • 源文件Queue.c:用来各种功能函数的具体实现
  • 源文件test.c:用来测试功能是否有问题,进行基本功能的使用

2.2基本结构及各功能(Queue.h)

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

typedef int QDataType;

typedef struct QueueNode//节点的结构体
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size; //元素数量(空间换时间)
}Queue;

void QInit(Queue* q);//初始化
void QDestroy(Queue* q);//销毁

void QPush(Queue* q, QDataType x);//插入
void QPop(Queue* q);//删除

QDataType QBack(Queue* q);//返回最后一个节点数据
QDataType QFront(Queue* q);//返回第一个节点数据

bool QEmpty(Queue* q);//是否为空

int QSize(Queue* q);//元素数量

这两个结构体组合在一起,构成了队列数据结构的基本框架

  • QNode 结构体用于表示队列中的节点

  • Queue 结构体则用于管理整个队列的状态和属性

    这种设计使得队列的操作和功能得以清晰地表现和实现

2.3各功能具体实现(Queue.c)

初始化

void QInit(Queue* q)
{
	assert(q);
	q->phead = q->ptail = NULL;
	q->size = 0;
}
  • 将队列的头尾指针设置为 NULL,表示队列为空。
  • 将队列中元素的数量设置为 0,因为队列此时没有任何元素

插入

void QPush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);//防止没有开辟成功(当人有点杞人忧天了)
	newnode->val = x;
	newnode->next = NULL;

	if (q->phead == NULL)
	{
		q->phead = q->ptail = newnode;
	}
	else
	{
		q->ptail->next = newnode;
		q->ptail = newnode;
	}
	q->size++;
}
  • 首先使用 assert 确保传入的队列指针 q 是有效的
  • 为新节点 newnode 分配内存,并设置其值为 xnext 指针指向 NULL
  • 如果队列为空(即头尾指针均为空),则将新节点同时设置为队列的头尾节点。
  • 如果队列不为空,则将新节点连接到队列尾部,并更新尾指针 ptail 指向新的尾节点。
  • 最后,增加队列的大小 size

删除

void QPop(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	QNode* next = q->phead->next;
	free(q->phead);
	q->phead = next;
	//当只有一个节点时:把	q->ptail = NULL;
	if (q->phead == NULL)
	{
		q->ptail = NULL;
	}
	q->size--;
}
  • 首先使用 assert 确保传入的队列指针 q 是有效的,并且队列中有元素即(size > 0
  • 通过 next 指针将队列头部的下一个节点保存下来,以备后续更新
  • 释放队列当前的头节点
  • 更新队列的头指针为下一个节点(如果有的话)
  • 如果删除节点后队列为空==(只有一个节点),则将尾指针 ptail 也设置为 NULL(一个节点时,二者指向同一个地址)==
  • 最后,减少队列的大小 size

返回最后一个节点数据

QDataType QBack(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->ptail->val;
}

返回第一个节点数据

QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->phead->val;
}

是否为空

bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

节点数量

int QSize(Queue* q)
{
	assert(q);
	return q->size;
}

销毁

void QDestroy(Queue* q)
{
	QNode* cur = q->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->phead = q->ptail = NULL;
	q->size = 0;
}

队列的内容也整理完毕了,下一次会为大家带来二叉树和堆的相关内容,感谢大家的支持!!!

文章来源:https://blog.csdn.net/qq_74415153/article/details/135211801
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。