队列与循环队列

目录

1. 前言:

2. 队列

2.1 队列的概念

2.2 队列的实现

2.3 队列的声明

2.4 队列的初始化

2.5 队列的入队

2.6 队列的出队

2.7 队列获取队头元素

2.8 队列获取队尾元素

2.9 队列获取有效数据个数

2.10 队列判断是否为空

2.11 打印队列

2.12 销毁队列

3. 队列完整代码

3.1 Queue.h

3.2 Queue.c

4. 循环队列

4.1 循环队列的概念

​编辑4.2 循环队列的实现

4.3 循环队列的声明

4.4 循环队列的初始化

4.5 循环队列判空

 4.6 循环队列判满

4.7 循环队列入队

4.8 循环队列出队

4.9 循环队列获取队头数据

4.10 循环队列获取队尾数据

4.11 循环队列获取有效数据个数

4.12 循环队列销毁

5. 循环队列完整代码

5.1 CircularQueue.h

5.2 CircularQueue.c


1. 前言:

在之前我们学习了栈,我们知道栈的特点是后进先出,我们今天学习的队列,它是先进先出的

2. 队列

2.1 队列的概念

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

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

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

2.2 队列的实现

其实队列和栈一样,也是可以使用顺序表和单链表来实现的,这里本章主要讲述使用单链表来实现队列。

Queue.h

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

typedef int QDataType;

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

typedef struct Queue
{
	//记录队头
	qn* phead;
	//记录队尾
	qn* ptail;
	//记录队列有效数据个数
	int size;
}q;

//初始化队列
void QInit(q* pq);
//入队
void QPush(q* pq, QDataType x);
//出队
void QPop(q* pq);
//获取队头元素
QDataType QFront(q* pq);
//获取队尾元素
QDataType QBack(q* pq);
//获取队列内有效数据个数
int QSize(q* pq);
//判断队列是否为空
bool QEmpty(q* pq);
//打印队列
void QPrint(q* pq);
//销毁队列
void QDestroy(q* pq);

2.3 队列的声明

Queue.h

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

typedef struct Queue
{
	//记录队头
	qn* phead;
	//记录队尾
	qn* ptail;
	//记录队列有效数据个数
	int size;
}q;

这里我们跟链式栈的声明方式一样,使用了两个结构体,一个结构体用来声明节点的结构,一个结构体声明队列的结构,这里在队列结构中,我们增加指向队头和队尾的指针和计数的size,这样可以方便我们迅速的找到队头数据和队尾数据还有队内有效数据个数。

2.4 队列的初始化

Queue.c

