当前位置： 首页 > news >正文

详解数据结构之队列、循环队列(源码)

news 来源：原创 2024/9/20 8:13:03

详解数据结构之队列、循环队列(源码)

队列属于线性表

队列：就好比如，我们在排队买东西时排队，第一个先来的第一个买，最后一个到的最后一个买，这里的队列也是满足先进先出，后进后出的规律（First In First Out），允许插入数据的一端叫做队头简称入队列，允许删除数据的一端叫做队尾简称出队列。

队列的存储形式：

  • 顺序存储结构，实现循环队列 ，队列长度时固定的

  • 链式存储结构，实现不循环队列，队列长度理论上是无限大的

两种存储结构实现的队列复杂度：

  • 时间复杂度 O(1)
  • 空间复杂度 O(1)

队列

使用链式结构实现的队列，其基本结构类似于单链表。使用next指针将每一个节点链接。主要区别在于没有使用一个指针来指向节点，这里定义了两个指针指针单链表，一个phead指针指向单链表的头，一个ptail指针指向单链表的尾。

单链表的头为队列的队头，单链表的尾为队列的队尾。

在这里插入图片描述

有了指针指向链表的最后一个节点，就不再需要使用循环遍历到链表的最后一个节点，将入栈的时间复杂度从O(N)优化到O(1)。

typedef int QueueDataType;
typedef struct QueueNode//节点
{QueueDataType val;struct QueueNode* next;}QueueNode;
struct Queue
{QueueNode* phead;//指向队头的指针QueueNode* ptail;//指向队尾的指针int size;//统计单链表的节点个数
};
typedef struct Queue Queue;

功能实现

//初始化
void QueueInit(Queue* p);
//销毁
void QueueDestory(Queue* p);
//入队列，队尾,不就是尾插
void QueuePush(Queue* p, QueueDataType x);
//出队列，队头
void QueuePop(Queue* p);
//取队头数据
QueueDataType QueueFront(Queue* p);
//取队尾数据
QueueDataType QueueBack(Queue* p);
//判空
bool QueueEmpty(Queue* p);
//获取有效数据个数
int QueueSize(Queue* p);

初始化、销毁

初始化

初始化指向队列的两个指针，和对统计节点个数大小的size，由于传递的是地址就不需要返回值。

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

销毁

将队列的节点一一销毁，其操作逻辑与单链表相似。

销毁链表，需要对每一个节点进行释放，而只使用一个指针pcur，释放当前的节点就找不到下一个节点了，这里需要使用两个指针。

一个指针用来释放（pcur），一个指针用来指向待释放之后的节点（next）。

当释放完pcur节点后，更新pcur的位置 pcur = next;，用来释放下一个节点，next指针也需要更新用来指向下一个节点 next = pcur->next;，用来对pcur进行更新。直到pcur指向空指针时释放完所有节点，跳出循环。而 phead和ptail指针，还没有置为空，这时候时野指针，最后一步 p->phead = p->ptail = NULL;。

void QueueDestory(Queue* p)
{assert(p);QueueNode* pcur = p->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}p->phead = p->ptail = NULL;p->size = 0;
}

判空

判断队列的节点是否为空并返回一个布尔值。

如上对队列的初始化，两个头尾指针指向的都为空，此时队列就是空，队列为空返回true，不为返回false。

函数起始别忘了对指针p判空，为空则说明队列不存在了。

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

入队列、出队列

入队列

想要进行尾插首先得有一个指针指向最后一个节点，然后将创建的新节点插入到该节点后面，最后更新ptail指针指向的位置
在这里插入图片描述

入队列有两种情况：

  • 队列为空

此时phead和ptail都指向空，插入一个新节点，phead和ptail均指向它。

  • 队列不为空

在ptail指针后插入一个新节点，通过节点的next指针连接，然后更新ptail指针，让其指向新的尾。
在这里插入图片描述

最后别忘了将统计节点个数的size加1。

