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

2024-01-18 18:42:07 浏览数 (1)

之前介绍了栈：探索栈数据结构：深入了解其实用与实现（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）

代码语言：javascript复制
#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）

初始化
代码语言：javascript复制
void QInit(Queue* q)
{
	assert(q);
	q->phead = q->ptail = NULL;
	q->size = 0;
}
  • 将队列的头尾指针设置为 NULL，表示队列为空。
  • 将队列中元素的数量设置为 0，因为队列此时没有任何元素
插入
代码语言：javascript复制
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 分配内存，并设置其值为 x，next 指针指向 NULL
  • 如果队列为空（即头尾指针均为空），则将新节点同时设置为队列的头尾节点。
  • 如果队列不为空，则将新节点连接到队列尾部，并更新尾指针 ptail 指向新的尾节点。
  • 最后，增加队列的大小 size。
删除
代码语言：javascript复制
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
返回最后一个节点数据
代码语言：javascript复制
QDataType QBack(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->ptail->val;
}
返回第一个节点数据
代码语言：javascript复制
QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->ptail);
	return q->phead->val;
}
是否为空
代码语言：javascript复制
bool QEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
节点数量
代码语言：javascript复制
int QSize(Queue* q)
{
	assert(q);
	return q->size;
}
销毁
代码语言：javascript复制
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;
}

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

队列 数据 指针 数据结构 fifo

0 人点赞