【数据结构】（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;                   // 实际存储数据个数,初始化为0queue->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 queueint length;	// maximum number of the queueint n;		// actual number of the queueint *front;	// point to the first elementint *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 spaceint *tmp = queue->front;			// copy datas to new memroy spaceif(queue->front < queue->rear){ // copy elements from front pointer to rear pointerfor(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 queuet[i] = *tmp;tmp++;}for(; i < queue->n; i++){ // copy elements from start of the queue to the rear pointert[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 0if(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 0if(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 pointerfor(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 queueprintf("%d  ", *tmp);tmp++;}for(; i < queue->n; i++){ // copy elements from start of the queue to the rear pointerprintf("%d  ", queue->p[i - m]);}}printf("\n");
}

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

执行可执行文件： ./queue

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

下载安装MySQL

下载安装MySQL

1.软件的下载 打开官网下载mysql-installer-community-8.0.37.0.msi 2.软件的安装 mysql下载完成后&#xff0c;找到下载文件&#xff0c;双击安装 3.配置环境变量 4.自带客户端登录与退出
阅读更多...
CocoaPodsCmake

CocoaPodsCmake

https://juejin.cn/post/7257048145233838141?searchId20240531171431E5868B41DC7B7016CCBA https://guides.cocoapods.org CocoaPods CocoaPods的作用 帮助程序员通过命令管理第三方库及更新&#xff0c;以达到扩展项目的目的。 CocoaPods的使用 在已有的工程目录下新增…
阅读更多...
【test】小爱同学通过esp32控制电脑开关

【test】小爱同学通过esp32控制电脑开关

文章目录 一、环境准备二、开关机原理数据传输框架 三、环境搭建1.巴法云平台设置2.米家设置3.windows网络唤醒设置4.搭建esp32开发环境并部署&#xff08;1&#xff09;新建项目&#xff08;2&#xff09;导入esp32库&#xff08;3&#xff09; 添加库&#xff08;4&#xff0…
阅读更多...
Oracle Database 23ai新特性：DB_DEVELOPER_ROLE角色

Oracle Database 23ai新特性：DB_DEVELOPER_ROLE角色

角色介绍 从 Oracle Database 23ai 开始&#xff0c;新角色“DB_DEVELOPER_ROLE”允许管理员快速分配开发人员为 Oracle 数据库设计、构建和部署应用程序所需的所有必要权限。&#xff08;包括构建数据模型所需的系统权限以及监视和调试应用程序所需的对象权限&#xff09;。通…
阅读更多...
MySQL之备份与恢复(四)

MySQL之备份与恢复(四)

备份与恢复 存储引擎和一致性 3.复制 从备库中备份最大的好处是可以不干扰主库&#xff0c;避免在主库上增加额外的负载。这是一个建立备库的好理由&#xff0c;即使不需要用它做负载均衡或高可用。如果钱是个问题&#xff0c;也可以把备份用的备库用于其他用户&#xff0c;…
阅读更多...
【C语言】刷题笔记 Day2

【C语言】刷题笔记 Day2

【笔记】 【1】局部变量不初始化&#xff0c;默认放的随机值。 1 int n0; 2 scanf("%d",&n); //13.141 【2】这里虽然输入的是一个浮点数&#xff0c;但是只取整数部分。 【3】3.156e7 表示的是3.156*10的7次方。 【4】多组输入&#xff0c;保存和不保存…
阅读更多...
半实物仿真测试系统

半实物仿真测试系统

设备组成 test系统主要由硬件部分与软件部分组成。硬件部分由PCI机箱、PCI控制器以及各种PCI接口板卡组成。软件部分由测试设计软件模块、测试执行服务软件模块、测试执行客户端软件模块、设备资源管理软件模块等主要软件模块以及曲线数据生成、CRC插件生成与诊断、测试数据记录…
阅读更多...
【UE5.3】笔记7 控制Pawn移动

【UE5.3】笔记7 控制Pawn移动

使用A、D键控制角色左右移动 打开我们的BP_Player蓝图类&#xff0c;选择事件图表&#xff0c;添加我们的控制事件 右键&#xff0c;搜索A keyboard&#xff0c;选择A,如下图&#xff0c;D也是 添加扭矩力 首先我们要把我们的player上的模拟物理选项打开&#xff0c;这样我们…
阅读更多...
Arduino - TM1637 4 位 7 段显示器

Arduino - TM1637 4 位 7 段显示器

Arduino - TM1637 4 位 7 段显示器 Arduino-TM1637 4 位 7 段显示器 A standard 4-digit 7-segment display is needed for clock, timer and counter projects, but it usually requires 12 connections. The TM1637 module makes it easier by only requiring 4 connectio…
阅读更多...
开始尝试从0写一个项目--后端（一）

开始尝试从0写一个项目--后端（一）