//入队列，队尾,不就是单链表的尾插
void QueuePush(Queue* p, QueueDataType x)
{assert(p);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//创建新节点if (newnode == NULL)//判空，有无开辟成功{perror("malloc");return;}newnode->val = x;//赋值newnode->next = NULL;if (p->phead == NULL)//phead和ptail为空时{p->phead = p->ptail = newnode;}else//两者不为空{p->ptail->next = newnode;p->ptail = newnode;}p->size++;//别忘了记录新加入的节点
}

出队列

出队列的逻辑并不复杂，前提是指针p不为空，为空则说明队列不存在、队列不为空，为空则说明没有节点可删，接下来就是对空指针解引用。

它同样分为两种情况：

  • 只有一个节点

即phead和ptail指向同一个节点时，将该节点释放，然后将phead和ptail指针指向空。

  • 有许多个节点

一，保存phead之后的节点 QueueNode* Next = phead->next;二，然后释放第一个节点 free(phead);三，最后将 Next 赋给 phead，更新头节点的位置。

最后将size减1。
在这里插入图片描述

//出队列，队头,这不就是单链表的头删吗
void QueuePop(Queue* p)
{assert(p);assert(!QueueEmpty(p));if (p->phead == p->ptail){free(p->phead);p->phead = p->ptail == NULL;}else{QueueNode* Next = p->phead->next;free(p->phead);p->phead = Next;}p->size--;
}

取队头数据、取队尾数据

取对头数据

取对头数据那是相当简易，只需要将头指针指向的节点的value值返回即可。需要注意的是对指针p和队列的判空，以及返回数据的类型。

//取队头数据
QueueDataType QueueFront(Queue* p)
{assert(p);assert(!QueueEmpty(p));return p->phead->val;
}

取队尾数据

有了之前定义的ptail指针，就不需要像单链表一个一个节点的遍历到最后一个节点，取队尾数据，只需将尾指针指向的节点的value值返回即可，它需要注意的点与取对头数据相同。

//取队尾数据
QueueDataType QueueBack(Queue* p)
{assert(p);assert(!QueueEmpty(p));return p->ptail->val;
}

取队列有效数据个数

将队列的size返回，返回值为int，因为它只是用来统计个数的。

//获取有效数据个数
int QueueSize(Queue* p)
{assert(p);return p->size;
}

源码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType val;struct QueueNode* next;}QueueNode;
struct Queue
{QueueNode* phead;//指向队头的指针QueueNode* ptail;//指向队尾的指针int size;
};
typedef struct Queue Queue;//初始化
void QueueInit(Queue* p);
//销毁
void QueueDestory(Queue* p);
//入队列，队尾,不就是尾插
void QueuePush(Queue* p, QueueDataType x);
//出队列，队头
void QueuePop(Queue* p);
//取队头数据
QueueDataType QueueFront(Queue* p);
//取队尾数据
QueueDataType QueueBack(Queue* p);
//判空
bool QueueEmpty(Queue* p);
//获取有效数据个数
int QueueSize(Queue* p);

Queue.c

#include "Queue.h"
//初始化
void QueueInit(Queue* p)
{assert(p);p->phead = p->ptail = NULL;p->size = 0;
}
//判空
bool QueueEmpty(Queue* p)
{assert(p);return p->ptail == NULL && p->phead == NULL;
}
//入队列，队尾
void QueuePush(Queue* p, QueueDataType x)
{assert(p);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");return;}newnode->val = x;newnode->next = NULL;if (p->phead == NULL){p->phead = p->ptail = newnode;}else{p->ptail->next = newnode;p->ptail = newnode;}p->size++;
}
//出队列，队头
void QueuePop(Queue* p)
{assert(p);assert(!QueueEmpty(p));if (p->phead == p->ptail){free(p->phead);p->phead = p->ptail == NULL;}else{QueueNode* Next = p->phead->next;free(p->phead);p->phead = Next;}p->size--;
}
//取队头数据
QueueDataType QueueFront(Queue* p)
{assert(p);assert(!QueueEmpty(p));return p->phead->val;
}
//取队尾数据
QueueDataType QueueBack(Queue* p)
{assert(p);assert(!QueueEmpty(p));return p->ptail->val;
}
//获取有效数据个数
int QueueSize(Queue* p)
{assert(p);return p->size;
}
//销毁
void QueueDestory(Queue* p)
{assert(p);QueueNode* pcur = p->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}p->ptail = p->ptail = NULL;p->size = 0;
}