void QInit(q* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.5 队列的入队

Queue.c

void QPush(q* pq, QDataType x)
{
	assert(pq);
	qn* newnode = (qn*)malloc(sizeof(qn));
	if (newnode == NULL)
	{
		perror("malloc");
		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.6 队列的出队

void QPop(q* pq)
{
	assert(pq);
	assert(pq->size > 0);
	//只有一个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点
	else
	{
		qn* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

2.7 队列获取队头元素

Queue.c

QDataType QFront(q* pq)
{
	assert(pq);
	assert(pq->size > 0);

	return pq->phead->data;
}

2.8 队列获取队尾元素

Queue.c

QDataType QBack(q* pq)
{
	assert(pq);
	assert(pq->size > 0);

	return pq->ptail->data;
}

2.9 队列获取有效数据个数

Queue.c

int QSize(q* pq)
{
	assert(pq);

	return pq->size;
}

2.10 队列判断是否为空

Queue.c

bool QEmpty(q* pq)
{
	assert(pq);

	return pq->size == 0;
}

2.11 打印队列

Queue.c

void QPrint(q* pq)
{
	assert(pq);
	while (!QEmpty(pq))
	{
		printf("%d ", QFront(pq));
		QPop(pq);
	}
}

2.12 销毁队列

Queue.c

void QDestroy(q* pq)
{
	assert(pq);
	qn* pcur = pq->phead;
	while (pcur)
	{
		qn* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;

}

3. 队列完整代码

3.1 Queue.h

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

typedef int QDataType;

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

typedef struct Queue
{
	//记录队头
	qn* phead;
	//记录队尾
	qn* ptail;
	//记录队列有效数据个数
	int size;
}q;

//初始化队列
void QInit(q* pq);
//入队
void QPush(q* pq, QDataType x);
//出队
void QPop(q* pq);
//获取队头元素
QDataType QFront(q* pq);
//获取队尾元素
QDataType QBack(q* pq);
//获取队列内有效数据个数
int QSize(q* pq);
//判断队列是否为空
bool QEmpty(q* pq);
//打印队列
void QPrint(q* pq);
//销毁队列
void QDestroy(q* pq);

3.2 Queue.c

#include"Queue.h"

void QInit(q* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QPush(q* pq, QDataType x)
{
	assert(pq);
	qn* newnode = (qn*)malloc(sizeof(qn));
	if (newnode == NULL)
	{
		perror("malloc");
		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 QPop(q* pq)
{
	assert(pq);
	assert(pq->size > 0);
	//只有一个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点
	else
	{
		qn* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

QDataType QFront(q* pq)
{
	assert(pq);
	assert(pq->size > 0);

	return pq->phead->data;
}

QDataType QBack(q* pq)
{
	assert(pq);
	assert(pq->size > 0);

	return pq->ptail->data;
}

int QSize(q* pq)
{
	assert(pq);

	return pq->size;
}

bool QEmpty(q* pq)
{
	assert(pq);

	return pq->size == 0;
}

void QPrint(q* pq)
{
	assert(pq);
	while (!QEmpty(pq))
	{
		printf("%d ", QFront(pq));
		QPop(pq);
	}
}

void QDestroy(q* pq)
{
	assert(pq);
	qn* pcur = pq->phead;
	while (pcur)
	{
		qn* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;

}

4. 循环队列

4.1 循环队列的概念

循环队列:循环队列是一种线性数据结构,其操作表示基于FIFO(先进先出)原则,并且队尾被连接在队头之后以形成一个循环,前提是它的空间大小是固定的。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

简单来说就是:有限的空间,保证先进先出,重复使用。

4.2 循环队列的实现

CircularQueue.h


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

#define k 4

typedef int CQDataType;

typedef struct CircularQueue
{
	CQDataType* arr;
	int front;//指向队头
	int rear;//指向队尾的下一个位置
}cq;

//初始化
void CqInit(cq* pcq);
//判空
bool CqEmpty(cq* pcq);
//判满
bool CqFull(cq* pcq);
//入队
void CqPush(cq* pcq, CQDataType x);
//出队
void CqPop(cq* pcq);
//获取队头数据
CQDataType CqFront(cq* pcq);
//获取队尾数据
CQDataType CqBack(cq* pcq);
//获取队列有效数据个数
int CqSize(cq* pcq);
//销毁队列
void CqDestroy(cq* pcq);

 在这里我们实现循环队列是基于顺序表的情况下实现。

我们首先思考一下,我们怎么判断循环队列是空还是满。

4.3 循环队列的声明

#define k 4

typedef int CQDataType;

typedef struct CircularQueue
{
	CQDataType* arr;
	int front;//指向队头
	int rear;//指向队尾的下一个位置
}cq;

这里我们需要是一个静态的队列,所以我们用#define来声明一个值。这里arr是指向动态开辟内存的一块空间,front指向循环队列的队头,rear指向循环队列队尾的下一个位置。

4.4 循环队列的初始化

void CqInit(cq* pcq)
{
	assert(pcq);
	//多开辟一个空间,避免出现循环队列假溢出的问题
	CQDataType* tmp = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1));
	if (tmp == NULL)
	{
		perror("malloc");
		exit(1);
	}
	pcq->arr = tmp;
	pcq->front = pcq->rear = 0;
}

4.5 循环队列判空

bool CqEmpty(cq* pcq)
{
	assert(pcq);
	//头和尾相等表示空
	return pcq->front == pcq->rear;
}

 4.6 循环队列判满

bool CqFull(cq* pcq)
{
	assert(pcq);
	//尾+1再模k+1解决了回绕问题
	return (pcq->rear + 1) % (k + 1) == pcq->front;
}

4.7 循环队列入队

void CqPush(cq* pcq, CQDataType x)
{
	assert(pcq);
	//判断循环队列是否满了
	assert(!CqFull(pcq));
	pcq->arr[pcq->rear++] = x;
	//解决了循环队列回绕的问题
	pcq->rear %= (k + 1);
}

4.8 循环队列出队

void CqPop(cq* pcq)
{
	assert(pcq);
	//判断循环队列是否为空
	assert(!CqEmpty(pcq));

	pcq->front++;

	pcq->front %= (k + 1);
}

4.9 循环队列获取队头数据

CQDataType CqFront(cq* pcq)
{
	assert(pcq);
	assert(!CqEmpty(pcq));

	return pcq->arr[pcq->front];
}

4.10 循环队列获取队尾数据

这里我们再获取循环队列队尾数据的时候,不是尾-1,当尾在0这个位置的时候,-1就是-1了,下标是不能访问-1的,所以我们这里有两种写法,可以写成pcq->rear == 0 ? 4 : pcq->rear-1,利用三目操作符进行判断。或者先让他-1再模k+1,最后整体在模k+1。

CQDataType CqBack(cq* pcq)
{
	assert(pcq);
	assert(!CqEmpty(pcq));

	return pcq->arr[(pcq->rear - 1+ k+1) % (k + 1)];
}

4.11 循环队列获取有效数据个数

这里计算循环队列中有效数据个数也不能直接返回rear,rear也不是代表size,这里当rear在front右边时,需要rear-front,当rear在front在边时,需要((rear-front)+(k+1))%(k+1))。其实rear在front右边时,也可与写成在左边的写法。当值小于k+1的时候,模k+1并没有影响。

int CqSize(cq* pcq)
{
	assert(pcq);
	if (CqEmpty(pcq))
	{
		return 0;
	}
	return ((pcq->rear - pcq->front) + (k + 1)) % (k + 1);
}

4.12 循环队列销毁

void CqDestroy(cq* pcq)
{
	assert(pcq);
	free(pcq->arr);
	pcq->arr = NULL;
	pcq->front = pcq->rear = 0;
}

5. 循环队列完整代码

5.1 CircularQueue.h


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

#define k 4

typedef int CQDataType;

typedef struct CircularQueue
{
	CQDataType* arr;
	int front;//指向队头
	int rear;//指向队尾的下一个位置
}cq;

//初始化
void CqInit(cq* pcq);
//入队
void CqPush(cq* pcq, CQDataType x);
//出队
void CqPop(cq* pcq);
//判空
bool CqEmpty(cq* pcq);
//判满
bool CqFull(cq* pcq);
//获取队头数据
CQDataType CqFront(cq* pcq);
//获取队尾数据
CQDataType CqBack(cq* pcq);
//获取队列有效数据个数
int CqSize(cq* pcq);
//销毁队列
void CqDestroy(cq* pcq);

5.2 CircularQueue.c

#include"CircularQueue.h"

void CqInit(cq* pcq)
{
	assert(pcq);
	//多开辟一个空间,避免出现循环队列假溢出的问题
	CQDataType* tmp = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1));
	if (tmp == NULL)
	{
		perror("malloc");
		exit(1);
	}
	pcq->arr = tmp;
	pcq->front = pcq->rear = 0;
}

void CqPush(cq* pcq, CQDataType x)
{
	assert(pcq);
	//判断循环队列是否满了
	assert(!CqFull(pcq));
	pcq->arr[pcq->rear++] = x;
	//解决了循环队列回绕的问题
	pcq->rear %= (k + 1);
}

bool CqEmpty(cq* pcq)
{
	assert(pcq);
	//头和尾相等表示空
	return pcq->front == pcq->rear;
}

bool CqFull(cq* pcq)
{
	assert(pcq);
	//尾+1再模k+1解决了回绕问题
	return (pcq->rear + 1) % (k + 1) == pcq->front;
}


void CqPop(cq* pcq)
{
	assert(pcq);
	//判断循环队列是否为空
	assert(!CqEmpty(pcq));

	pcq->front++;

	pcq->front %= (k + 1);
}


CQDataType CqFront(cq* pcq)
{
	assert(pcq);
	assert(!CqEmpty(pcq));

	return pcq->arr[pcq->front];
}

CQDataType CqBack(cq* pcq)
{
	assert(pcq);
	assert(!CqEmpty(pcq));

	return pcq->arr[(pcq->rear - 1+ k+1) % (k + 1)];
}

int CqSize(cq* pcq)
{
	assert(pcq);
	if (CqEmpty(pcq))
	{
		return 0;
	}
	return ((pcq->rear - pcq->front) + (k + 1)) % (k + 1);
}

void CqDestroy(cq* pcq)
{
	assert(pcq);
	free(pcq->arr);
	pcq->arr = NULL;
	pcq->front = pcq->rear = 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/746332.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Prometheus中添加基本身份验证功能

在Prometheus中添加基本身份验证功能&#xff0c;可以按照以下步骤进行&#xff1a; 一、生成哈希密码 首先&#xff0c;需要安装bcrypt工具&#xff0c;用于生成哈希密码。这可以通过Python的bcrypt库来完成。如果未安装&#xff0c;可以使用pip进行安装。 创建一个Python脚…

mysql窗口函数排名查询 与 连续出现的数字查询

排名查询 学会这一个查询&#xff0c;我们应该对该类型的查询 方法就能有一个了解&#xff0c;不然 如果下次遇到该类型的查询&#xff0c;我们依然分析不出 给你一张表&#xff0c;里面有id 和score字段&#xff0c;根据score的分数大小 排序 &#xff0c;假如有相同的分数&…

狗都能看懂的DBSCAN算法详解

文章目录 DBSCAN简介DBSCAN算法流程运行机制举个实例 DBSCAN算法特点DBSCAN参数选取技巧 ϵ \epsilon ϵ的选取&#xff1a;找突变点MinPts的选取 DBSCAN简介 DBSCAN&#xff08;Density-Based Spatial Clustering of Applications with Noise&#xff0c;具有噪声的基于密度的…

构筑卓越:建筑企业如何通过GB/T 50430:2017认证铸就质量管理基石

在建筑业这片充满挑战和机遇的战场上&#xff0c;企业资质犹如一面旗帜&#xff0c;标志着企业的实力和信誉。GB/T 50430:2017《工程建设施工企业质量管理规范》的实施&#xff0c;成为了建筑企业提高管理水平、赢得市场竞争的重要武器。 GB/T 50430:2017的战略意义 GB/T 5043…

Pixea Plus for Mac:图像编辑的极致体验

Pixea Plus for Mac 是一款专为 Mac 用户设计的强大图像编辑软件。凭借其卓越的性能和丰富的功能&#xff0c;它为用户带来了前所未有的图像编辑体验。无论是专业的设计师&#xff0c;还是业余的摄影爱好者&#xff0c;Pixea Plus 都能满足您对于图像编辑的各种需求。 Pixea P…

Promise入门详解

文章目录 Promise 的介绍和优点&#xff08;为什么需要 Promise&#xff1f;&#xff09;Promise 的基本使用Promise 的状态和回调函数Promise 对象的 3 种状态 Promise 的回调函数Promise的状态图&#xff1a; new Promise() 是同步代码Promise 封装定时器Promise 封装 Ajax 请…

2024/06/24(11.1115)指针进阶

1.字符指针 2.数组指针 3.指针数组 4.数组传参和指针传参 5.函数指针 6.函数指针数组 7.指向函数指针数组的指针 8.回调函数 9.指针和数组一些题目的解析 字符指针 char* 我们用这种方法修改了*pch的内容从"A"变成了"a" 存储内容是什么一般指针就…

浏览器扩展V3开发系列之 chrome.storage 的用法和案例

【作者主页】&#xff1a;小鱼神1024 【擅长领域】&#xff1a;JS逆向、小程序逆向、AST还原、验证码突防、Python开发、浏览器插件开发、React前端开发、NestJS后端开发等等 chrome.storage 是用于存储、获取用户数据的 API。当我们需要持久化存储数据时&#xff0c;比如&…

无忧易售升级:一键设置图片分辨率,赋能十大跨境电商平台

在电商领域&#xff0c;产品图片的品质直接影响着顾客的购买决策与品牌形象的塑造。无忧易售ERP特推出图片分辨率修改功能&#xff0c;为电商卖家们提供更专业的图像优化工具&#xff0c;让每一像素都成为吸引客户的秘密武器&#xff01; 一、Allegro、OZON、Coupang、Cdiscou…

低成本STC32G8K64驱动控制BLDC开源入门学习方案

低成本STC32G8K64驱动控制BLDC开源入门学习方案 ✨采用STC32G8K64单片机&#xff0c;参考梁工的STC32G12K128-LQFP48驱动方案制作&#xff0c;梁工BLDC相关的资料&#xff1a;https://www.stcaimcu.com/forum.php?modviewthread&tid7472&extrapage%3D1&#xff0c;在此…

如何编写时区源文件

0、背景 ① 修改TZ环境变量改变时区不能立即生效。要求设置时区后立即生效&#xff0c;只能用修改/etc/localtime方式。 ② 原文作者 Bill Seymour&#xff0c;想要查看原文&#xff0c;点击官网地址https://www.iana.org/time-zones下载 zic 源码&#xff0c;源码目录中的 tz…

[leetcode] smallest-k-lcci. 最小的k个数

. - 力扣&#xff08;LeetCode&#xff09; class Solution { public:vector<int> smallestK(vector<int>& nums, int k) {int L 0, R nums.size() - 1;while (L < R){int left L, right R;int key nums[left];while (left < right){while (left &l…

XX能源云数据平台建设项目_投标书_技术部分(194页word)

标书介绍&#xff1a; 该标书通过物联网技术&#xff0c;实时采集能源行业各类数据&#xff0c;并进行标准化整合。采用分布式存储技术&#xff0c;确保数据的安全性和可扩展性。运用大数据和人工智能技术&#xff0c;对数据进行深度分析和挖掘&#xff0c;提供有价值的业务洞…

鉴权开发框架Django REST framework的应用场景

目录 一、鉴权开发框架介绍二、Django REST framework是什么三、如何实现认证、权限与限流功能四、Django REST framework的应用场景 一、鉴权开发框架介绍 鉴权开发框架是一种用于实现身份验证和授权的软件开发工具。它可以帮助开发者快速构建安全、可靠的身份验证和授权系统…

AI大模型训练过程

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 大模型训练概述 AI大模型训练是指在海量数据中&#xff0c;对拥有数百万至数千万参数及深层次神经网络结构的模型进行训练的过程。这类大模型因其庞大的参数规模和复杂的网…

利用LabVIEW和数字孪生技术实现PCB电路板测试

利用LabVIEW和数字孪生技术对PCB电路板进行测试&#xff0c;可以通过动画展示实现测试过程的生动、形象和直观。本文详细说明了如何结合LabVIEW与数字孪生技术进行PCB电路板的测试&#xff0c;包括系统架构、实现方法以及具体展示效果&#xff0c;适合对外展示。 在现代电子制造…

Redis安装与使用

目录 1、介绍 1、redis的特点: 2、缓存 2、安装Redis 1、安装单机版redis 2、redis-cli命令参数 3、清空数据库的两种方式和作用域&#xff1a; 4、redis的增删查改命令 5、redis的查看所有分类命令 6、redis过期时间与控制键的行为 7、redis的相关工具 1、介绍 r…

如何成为专业的 .NET 开发人员

如今&#xff0c;网上有大量信息&#xff0c;找到正确的信息并非易事。当你开始编程之旅并希望获得全面的指南时&#xff0c;最好寻找一个可以指导你完成整个过程的指南。 本文将帮助您制定一份路线图&#xff0c;告诉您什么是重要的以及什么是需要学习的. 一.一切从软件基础…

CSS|03 尺寸样式属性文本与字体属性

尺寸样式属性 height:元素高度height的值&#xff1a;auto 自动length 使用px定义高度% 基于包含它的块级对象的百分比高度 width&#xff1a;元素的宽度width的值与height一样span标签可以设置宽度、高度吗&#xff1f; 答&#xff1a;不可以&#xff0c;因为span标签是一个行…

机器人控制系列教程之动力学建模(1)

简介 机器人动力学是对机器人机构的力和运动之间关系与平衡进行研究的学科。机器人动力学是以机器人运动为基础&#xff0c;研究在运动过程中连杆与连杆之间、连杆与工件之间力或力矩等关系。 分类&#xff1a; 根据研究方向的不同&#xff0c;机器人的动力学分析也分为正、逆…