数据结构之《队列》

🕗 发布于 2024-07-26 03:05 c语言 学习 数据结构

在数据结构之《栈》章节中学习了线性表中除了顺序表和链表外的另一种结构——栈，在本篇中我们将继续学习另一种线性表的结构——队列，在通过本篇的学习后，你将会对栈的结构有充足的了解，在了解完结构后我们还将进行栈的实现。一起加油吧！！！

1.队列的结构与定义

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

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

那么在队列的底层结构应该选择的是数组还是链表呢？接下来就来分析看看

在使用数组作为队列的底层结构时，由于队列的性质要求先进先出，所以可以使用size来表示数组内的有效元素个数，这样在入队列时就可以直接在数组的size位置插入数据，但是在出队列时为了将数组内的首个元素也就是数组下标为0的位置移除，这就需要将数组从下标为1的位置开始整体都向前移动一位，所以在出队列的时间复杂度为O(N)

在使用单链表作为队列的底层结构时，由于队列的性质要求先进先出，所以如果只用一个phead指针指向链表的第一个节点，那么就会使得在入队列时要找到链表的尾节点就需要通过遍历链表才能实现，这就会使得时间复杂度为O(N),所以为了解决以上这种缺陷，就在创建一个指针指向链表的尾节点，在入队列是就可以直接找到尾节点，这样就可以使得无论是入队列还是出队列时间复杂度都为O(1)

通过以上的分析就可以得出在实现队列时底层结构选择单链表是最优解

2.队列的实现

在实现队列的代码中，在Queue.h头文件中定义队列的结构以及队列中各个函数的声明，在Queue.c文件内完成各个函数的定义，在test.c文件内对实现的各个函数进行测试

2.1队列结构的定义

在队列结构的定义中，创建一个结构体QueueNode来表示节点，该节点内部有两个成员变量，data来存放节点的数据，next指针来存放下一个节点的地址；之后还需再创建一个结构体Queue来存放指向链表的第一个节点和尾节点的指针，并且在这个结构体内还创建一个成员变量size来表示链表中节点的个数，这样是为了在之后的计算队列有效数据个数时直接将size的值提取出来就可实现了

//队列结构的定义
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;//节点内的数据
struct QueueNode* next;//指向下一个节点的指针

}QueueNode;

typedef struct Queue
{
struct QueueNode* phead;//指向第一个节点的指针
struct QueueNode* ptail;//指向尾节点的指针
int size;//节点的个数

}Queue;

2.2队列的初始化

要完成队列的初始化函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueInit，函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言

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

2.2判断队列是否为空

要完成队列判空函数首先要在Queue.h内完成函数的声明

bool QueueEmpty(Queue* pq);

将该函数命名为QueueEmpty，函数的为存放指向头尾节点指针的结构体指针，函数的放回类型是布尔类型，当队列为空时放回true，不为空就放回false

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言

在队列为空时就是指向第一个队列的指针phead和指向队列的尾部的指针ptail都为空，所以该函数的返回值就为pq->phead ==NULL && pq->ptail == NULL

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

2.3入队列

要完成入队列函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueuePush，函数的参数有两个，第一个为存放指向头尾节点指针的结构体指针,第二个为要插入的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
在实现数据的入队列前要为数据申请新的节点空间，在此使用malloc来实现，申请完之后在将要入队列的数据x存放到新节点newnode中，之后在将新节点插入到链表时要分以下两种情况，一种是phead指针指向为空时也就是这时链表内一个节点都没有，这时就要将phead和ptail都newnode；另外一种情况是phead指针指向不为空时，这时就先使得ptail的next指针指向newnode，之后再将ptail指向新节点newnode
最后在完成以上操作后要将有效个数size+1

//入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead== NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}

2.4出队列

要完成出队列函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueuePop，函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言

之后在出队列也就是删除单链表的第一个节点时分为以下两种情况，第一种是指针phead和指针ptail指向同一个节点也就是链表中只有一个节点，这时就直接释放该节点，之后再将phead和ptail置为空；另外一种情况是指针phead和指针ptail不相同，这时就先创建一个新的指针变量Next指向原来的phead的next指针指向的节点，之后将phead指向的节点释放后，在将phead指针置为Next指向的节点

最后在完成以上操作后要将有效个数size-1

//出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* Next = pq->phead->next;
free(pq->phead);
pq->phead = Next;
}
pq->size--;

}

2.5取队列头数据

要完成取队列头数据函数首先要在Queue.h内完成函数的声明

//取队列头数据
QDataType QueueFront(Queue* pq);

将该函数命名为QueueFront，函数的参数存放指向头尾节点指针的结构体指针，函数的放回值就为队列的头数据也就是单链表的第一个节点存放的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言
在队列中的头数据就为phead指针指向的节点内存放的数据
因此该函数直接放回pq->phead->data即可

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

2.6取队尾数据