循环队列

循环队列，就类似将链表的头尾节点链接在一起了。

使用顺序存储结构的优缺点：

优

  • 数组支持随机访问，在O(1)时间内访问任意元素（速度）
  • 数组的操作和使用简单好理解
  • 不需要使用额外空间存储节点指针

缺

  • 数组的大小在创建时就确定了
typedef int CQDataType;
typedef struct CircularQueue
{CQDataType* arr;int front;//指向队头元素int rear;//指向队尾的下一个位置int capacity;//空间大小
}CQueue;

在这里插入图片描述

初始情况下，front和rear指向同体块空间时，队列为空，入队列后front不变，rear向后加1，如下图。
在这里插入图片描述

当插入a5时rear将指向数组外的空间，然后在插入a6，rear继续指向数组之外的空间。纳尼？？都指向数组之外的空间了，那不是越界访问了吗？

在这里插入图片描述

现在假设不存在这种问题，插入a5数据后rear指向front，此时有没有发现又乱套了。front和rear指向了同一块空间，前文以及说过当frong和rear指向同一块空间时队列为空，那这种情况又该咋办呢~。
在这里插入图片描述

为了解决以上两种情况，这里将数组空出一块空间，不插入a5此时队列就是满队列的情况。

而想要实现rear为4时在加上1能够循环到0，可以使用求模运算操作符。

在这里插入图片描述

初始条件下开辟给数组capacity+1的空间，多余的1是给rear用的，防止font和rear相等无法判断是否满队列还是空队列的情况。假设此时capacity为4，那就得开辟空间大小为5的数组，如上图。

pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;如上图，此时rear为4，capacity为4，都加1后 5 % 5结果为刚好等于front此时满队列，而不是如同之前的情况，rear和front的尴尬情况。

在这里插入图片描述

实现rear加1后能够在 0 ~ 4内循环，而不造成数组越界访问使用取模操作符 ，如上图，当rear为4时加1为5，但它指向了0，根据pcq->rear = pcq->rear % pcq->capacity + 1;不能得出 此时 5 % 5的结果为0，然后将0赋给rear重置了rear的位置。

功能实现

//开辟空间，n指开辟大小
void CQCreat2(CQueue* pcq, int n);
//判断队列空否
bool CQEmpty(CQueue* pcq);
//判断队列满否
bool CQFull(CQueue* pcq);
//入队列
void CQPush(CQueue* pcq, CQDataType x);
//出队列
void CQPop(CQueue* pcq);
//取队头元素
CQDataType CQFront(CQueue* pcq);
//取队尾元素
CQDataType CQBACK(CQueue* pcq);
//销毁队列
void CQDestory(CQueue* pcq);

开辟空间、销毁队列

开辟空间、初始化

开辟大小为n + 1的空间，让后将front和rear置0，将n赋给capacity，表示了rear和front的最大取值。

void CQCreat2(CQueue* pcq, int n)
{pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1));pcq->front = pcq->rear = 0;pcq->capacity = n;
}

销毁队列

销毁队列，将arr数组释放，让后置空（此时为野指针），需要注意的是对 pcq->arr，的判空，若它为空指针就不需要释放数组。

//销毁队列
void CQDestory(CQueue* pcq)
{assert(pcq);if(pcq->arr)free(pcq->arr);pcq->arr = NULL;pcq->front = pcq->rear = pcq->capacity = 0;
}

