当前位置: 首页 > 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;但仍然可以用来…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...