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

队列的实现及循环队列

一、队列的概念及结构

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

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

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

二、队列的实现(单链表实现)

Queue.h文件:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
//链式结构:表示队列
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;
//队列的结构
//多个参数可以封装成结构体,方便传参,否则下面传二级指针
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队尾插入
void QueuePush(Queue* pq, QDataType x);
//队头删除
void QueuePop(Queue* pq);
//获取队头数据
QDataType QueueFront(Queue* pq);
//获取队尾数据
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
void QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

Queue.c文件:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->front = NULL;pq->rear = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->front;while (cur){Queue* next = cur->next;free(cur);cur = next;}pq->front = pq->rear = NULL;pq->size = 0;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");return;}newnode->next = NULL;newnode->val = x;if (pq->rear == NULL){pq->front = pq->rear = newnode;}else{pq->rear->next = newnode;pq->rear = newnode;}pq->size++;
}
//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size > 0);if (pq->front == pq->rear){free(pq->front);pq->front = pq->rear = NULL;}else{QNode* next = pq->front->next;free(pq->front);pq->front = next;}pq->size--;
}
//获取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->front);return pq->front->val;
}
//获取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->rear);return pq->rear->val;
}
//获取队列中有效元素个数
void QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->size == 0){return 1;}else{return 0;}
}

Test文件:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");return 0;
}

三、设计循环队列

622. 设计循环队列 - 力扣(LeetCode)

方法:额外多开一个空间

代码:

typedef struct {int* a;int head;int tail;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开一个解决假溢出问题obj->a = (int*)malloc(sizeof(int)*(k+1));obj->head = 0;obj->tail = 0;obj-> k = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k+1) == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->head;obj->head %= (obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->tail + obj->k) % (obj->k+1)]; 
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

相关文章:

队列的实现及循环队列

一、队列的概念及结构 队列只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表。队列具有先进先出FIFO&#xff08;Fist In First Out&#xff09;。 入队列&#xff1a;进行插入操作的一端称为队尾。 出队列&#xff1a;进行删除操作的一端称为…...

docker部署zookeeper和kafka

docker部署zookeeper和kafka zookeeperkafkakafka-eagle zookeeper firewall-cmd --zonepublic --add-port2181/tcp --permanent firewall-cmd --reload docker pull zookeeper:3.4.14 docker run -d --name zk -p 2181:2181 zookeeper:3.4.14mkdir -p /root/zookeeper/data m…...

(13)zabbix的监控-1

前言&#xff1a;在上一次的基础上&#xff0c;完成实验。 1、添加一个空模板&#xff0c;方便 2、添加空模板到主机192.168.121.50 client-one里面模板是空的 4、在主机添加监控项和图形 5、自定义监控项&#xff0c;在客户端定义 [rootclient1 ~]# vim /etc/zabbix/zabbix_…...

Redis相关面试题(二)

一、Bit中不同命令使用的场景 二、什么是缓存击穿&#xff0c;缓存穿透&#xff0c;缓存雪崩&#xff1f; 缓存击穿&#xff1a;是指当某一个key的缓存过期时大并发量的请求同时访问key&#xff0c;瞬间击穿服务器直接访问到数据库&#xff0c;使得数据库处于负载情况 缓存穿透…...

Docker Compose与私有仓库

Docker Compose与私有仓库 docker-compose -v 查看版本信息 Docker Compose的应用 创建APACHE容器 vim docker-compose.yaml yaml文件缩进严格&#xff1b;冒号后有内容需要加空格&#xff0c;冒号后无内容一般不加空格 冒号后的内容中若包含路径‘/’或‘&#xff1a;’时…...

AI学习记录 - gpt如何进行token化,理论知识,以GPT2为举例

AI学习记录已经发了十几篇&#xff0c;大佬们可以看看&#xff0c;如果有帮助动动小手点赞 token入门版&#xff0c;有空会更新具体代码操作 GPT4当中&#xff0c;我们提问问题是按照token进行扣费的&#xff0c;那到底什么是token&#xff1f; 在不同的语言模型当中&#x…...

Java线程池和执行流程

在 Java 中&#xff0c;常见的四种线程池包括&#xff1a; 1. newFixedThreadPool&#xff08;固定大小线程池&#xff09; 应用场景&#xff1a;适用于需要限制线程数量&#xff0c;并且任务执行时间比较均匀的场景&#xff0c;例如服务器端的连接处理。优点&#xff1a;线程数…...

进程信号的产生与处理

目录 前言 一.信号的概念 二.信号的产生 1.键盘产生 2.系统调用 3.软件条件 4.异常 三.信号的保存 四.信号的处理 信号处理的方式 设定屏蔽信号 自定义处理信号 信号处理的时机 前言 进程信号&#xff08;Process Signals&#xff09;是操作系统与运行进程之间进行通…...

统一响应结果封装,Result类的实现【后端 06】