判断队列满否、空否

判断队列是否被放满

前文以及提过，判空后队列满返回真，队列未满返回假，使用assert断言避免pcq为空指针，从而造成对空指针的解引用。

//判断队列满否
bool CQFull(CQueue* pcq)
{assert(pcq);return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;
}

判断队列是否为空队列

front与rear相等队列为空返回真，不相等返回假。

//判断队列空否
bool CQEmpty(CQueue* pcq)
{assert(pcq);return pcq->front == pcq->rear;//相等为空
}

入队列、出队列

入队列

入队列不难理解，只需要找到对应得数组标然后放进去即可。但需要严重关注的是在入队列前对数组是否满了进行判断，以及成功入了一个元素rear加1后，对rear重新修正大小，避免造成数组越界。

//入队列
void CQPush(CQueue* pcq, CQDataType x)
{assert(pcq);assert(!CQFull(pcq));pcq->arr[pcq->rear++] = x;pcq->rear %= pcq->capacity + 1;
}

出队列

出队列，同理出队列，想要出队列那就不可能对一个空队列出元素，那得先调用判断队列是否为空队列的函数，然后在出队列，想要实现出队列，只需要让front加1即可，前front指向的数据被放弃掉是无效的，将front加1后同rear一样需要对其重新修正大小，避免造成数组越界。

//出队列
void CQPop(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));pcq->front++;pcq->front %= pcq->capacity + 1;
}

取对头数据、取队尾数据

取对头数据

只需将front指向的数据返回。

//取队头元素
CQDataType CQFront(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));return pcq->arr[pcq->front];
}

取队尾数据

只需将rear指向的数据返回。

//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));int ret = pcq->rear - 1;if (pcq->rear == 0){ret = pcq->capacity;}return pcq->arr[ret];
}

源码

CircularQueue.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int CQDataType;
typedef struct CircularQueue
{CQDataType* arr;int front;int rear;int capacity;
}CQueue;//开辟空间，n指开辟大小
CQueue* CQCreat(int n);
void CQCreat2(CQueue* pcq, int n);
//判断队列空否
bool CQEmpty(CQueue* pcq);
//判断队列满否
bool CQFull(CQueue* pcq);
//入队列
void CQPush(CQueue* pcq, CQDataType x);
//出队列
void CQPop(CQueue* pcq);
//取队头元素
CQDataType CQFront(CQueue* pcq);
//取队尾元素
CQDataType CQBACK(CQueue* pcq);
//销毁队列
void CQDestory(CQueue* pcq);

CircularQueue.c