创建文件的目录结构 利用这个界面创建 序号 名称 说明 1 SEMS maven父工程&#xff0c;统一管理依赖版本&#xff0c;聚合其他子模块 2 sems-common 子模块&#xff0c;存放公共类&#xff0c;例如&#xff1a;工具类、常量类、异常类等 3 sems-pojo 子模块&#x…
阅读更多...
【Qt】之【Bug】大量出现“未定义的标识符”问题

【Qt】之【Bug】大量出现“未定义的标识符”问题

背景 构建时出现大量错误 原因 中文注释问题 解决 方法1. 报错代码附近的中文注释全部删掉。。。 方法2. 报错的文件添加 // Chinese word comment solution #pragma execution_character_set("utf-8")
阅读更多...
【C语言】—— 文件操作（下）

【C语言】—— 文件操作（下）

【C语言】—— 文件操作&#xff08;下&#xff09; 前言&#xff1a;五、文件的顺序读写5.1、 顺序读写函数介绍5.2、 f p u t c fputc fputc 函数5.3、 f g e t c fgetc fgetc 函数5.4、 f p u t s fputs fputs 函数5.5、 f g e t s fgets fgets 函数5.6、 f p r i n t f…
阅读更多...
神经网络在机器学习中的应用：手写数字识别

神经网络在机器学习中的应用：手写数字识别

机器学习是人工智能的一个分支&#xff0c;它使计算机能够从数据中学习并做出决策或预测。神经网络作为机器学习的核心算法之一&#xff0c;因其强大的非线性拟合能力而广泛应用于各种领域&#xff0c;包括图像识别、自然语言处理和游戏等。本文将介绍如何使用神经网络对MNIST数…
阅读更多...
2024亚太杯中文赛数学建模选题建议及各题思路来啦！

2024亚太杯中文赛数学建模选题建议及各题思路来啦！

大家好呀&#xff0c;2024年第十四届APMCM亚太地区大学生数学建模竞赛&#xff08;中文赛项&#xff09;开始了&#xff0c;来说一下初步的选题建议吧&#xff1a; 首先定下主基调&#xff0c; 本次亚太杯推荐大家选择B题目。C题目难度较高&#xff0c;只建议用过kaiwu的队伍…
阅读更多...
怎样将word默认Microsoft Office，而不是WPS

怎样将word默认Microsoft Office，而不是WPS

设置——>应用——>默认应用——>选择"word"——>将doc和docx都选择Microsoft Word即可
阅读更多...
PE文件学习

PE文件学习

一、介绍 PE文件&#xff0c;即Portable Executable文件&#xff0c;是一种标准的文件格式&#xff0c;主要用于微软的Windows操作系统上。这种格式被用来创建可执行程序&#xff08;如.exe文件&#xff09;、动态链接库&#xff08;.DLL文件&#xff09;、设备驱动&#xff0…
阅读更多...
苹果电脑虚拟机运行Windows Mac环境安装Win PD19虚拟机 parallels desktop19虚拟机安装教程免费密钥激活

苹果电脑虚拟机运行Windows Mac环境安装Win PD19虚拟机 parallels desktop19虚拟机安装教程免费密钥激活

在如今多元的数字时代&#xff0c;我们经常需要在不同的操作系统环境下进行工作和学习。而对于 Mac 用户来说&#xff0c;有时候需要在自己的电脑上安装 Windows 操作系统&#xff0c;以体验更多软件及功能&#xff0c;而在 Mac 安装 Windows 虚拟机是常用的一种操作。下面就来…
阅读更多...
Codeforces Round 955 (Div. 2, with prizes from NEAR!)（A~C题解）

Codeforces Round 955 (Div. 2, with prizes from NEAR!)（A~C题解）

这场比赛怎么说呢&#xff0c;一开始打的还算好&#xff0c;能进前1000&#xff0c;但是后面就被卡住了&#xff0c;这个确实没办法水平还是不够&#xff0c;学过的还是没想起来&#xff0c;后面继续练 A. Soccer 题解&#xff1a;水题一个&#xff0c;想要在过程中出现平局的…
阅读更多...
使用 iconfont.ttf文件保存多个图标文件，并且像文字一样使用代码绘制出来

使用 iconfont.ttf文件保存多个图标文件，并且像文字一样使用代码绘制出来

先看演示效果 这里的多个图标其实是存储在 iconfont.ttf文件中 这个文件里面的图标对应的编码 显示代码 void CMFCApplication3Dlg::OnBnClickedOk() {// 加载字体文件CString fontPath = _T("C:\\Users\\35497\\Desktop\\test\\MFCApplication3\\font\\iconfont.ttf&qu…
阅读更多...
pytorch中的contiguous()

pytorch中的contiguous()

官方文档&#xff1a;https://pytorch.org/docs/stable/generated/torch.Tensor.contiguous.html 其描述contiguous为&#xff1a; Returns a contiguous in memory tensor containing the same data as self tensor. If self tensor is already in the specified memory forma…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023