统一响应结果封装&#xff0c;Result类的实现 在开发Web应用或API接口时&#xff0c;如何优雅地处理并返回响应结果是每个开发者都需要考虑的问题。统一响应结果封装&#xff08;Unified Response Encapsulation&#xff09;作为一种广泛采用的实践&#xff0c;不仅提高了API的…...

明日周刊-第20期

本周异形新电影上映&#xff0c;开始期待起来了&#xff0c;毕竟这是一个经久不衰的ip。还有就是马上来临的黑神话悟空&#xff0c;属于我们自己的3A大作&#xff0c;接下去的每一天都是新的期待。 文章目录 科技短讯资源分享随便说说一点心情 科技短讯 科技创新与突破 人工智…...

深入剖析 Spring 常用注解:功能与差异的全景洞察

《深入剖析 Spring 常用注解&#xff1a;功能与差异的全景洞察》 在当今的 Java 开发领域&#xff0c;Spring 框架无疑是最广泛使用的框架之一。而在 Spring 中&#xff0c;注解的运用极大地简化了开发流程&#xff0c;提高了代码的可读性和可维护性。本文将深入探讨 Spring 中…...

【隐私计算篇】隐私计算使用不当也会泄露原始数据

1. 背景信息 有个有趣的问题&#xff0c;刚好最近有讨论到&#xff0c;在这里也抛一下&#xff0c;就是隐私计算中我们经常谈到主流的一些技术&#xff0c;比如联邦学习、多方安全计算、安全求交、匿踪查询、可信执行环境等&#xff0c;然后笼统地会称这些技术实现了对隐私…...

C++第一讲:开篇

C第一讲&#xff1a;开篇 1.C历史背景1.1C创世主--本贾尼1.2C版本更新1.3C的重要性1.4C书籍推荐 2.C的第一个程序3.命名空间3.1namespace是什么3.2namespace的使用3.3namespace使用注意事项3.4命名空间的使用 4.C输入和输出5.缺省参数6.函数重载7.引用7.1什么是引用7.2引用的定…...

OceanBase V4.2特性解析:MySQL模式下GIS空间表达式的场景及能力解析

1. 背景 1.1. OceanBase Mysql gis空间表达式的应用场景及能力 在OceanBase 4.1版本中&#xff0c;mysql模式下支持了gis数据类型以及部分空间对象相关的表达式&#xff0c;随着客户使用空间数据的需求日益增长&#xff0c;需要快速地补齐空间数据存储和计算分析的能力&#…...

HSL模型和HSB模型,和懒人配色的Color Hunt

色彩不仅仅是视觉上的享受&#xff0c;它在数据可视化中也扮演着关键角色。通过合理运用色彩模型&#xff0c;我们可以使数据更具可读性和解释性。在这篇文章将探讨HSL&#xff08;Hue, Saturation, Lightness&#xff09;和HSB&#xff08;Hue, Saturation, Brightness&#x…...

什么是云原生?(二)

1. 云原生的定义 云原生指构建和运行应用以充分利用通过云技术交付模式交付的分布式计算。云原生应用旨在充分利用云技术平台特有的可扩展性、弹性和灵活性优势。 根据云原生计算基金会 (CNCF) 的定义&#xff0c;云原生技术可帮助企业在公有云、私有云和混合云环境中构建和…...

pytorch 47 模型剪枝实战|基于torch-pruning库代码对yolov10n模型进行剪枝

torch-pruning官方提供了基于yolov8的剪枝代码,基于此代码改进博主实现了对yolov10n模型的剪枝。虽然实现了对yolov10n模型的剪枝,剪枝目标为移除60%的通道,然而实验是失败的,针对coco数据集进行操作,剪枝前的模型map时37,剪枝后只能恢复到22,比预计下降了15个点,剪枝后…...

LeetCode_sql_day15(262.行程与用户)

描述&#xff1a;262. 行程和用户 - 力扣&#xff08;LeetCode&#xff09; 取消率 的计算方式如下&#xff1a;(被司机或乘客取消的非禁止用户生成的订单数量) / (非禁止用户生成的订单总数)。 编写解决方案找出 "2013-10-01" 至 "2013-10-03" 期间非禁止…...

【MySQL】详解数据库约束、聚合查询和联合查询

数据库约束 约束类型 数据库的约束类型主要包括以下几种&#xff1a; 主键约束&#xff08;Primary Key Constraint&#xff09;&#xff1a;确保表中的每一行都有唯一的标识&#xff0c;且不能为NULL。 外键约束&#xff08;Foreign Key Constraint&#xff09;&#xff1a…...

bug积累

1.只写 int p[len1 len2]; 时&#xff0c;实际上是在使用 C99 标准中引入的变长数组&#xff08;VLA, Variable Length Array&#xff09;的特性。变长数组允许在栈上分配其大小在运行时确定的数组。这意味着 len1 和 len2 的值可以在程序运行时确定&#xff0c;但仍然可以用来…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...