#include "Queues.h"
//开辟空间，n指开辟大小
void CQCreat2(CQueue* pcq, int n)
{pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1));pcq->front = pcq->rear = 0;pcq->capacity = n;
}
//判断队列空否
bool CQEmpty(CQueue* pcq)
{assert(pcq);return pcq->front == pcq->rear;//相等为空
}
//判断队列满否
bool CQFull(CQueue* pcq)
{assert(pcq);return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;
}
//入队列
void CQPush(CQueue* pcq, CQDataType x)
{assert(pcq);assert(!CQFull(pcq));pcq->arr[pcq->rear++] = x;pcq->rear %= pcq->capacity + 1;
}
//出队列
void CQPop(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));pcq->front++;pcq->front %= pcq->capacity + 1;
}
//取队头元素
CQDataType CQFront(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));return pcq->arr[pcq->front];
}
//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));int ret = pcq->rear - 1;if (pcq->rear == 0){ret = pcq->capacity;}return pcq->arr[ret];
}
//销毁队列
void CQDestory(CQueue* pcq)
{assert(pcq);free(pcq->arr);pcq->arr = NULL;pcq->front = pcq->rear = pcq->capacity = 0;
}Type x)
{assert(pcq);assert(!CQFull(pcq));pcq->arr[pcq->rear++] = x;pcq->rear %= pcq->capacity + 1;
}
//出队列
void CQPop(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));pcq->front++;pcq->front %= pcq->capacity + 1;
}
//取队头元素
CQDataType CQFront(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));return pcq->arr[pcq->front];
}
//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{assert(pcq);assert(!CQEmpty(pcq));int ret = pcq->rear - 1;if (pcq->rear == 0){ret = pcq->capacity;}return pcq->arr[ret];
}
//销毁队列
void CQDestory(CQueue* pcq)
{assert(pcq);free(pcq->arr);pcq->arr = NULL;pcq->front = pcq->rear = pcq->capacity = 0;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • filebeat，kafka，clickhouse，ClickVisual搭建轻量级日志平台
  • 【Spring Security】初识Spring Security
  • Web 3.0革新：社交金融与边玩边赚开启用户数据主权时代
  • Spring Data Jpa 原生SQL联表查询返回自定义DTO
  • 低空经济未来出行，evtol飞行器技术前景分析
  • 三字棋游戏（C语言详细解释）
  • layui 监听弹窗关闭并刷新父级table
  • 应用层——HTTP
  • 42、PHP 实现把二叉树打印成多行
  • 【补】【康复学习--LeetCode每日一题】1186. 删除一次得到子数组最大和
  • 企业级-PDF图片水印
  • 【React】事件绑定、React组件、useState、基础样式
  • 如何理解ref toRef和toRefs
  • 问题记录-Spring Security- bean httpSecurity not found
  • HarmonyOS Web组件（二）
  • 【从零开始安装kubernetes-1.7.3】2.flannel、docker以及Harbor的配置以及作用
  • java概述
  • Koa2 之文件上传下载
  • LeetCode刷题——29. Divide Two Integers（Part 1靠自己）
  • MySQL的数据类型
  • MySQL数据库运维之数据恢复
  • React系列之 Redux 架构模式
  • Storybook 5.0正式发布：有史以来变化最大的版本\n
  • Twitter赢在开放，三年创造奇迹
  • 分享几个不错的工具
  • 机器学习中为什么要做归一化normalization
  • 使用阿里云发布分布式网站，开发时候应该注意什么？
  • 数据库写操作弃用“SELECT ... FOR UPDATE”解决方案
  • 小程序上传图片到七牛云（支持多张上传，预览，删除）
  • 学习笔记：对象，原型和继承（1）
  • 一份游戏开发学习路线
  • 再次简单明了总结flex布局，一看就懂...
  • ​2020 年大前端技术趋势解读
  • ​经​纬​恒​润​二​面​​三​七​互​娱​一​面​​元​象​二​面​
  • ​力扣解法汇总1802. 有界数组中指定下标处的最大值
  • ​学习一下，什么是预包装食品？​
  • ###51单片机学习（1）-----单片机烧录软件的使用，以及如何建立一个工程项目
  • #宝哥教你#查看jquery绑定的事件函数
  • ()、[]、{}、(())、[[]]等各种括号的使用
  • （1）svelte 教程：hello world
  • （3）(3.5) 遥测无线电区域条例
  • （3）选择元素——（17）练习（Exercises）
  • （Oracle）SQL优化技巧（一）：分页查询
  • （第27天）Oracle 数据泵转换分区表
  • （附源码）spring boot公选课在线选课系统 毕业设计 142011
  • （附源码）springboot社区居家养老互助服务管理平台 毕业设计 062027
  • （五）网络优化与超参数选择--九五小庞
  • （学习日记）2024.03.25：UCOSIII第二十二节：系统启动流程详解
  • （自用）learnOpenGL学习总结-高级OpenGL-抗锯齿
  • ../depcomp: line 571: exec: g++: not found
  • .net core 连接数据库，通过数据库生成Modell
  • .net framework 4.8 开发windows系统服务
  • .NET Framework Client Profile - a Subset of the .NET Framework Redistribution
  • .NET 中让 Task 支持带超时的异步等待
  • .NET/C# 的字符串暂存池