【数据结构】（C语言）：队列

队列：

  • 线性的集合。
  • 先进先出（FIFO，first in first out）。
  • 两个指针：头指针（指向第一个进入且第一个出去的元素），尾指针（指向最后一个进入且最后一个出去的元素）。
  • 两个操作：入队（往队尾添加元素），出队（从队头删除元素）。
  • 队列有优先队列，双端队列，循环队列等。
  • 可以使用链表实现，也可以使用数组实现。本文使用数组实现循环队列。

添加元素：

往队尾添加。若尾指针已指向队尾，则循环重新指向队头。

删除元素：

从队头删除。若头指针已指向队尾，则循环重新指向队头。

扩容、缩容：

若内存区域已全部使用完，则增加内存区域。若内存区域使用小，则减少内存区域。

方法：新开辟内存区域，将原数据复制到新内存区域。

若头指针在尾指针的前面，则从头指针到尾指针的数据依次复制到新内存区域。

若尾指针在头指针的前面，则从头指针到内存区域最后的这m个数据，依次复制到新区域0到m-1，再从0到尾指针的数据，依次复制到n到n-1（n为实际存储数据个数）。

 ​​​​​​

C语言实现：（使用数组实现循环队列）

创建结构体数据类型：

  • 指针p：记录数组的内存地址（即数组第一个元素的地址）。
  • 整型length：记录数组最大物理容量（即创建数组时指定的内存大小）。
  • 整型n：记录数组实际逻辑大小（即数组实际已经存储的数据个数）。
  • 指针front：头指针，始终指向数组数据中第一个进入且将第一个出去的元素。
  • 指针rear：尾指针，始终指向数组数据中最后一个进入且将最后一个出去的元素。
typedef struct Queue
{
	int *p;		    // 数组内存地址
	int length;	    // 物理最大容量
	int n;		    // 实际存储数据
	int *front;	    // 始终指向第一个进入且第一个出去的元素
	int *rear;	    // 始终指向最后一个进入且最后一个出去的元素
} Queue;	        // 别名

创建队列变量：

Queue queue;

初始化队列：

void init(Queue *queue, int len)
{
	queue->p = (int *)malloc(len * sizeof(int));     // 分配数组内存空间
	if(queue->p == NULL)
	{
		perror("Memory allocation failled");
		exit(-1);
	}
	queue->length = len;            // 指定物理大小
	queue->n = 0;                   // 实际存储数据个数,初始化为0
	queue->front = queue->p;        // 头指针,初始化指向数组第一个元素地址
	queue->rear = queue->p;         // 尾指针,初始化指向数组第一个元素地址
}

扩容、缩容：

void resize(Queue *queue, int len)
{
    // 开辟新内存空间，将原数据复制到新地址
	int *t = (int *)malloc(len * sizeof(int));
	int *tmp = queue->front;

    // 若头指针在前，依次复制从头指针到尾指针的数据
	if(queue->front < queue->rear)
	{
		for(int k = 0; k < queue->n; k++)
		{
			t[k] = *tmp;
			tmp++;
		} 
	}
    // 若尾指针在前，复制头指针到数组最后的数据，再复制数组开头到尾指针的数据
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{
			t[i] = *tmp;
			tmp++;
		}
		for(; i < queue->n; i++)
		{
			t[i] = queue->p[i - m];
		}
	}
	queue->p = t;
	queue->length = len;
	queue->front = queue->p;
	queue->rear = queue->p + queue->n - 1;
}

 添加元素：

往队尾添加。尾指针rear指向下一个元素。若尾指针已指向区域最后，则尾指针循环重新指向区域开头。

void add(Queue *queue, int data)
{
	if(queue->length == queue->n)	// 若数组满，扩容
	{
		int newlength = queue->length * 2;
		resize(queue, newlength);
	}
	
	// 若尾指针指向数组最后，尾指针循环开始指向数组开头
	if(queue->rear == queue->p + queue->n) queue->rear = queue->p;
	else queue->rear++;

	*queue->rear = data;
	queue->n++;
}

删除元素：

从队头删除。头指针front指向下一个元素。若头指针已指向区域最后，则头指针循环重新指向区域开头。

int deltop(Queue *queue)
{
	int value = *queue->rear;
	queue->n--;

	// 若头指针已指向数组尾部，头指针循环开始指向数组开头
	if(queue->front == queue->p + queue->n)	queue->front = queue->p;
	else queue->front++;

	if(queue->n < ceil(queue->length / 2) && queue->length > 4)	// 满足条件，缩容
	{
		int newlength = ceil(queue->length / 2);
		resize(queue, newlength);
	}
	return value;
}

遍历队列元素：