要完成取队列尾数据函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueBack，函数的参数为存放指向头尾节点指针的结构体指针，函数的放回值就为队列的尾数据也就是单链表的最后一个节点存放的数据

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言
在队列中的尾数据就为ptail指针指向的节点内存放的数据
因此该函数直接放回pq->ptail->data即可

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

2.7队列有效数据个数

要完成队列有效数据个数函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueSize，函数的参数为存放指向头尾节点指针的结构体指针，函数的返回值就为队列内有效的数据个数

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
因为队列内的有效数据个数就为结构体Queue内的成员变量size的值
所以该函数直接放回pq->size即可

//队列有效数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

2.8队列的销毁

要完成队列的销毁函数首先要在Queue.h内完成函数的声明

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

将该函数命名为QueueDestory， 函数的参数为存放指向头尾节点指针的结构体指针

完成了函数的声明接下来就是在Queue.c函数内完成函数的定义

因为以下函数中的pq指针是存放指向头尾节点指针的结构体指针，该指针不能为空，因此要将pq进行assert断言
同时在出队列时队列内不能一个节点都没有，所以要判断队列内不为空，因此要将!QueueEmpty进行assert断言

在销毁过程中通过遍历的方法来用free释放链表的所有节点，最后再将指针phead和指针ptail置为空，将有效数据个数赋值为0

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

3.队列实现完整代码

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
{
struct QueueNode* phead;//指向第一个节点的指针
struct QueueNode* ptail;//指向尾节点的指针
int size;//节点的个数

}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"

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

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

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



//入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead== NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}





//出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* Next = pq->phead->next;
free(pq->phead);
pq->phead = Next;
}
pq->size--;

}

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

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

}

//队列有效数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

原文地址：https://blog.csdn.net/2303_81098358/article/details/140687181

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：2024新版黑马程序员《C++零基础入门》笔记——第一章03 符号常量
下一篇：【组件协作】模板方法

linux线程cp模型，posix信号量，线程池，线程封装，单例模型，懒汉饿汉实现方式，自旋锁，读者写者模型
前面的同步，我们并没有一个很好的场景来模拟同步，只是简单的将有序的现象输出出来；现在我们来讲解一个比较合理且常见的模型——生产者消费者模型；
阅读更多2024-09-07
Qt/C++开源项目 TCP服务器调试助手（源码分享+发布链接下载）
该TCP服务器调试助手是用于测试和监控基于TCP协议的网络通信工具，能够帮助开发者便捷地进行网络通信调试。通过简洁的界面设计，用户可以轻松配置、管理TCP端口的连接，收发消息并进行数据监控分析。123
阅读更多2024-09-07
vue3整合antv x6实现图编辑器快速入门
例如：在上面节点基础上，我们有一个新的需求：给节点加上右键菜单。X6 支持使用 SVG、HTML 来渲染节点内容，在此基础上，我们还可以使用 React、Vue 组件来渲染节点，这样在开发过程中会非常
阅读更多2024-09-07
linux使用samba共享目录，其他虚拟机和windows都可以访问
linux使用samba共享目录，其他虚拟机和windows都可以访问
阅读更多2024-09-07
Linux系统编程实现ls -l | wc -l指令
由于该指令是通过管道的形式实现的，所以我们要使用系统函数pipe。ls -l |wc -l的作用就是统计当前目录有多少文件。由于父子间通过管道实现，所以存在读写阻塞问题，不用担心僵尸进程的产生，所以可
阅读更多2024-09-07
MySQL表操作及约束
MySQL表操作及约束
阅读更多2024-09-07
1.2CubeMAX创建FREERTOS入门示例
内核参数设置，用户根据自己的实际应用来裁剪定制。：相关宏的定义，可以自建一些常量在工程中使用。User Constants（用户常量）：定时器和信号量的创建。：用于查看堆使用情况。：任务与队列
阅读更多2024-09-07
YOLOv9改进策略【注意力机制篇】| PSA极化自我关注：实现高质量像素回归
本文记录的是基于PSA注意力模块的YOLOv9目标检测方法研究。PSA模块。本文将其应用到YOLOv9的检测任务中，使模型能够更好地捕捉图像中的细节信息，以实现目标检测任务中准确识别和定位。
阅读更多2024-09-07
爆改YOLOv8|利用yolov10的SCDown改进yolov8-下采样
yolov8改进，yolov10, 下采样SCDown, 即插即用
阅读更多2024-09-07
PDF样本图册转换为一个链接，随时打开无需印刷
想象一下，您手中有一本厚重的样本图册，里面包含了丰富多样的内容，如产品介绍、项目方案、学术论文等。在过去，您需要逐一翻阅、筛选，甚至为了便于查看，不得不将其印刷出来。如今，借助先进的数字化技术，还能实
阅读更多2024-09-07

数据结构之《队列》

1.队列的结构与定义

2.队列的实现

2.1队列结构的定义

2.2队列的初始化

2.2判断队列是否为空

2.3入队列

2.4出队列

2.5取队列头数据

2.6取队尾数据

2.7队列有效数据个数

2.8队列的销毁

3.队列实现完整代码

Queue.h

Queue.c

相关文章