void travel(Queue *queue)
{
	if(queue->n == 0) return ;

	printf("elements: ");
	int *tmp = queue->front;
    
    // 若头指针在前，依次从头指针遍历到尾指针
	if(queue->front < queue->rear)
	{
		for(int k = 0; k < queue->n; k++)
		{
			printf("%d  ", *tmp);
			tmp++;
		} 
	}
    // 若尾指针在前，遍历头指针到数组最后，再遍历数组开头到尾指针
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{
			printf("%d  ", *tmp);
			tmp++;
		}
		for(; i < queue->n; i++)
		{
			printf("%d  ", queue->p[i - m]);
		}
	}
	printf("\n");
}

完整代码：（queue.c）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* structure */
typedef struct Queue
{
	int *p;		// memory address of the queue
	int length;	// maximum number of the queue
	int n;		// actual number of the queue
	int *front;	// point to the first element
	int *rear;	// point to the end element
} Queue;

/* function prototype */
void init(Queue *, int);	// queue initialization
void resize(Queue *, int);	// increase or reduce the size of the queue
void add(Queue *, int);         // add element to the end of the queue
int deltop(Queue *);		// delete element from the start of the queue
void travel(Queue *);		// show element one by one

/* main function */
int main(void)
{
	Queue queue;
	init(&queue, 4);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	
	add(&queue, 8);
	add(&queue, 16);
	add(&queue, 23);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	add(&queue, 65);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	add(&queue, 27);     // 已满，扩容
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);

	deltop(&queue);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	deltop(&queue);      // 使用少于一半，缩容
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	deltop(&queue);
	deltop(&queue);
	deltop(&queue);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	return 0;
}

/* subfunction */
void init(Queue *queue, int len)		// queue initialization
{
	queue->p = (int *)malloc(len * sizeof(int));
	if(queue->p == NULL)
	{
		perror("Memory allocation failled");
		exit(-1);
	}
	queue->length = len;
	queue->n = 0;
	queue->front = queue->p;
	queue->rear = queue->p;
}

void resize(Queue *queue, int len)	// increase or reduce the size of the queue
{
	int *t = (int *)malloc(len * sizeof(int));	// new memory space
	int *tmp = queue->front;			// copy datas to new memroy space
	if(queue->front < queue->rear)
	{ // copy elements from front pointer to rear pointer
		for(int k = 0; k < queue->n; k++)
		{
			t[k] = *tmp;
			tmp++;
		} 
	}
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{ // copy elements from front pointer to the end of the queue
			t[i] = *tmp;
			tmp++;
		}
		for(; i < queue->n; i++)
		{ // copy elements from start of the queue to the rear pointer
			t[i] = queue->p[i - m];
		}
	}
	queue->p = t;
	queue->length = len;
	queue->front = queue->p;
	queue->rear = queue->p + queue->n - 1;
}

void add(Queue *queue, int data)        // add element to the end of the queue
{
	if(queue->length == queue->n)	// increase the size of the queue
	{
		int newlength = queue->length * 2;
		resize(queue, newlength);
	}
	
	// if rear point to the end space, rear point to index 0
	if(queue->rear == queue->p + queue->n) queue->rear = queue->p;
	else queue->rear++;

	*queue->rear = data;
	queue->n++;
}

int deltop(Queue *queue)		// delete element from the start of the queue
{
	int value = *queue->rear;
	queue->n--;

	// if front point to the end space,front point to index 0
	if(queue->front == queue->p + queue->n)	queue->front = queue->p;
	else queue->front++;

	if(queue->n < ceil(queue->length / 2) && queue->length > 4)	// reduce the size of the queue
	{
		int newlength = ceil(queue->length / 2);
		resize(queue, newlength);
	}
	return value;
}


void travel(Queue *queue)		// show element one by one
{
	if(queue->n == 0) return ;

	printf("elements: ");
	int *tmp = queue->front;
	if(queue->front < queue->rear)
	{ // copy elements from front pointer to rear pointer
		for(int k = 0; k < queue->n; k++)
		{
			printf("%d  ", *tmp);
			tmp++;
		} 
	}
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{ // copy elements from front pointer to the end of the queue
			printf("%d  ", *tmp);
			tmp++;
		}
		for(; i < queue->n; i++)
		{ // copy elements from start of the queue to the rear pointer
			printf("%d  ", queue->p[i - m]);
		}
	}
	printf("\n");
}

编译链接： gcc -o queue queue.c

执行可执行文件： ./queue

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

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

相关文章

Redis优化之持久化

Redis优化之持久化

目录 1.Redis高可用 2.Redis持久化 2.1 RDB持久化 2.1.1 触发条件 2.1.2 执行流程 2.1.3 启动时加载 2.2 AOF持久化 2.2.1 开启AOF 2.2.2 执行流程 2.2.3 文件重写触发方式 2.2.4 文件重写的流程 2.2.5 启动时加载 2.3 RDB和AOF的优缺点 3.Redis性能管理 3.1 查看…
阅读更多...
C++ 教程 - 07 类的静态成员

C++ 教程 - 07 类的静态成员

文章目录 静态成员 静态成员 使用static修饰的成员&#xff1b; 静态的成员变量&#xff1b; 仅保留一份副本&#xff0c;不管创建多少个实例对象&#xff0c;都共享这一份数据&#xff1b;类、对象均可以调用&#xff1b;类外重新声明&#xff0c;并通过类初始化&#xff1b;…
阅读更多...
怎么在vite项目中全局导入一个scss文件

怎么在vite项目中全局导入一个scss文件

怎么在vite项目中全局导入一个scss文件 &#x1f389;&#x1f389;&#x1f389;欢迎来到我的博客,我是一名自学了2年半前端的大一学生,熟悉的技术是JavaScript与Vue.目前正在往全栈方向前进, 如果我的博客给您带来了帮助欢迎您关注我,我将会持续不断的更新文章!!!&#x1f64…
阅读更多...
腾讯云CVM,CentOS8系统下部署Java-Web项目步骤详解

腾讯云CVM,CentOS8系统下部署Java-Web项目步骤详解

在CVM中部署项目首先要配置好JDK,Tomcat,Mysql(这里以Tomcat和Mysql为例)。部署JDK和Tomcat的步骤可以参考 CentOS7系统下部署tomcat,浏览器访问localhost:8080/_不积跬步&#xff0c;无以至千里&#xff1b;不积小流&#xff0c;无以成江河。-CSDN博客 我这里从Mysql的安装和设…
阅读更多...
Java | Leetcode Java题解之第201题数字范围按位与

Java | Leetcode Java题解之第201题数字范围按位与

题目&#xff1a; 题解&#xff1a; class Solution {public int rangeBitwiseAnd(int m, int n) {while (m < n) {// 抹去最右边的 1n n & (n - 1);}return n;} }
阅读更多...
C#——命名空间详情

C#——命名空间详情

命名空间 在 C# 中&#xff0c;可以将命名空间看作是一个范围&#xff0c;用来标注命名空间中成员的归属&#xff0c;一个命名空间中类与另一个命名空间中同名的类互不冲突&#xff0c;但在同一个命名空间中类的名称必须是唯一的。 定义命名空间 定义命名空间需要使用 namesp…
阅读更多...
微软推出最新视觉基础模型Florence-2 可在浏览器运行

微软推出最新视觉基础模型Florence-2 可在浏览器运行

据微软官方消息&#xff0c;微软推出视觉基础模型Florence-2&#xff0c;该模型现已能够在支持WebGPU的浏览器中100%本地运行。Florence-2-base-ft是一个拥有2.3亿参数的视觉基础模型&#xff0c;采用基于提示的方法来处理广泛的视觉和视觉语言任务。 该模型支持多种功能&…
阅读更多...
youlai-boot项目的学习(4) 前后端本地部署

youlai-boot项目的学习(4) 前后端本地部署

环境 1、macOS, brew, IntelliJ IDEA, WebStrom 2、后端&#xff1a;https://gitee.com/youlaiorg/youlai-boot.git , master, 9a753a2e94985ed4cbbf214156ca035082e02723 3、前端&#xff1a;https://gitee.com/youlaiorg/vue3-element-admin.git, master, 66b913ef01dc880ad…
阅读更多...
25届最近5年重庆邮电大学自动化考研院校分析

25届最近5年重庆邮电大学自动化考研院校分析

重庆邮电大学 目录 一、学校学院专业简介 二、考试科目指定教材 三、近5年考研分数情况 四、近5年招生录取情况 五、最新一年分数段图表 六、历年真题PDF 七、初试大纲复试大纲 八、学费&奖学金&就业方向 一、学校学院专业简介 二、考试科目指定教材 1、考试…
阅读更多...
提取url中的参数

提取url中的参数

let url https://alibaba.com?a1&b2&c3#hash function queryUrlParams(URL){let url URL.split(?)[1];const urlSearchParams new URLSearchParams(url);console.log(url1, urlSearchParams);console.log(entries,urlSearchParams.entries())const params Object…
阅读更多...
大模型推理知识总结

大模型推理知识总结

一、大模型推理概念 大多数流行的only-decode LLM&#xff08;例如 GPT-3&#xff09;都是针对因果建模目标进行预训练的&#xff0c;本质上是作为下一个词预测器。这些 LLM 将一系列tokens作为输入&#xff0c;并自回归生成后续tokens&#xff0c;直到满足停止条件&#xff0…
阅读更多...
多表查询-子查询

多表查询-子查询

前言 上一篇博客&#xff0c;我简单的讲述了联合查询。今天本篇博客我将详细的阐述子查询的四个方面如 标量子查询&#xff0c;列子查询&#xff0c;行子查询&#xff0c;表子查询。 正文 子查询的认识 子查询的认识 子查询&#xff1a;是SQL语句中&#xff0c;嵌套select …
阅读更多...
SAP揭秘者-在QM标准功能增加取消UD的功能第三季

SAP揭秘者-在QM标准功能增加取消UD的功能第三季

下面让我们来看实际项目中使用的最佳方案&#xff1a; 运用增强QEVA0008&#xff0c;该增强会在下面UD界面(QA12)里增加一个Customer Function(Reset UD)的按钮;我们在这个用户出口中再增加代码去调用上面两支程序&#xff0c;则可以实现该功能。 步骤如下&#xff1a; 步骤一&…
阅读更多...
【YOLOv5/v7改进系列】引入RT-DETR的RepC3

【YOLOv5/v7改进系列】引入RT-DETR的RepC3

一、导言 RT-DETR&#xff08;Real-Time Detection Transformer&#xff09;是一种针对实时目标检测任务的创新方法&#xff0c;它旨在克服YOLO系列和其他基于Transformer的检测器存在的局限性。RT-DETR的主要优点包括&#xff1a; 无NMS&#xff08;非极大值抑制&#xff09;…
阅读更多...
GGUF模型转换入门

GGUF模型转换入门

一、定义 1 定义 2 案例 二、实现 定义 GGUF是一种大模型文件格式&#xff0c;由开发者Georgi Gerganov提出。 这是一种针对大规模机器学习模型设计的二进制格式文件规范。它的主要优势在于能够将原始的大模型预训练结果经过特定优化后转换成这种格式&#xff0c;从而可以更…
阅读更多...
UI Toolkit系统学习

UI Toolkit系统学习

UI Toolkit 此文章用于学习UnityUI系统&#xff0c;手头的项目做完会来完善 官方文档 Unity上方菜单栏点击Window->UI Toolkit->Samples可以看UI Toolkit中的很多样例 使用 UI Toolkit 和 UI Builder 制作物品编辑器 在文件夹中右键->Create->UI Toolkit->Edi…
阅读更多...
花卉寄售系统

花卉寄售系统

摘 要 随着互联网的快速发展和普及&#xff0c;电子商务已经成为人们日常生活中不可或缺的一部分。在电子商务领域&#xff0c;花卉行业也逐渐崭露头角&#xff0c;成为一个具有巨大潜力的市场。传统的花卉销售模式通常是通过实体店面进行销售&#xff0c;这种模式存在着许多问…
阅读更多...
Android开发系列（十二）Jetpack Compose之BottomSheet

Android开发系列（十二）Jetpack Compose之BottomSheet

BottomSheet 是 Android 中一个常用的 UI 组件&#xff0c;它通常用于显示从屏幕底部弹出的用户界面。Jetpack Compose 是 Android 中的一个全新 UI 工具包&#xff0c;它提供了一种声明式的方式来构建用户界面。Jetpack Compose 中也有一个名为 BottomSheet 的组件&#xff0c…
阅读更多...
数据恢复篇：如何从 Mac 硬盘安全恢复丢失的文件

数据恢复篇：如何从 Mac 硬盘安全恢复丢失的文件

Mac RAID 阵列用于大存储。Mac RAID 上的数据丢失可能很复杂。一般来说&#xff0c;从 Mac RAID 硬盘恢复已删除的文件并不困难。但如果​​您想从 Mac RAID 硬盘恢复由于格式化、病毒感染、硬盘故障而丢失的文件&#xff0c;情况就会发生变化。您必须找到一个功能强大的 Mac R…
阅读更多...
【ONLYOFFICE 8.1】的安装与使用——功能全面的 PDF 编辑器、幻灯片版式、优化电子表格的协作

【ONLYOFFICE 8.1】的安装与使用——功能全面的 PDF 编辑器、幻灯片版式、优化电子表格的协作

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 一、引言二、ONLYOFFICE 简介三、安装1. Windows/Mac 安装2. 文档开发者版安装安装前准备使用 Docker 安装使用 Linux 发行版安装配置 ONLYOFFICE 文档开发者版集成和开发 四、使用1. 功能全面的 PDF 编辑器PDF 查看和导航P…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站