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

【队列】循环队列（Circular Queue）详解

news 来源：原创 2025/9/19 7:44:56

文章目录

一、循环队列简介
二、循环队列的判空和判满
三、循环队列的实现
- leetcode 622. 设计循环队列

一、循环队列简介

在实际开发中，队列是一种常用的数据结构，而循环队列（Circular Queue）则一般是一种基于数组实现的队列（也可使用循环链表）。与传统的 FIFO 队列相比，循环队列通过将数组首尾相连形成一个 “环”，能够更高效地利用内存空间。

循环队列的主要思想是：当队尾指针到达数组末端时，如果数组前面还有空余空间，就可以从数组头部重新利用这些空间进行入队操作。也就是说，数组的末端和头部通过逻辑上的连接，形成一个环状结构，从而避免了顺序队列中由于出队操作而导致的空间浪费问题。

如下图就是一个典型的循环队列，其中的 front 表示头指针，指向队头。rear 则表示尾指针，指向队尾元素的下一个位置。

请添加图片描述

二、循环队列的判空和判满

在循环队列中，front 与 rear 都是可以循环移动的，当队空时，front == rear 成立；当队满时，front == rear 也成立。因此显然不能只凭 front == rear 来判断队空还是队满。

为了解决这个问题，在循环队列中约定：少用一个元素空间，当队尾标识的 rear在队头标识front 的上一个位置时，队列为满。此时，判断队空和队满的条件分别如下：

队空时：front == rear

队满时：(rear + 1) % MAXSIZE == front

其中，MAXSIZE 是队列容量的大小

两种情况下队列中指针的状态如下图所示：

请添加图片描述

既然少一个元素空间，这就意味着，如果要存储的数据个数最大为 k，那么你需要开辟的循环队列的大小应为 k+1

三、循环队列的实现

我们来以具体的一道题目来实现循环队列的各种操作

leetcode 622. 设计循环队列

请添加图片描述

typedef struct {int* a;int front;  // 头“指针”指向队头数据int tail;  // 尾“指针”指向队尾的下一个位置int k;  // 一会儿开辟的队列大小为 k+1
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);  // 前面先实现的函数要用到这两个接口，所以事先声明一下// 循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->a = (int*)malloc(sizeof(int)*(k+1));cq->front = 0;  // 初始化数据cq->tail = 0;cq->k = k;return cq;
}// 入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)) return false;  // 满了就不能再入了obj->a[obj->tail] = value;  // 将数据入进来++obj->tail; // 更新tailobj->tail %= (obj->k+1);  // tail 自增了之后可能超出循环队列的大小范围所以要取模// 模的是循环队列的大小 k+1return true;
}// 出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return false;  // 为空就不能再删obj->front = (obj->front+1)%(obj->k+1);  // 和前面是一样的原理，注意同样是加一再取模return true;
}// 获取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return -1;return obj->a[obj->front];
}// 获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return -1;if(obj->tail == 0) return obj->a[obj->k];  // 跨越了一个循环的情况else return obj->a[obj->tail-1];
}// 判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;
}// 判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1) % (obj->k+1) == obj->front;  // tail的后一个是front说明满了，但是有可能tail+1跨过了一个循环。所以要取模
}// 释放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);  // 注意这里要先释放结构体内的数组！！！不然会可能内存泄漏free(obj);  
}

【队列】循环队列（Circular Queue）详解

文章目录一、循环队列简介二、循环队列的判空和判满三、循环队列的实现leetcode 622. 设计循环队列一、循环队列简介在实际开发中，队列是一种常用的数据结构，而循环队列（Circular Queue）则一般是一种基于数组实现的队列&#x…...

编程日记 2025/9/19 7:44:56

Spring-GPT智谱清言AI项目(附源码)

一、项目介绍本项目是Spring AI第三方调用整合智谱请言（官网是：https://open.bigmodel.cn）的案例，回答响应流式输出显示，这里使用的是免费模型，需要其他模型可以去 https://www.bigmodel.cn/pricing 切换…...

编程日记 2025/9/19 7:42:43

【JavaEE进阶】MyBatis入门

目录 🌴前言 🌲什么是MyBatis? 🌳准备工作 🚩创建工程 🚩配置数据库连接字符串 🚩数据准备 🚩编写持久层代码 🍃单元测试 🌴前言在应⽤分层学习时,我们了解到…...

编程日记 2025/9/19 7:43:56

网络安全:防范NetBIOS漏洞的攻击

稍微懂点电脑知识的朋友都知道，NetBIOS 是计算机局域网领域流行的一种传输方式，但你是否还知道，对于连接互联网的机器来讲，NetBIOS是一大隐患。漏洞描述 NetBIOS(Network Basic Input Output System，网络基本输入输…...

编程日记 2025/9/15 13:54:54

【OS安装与使用】part3-ubuntu安装Nvidia显卡驱动+CUDA 12.4

文章目录一、待解决问题1.1 问题描述1.2 解决方法二、方法详述2.1 必要说明2.2 应用步骤2.2.1 更改镜像源2.2.2 安装NVIDIA显卡驱动：nvidia-550（1）查询显卡ID（2）PCI ID Repository查询显卡型号（3&#xf…...

编程日记 2025/9/19 7:42:41

如何在本地和服务器新建Redis用户和密码

文章目录一. Redis安装二. 新建Redis用户，测试连接2.1 本地数据库2.2 线上数据库2.2.1 安装和配置2.2.2 测试连接三. 配置四. 分布式一. Redis安装 Redis安装可以设置开机自动启动，也可以在去查看系统服务，按[win R]，输入命…...

编程日记 2025/9/15 22:05:17

使用SHOW PROCESSLIST和SHOW ENGINE INNODB STATUS排查mysql锁等待问题

现象： mysql 查某表一直不能结束，查别的表没有问题。已知之前刚刚alter此表想把它的一个字段长度增长，但是这个操作一直没有结束。现在应该怎么办? 方案: 使用 SHOW PROCESSLIST; 查看当前所有活动的SQL线程，找出是否有长时间…...

编程日记 2025/9/19 7:42:40

探索HarmonyOS的UI开发新境界：从基础到进阶的深度解析

在科技日新月异的今天，操作系统作为连接硬件与软件的桥梁，其重要性不言而喻。HarmonyOS，作为华为自主研发的分布式全场景操作系统，正以其独特的分布式技术架构和一次开发多端部署的能力，引领着操作系统的新潮流。本文将…...

编程日记 2025/9/18 12:56:41

Android 动态加入Activity 时 manifest 注册报错解决。使用manifestPlaceholders 占位

需求如下： 项目测试demo 有多个渠道，部分渠道包含支付功能，在主测试代码外，需要一个单独 Activity 调用测试代码。 MainActivityPayActivity渠道A包含不包含渠道B包含包含因为支付功能需要引入对应的 moudule，因此…...

编程日记 2025/9/18 12:13:27

OpenCV（1）：简介、安装、入门案例、基础模块

1 OpenCV 简介 OpenCV 是一个功能强大、应用广泛的计算机视觉库，它为开发人员提供了丰富的工具和算法，可以帮助他们快速构建各种视觉应用。随着计算机视觉技术的不断发展，OpenCV 也将会继续发挥重要的作用。OpenCV 提供了大量的计算机视觉算法…...

编程日记 2025/9/13 14:20:57

Linux-GlusterFS操作子卷

文章目录分布式卷添加卷分布式卷删除子卷删除总卷 🏡作者主页：点击！ 🤖Linux专栏：点击！ ⏰️创作时间：2025年02月20日19点30分分布式卷添加卷 Node1上进行操作扩容 #服务器端 gluster volu…...

编程日记 2025/9/14 18:26:43

kettle从入门到精通第九十二课 ETL之kettle 使用Kettle的Carte对外发布读写接口

场景：使用kettle实现将查询结果返回给客户端，也就是说kettle暴露查询接口供外围系统调用。前提必须是使用carte服务才可以提供接口供外部系统调用。具体实操方法如下： 1、设计转换根据具体需求设计转换，主要用到的步骤有获取变…...

编程日记 2025/9/18 6:06:38

【精调】LLaMA-Factory 快速开始1: Meta-Llama-3.1-8B-Instruct

llamafactory-cli train examples/train_lora/llama3_lora_sft.yaml llamafactory-cli chat examples/inference/llama3_lora_sft.yaml llamafactory-cli export examples/merge_lora/llama3_lora_sft.yaml模型下载 git clone https://www.modelscope.cn/LLM-Research/Meta-Lla…...

编程日记 2025/9/12 8:42:00

数据库加密全解析：从传输到存储的安全实践

title: 数据库加密全解析：从传输到存储的安全实践 date: 2025/2/17 updated: 2025/2/17 author: cmdragon excerpt: 数据加密是数据库安全的最后一道物理防线。传输层SSL/TLS配置、存储加密技术及加密函数实战应用，覆盖MySQL、PostgreSQL、Oracle等主流数据库的20+生产级加密…...

编程日记 2025/9/9 12:40:10

PHP+Apache+MySQL安装（Windows）

一、安装教程参考链接1 参考链接2 二、问题描述 PHP安装目录下找不到php8apache2_4.dll PHP安装包下载错误 Apache Service Monitor: request operation has failed! 定位问题： 查看【事件查看器】解决问题安装或更新与PHP版本相对应的Visual C Redistribu…...

编程日记 2025/8/30 13:50:11

alt+tab切换导致linux桌面卡死的急救方案

环境 debian12 gnome43.9 解决办法观察状态栏，其实系统是没有完全死机的，而且gnome也可能没有完全死机。 1. alt f4 关闭桌面上的程序，因为这个方案是我刚刚看到的，所以不确定能不能用，比起重启系统，…...

编程日记 2025/9/16 5:13:39

Mysql基础语句

一、 MySQL语句在熟悉安装及访问 MySQL 数据库以后， 接下来将学习使用 MySQL 数据库的基本操作，这也是在服务器运维工作中不可或缺的知识。本节中的所有数据库语句均在“MySQL>”操作环境中执行 MySQL 是一套数据库管理系统，在每台 MySQ…...

编程日记 2025/9/18 13:11:47

网络通信基础：端口、协议和七层模型详解，网络安全零基础入门到精通实战教程！

一、端口和协议的概念 1.在网络技术中，端口(Port) 大致有两种意思： 一是物理意义上的端口，比如，ADSL Modem、集线器、交换机、路由器用于连接其他网络设备的接口，如RJ-45端口、SC端口等等。二是逻辑意义上的端口&…...

编程日记 2025/9/13 22:08:28

【力扣Hot 100】栈2

5. 柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例 1: !https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg …...

编程日记 2025/9/10 3:33:46

1. Linux下 MySQL 的详细安装与使用

1. Linux下 MySQL 的详细安装与使用文章目录 1. Linux下 MySQL 的详细安装与使用1. Linux 下安装 MySQL8.0 的详细安装步骤：2. Linxu 当中的MySQL 设置远程登录3. 最后： 1. Linux 下安装 MySQL8.0 的详细安装步骤： 查看是否安装过MySQL&…...

编程日记 2025/9/14 16:03:37

Idea24.3 如何设置Git忽略某一个文件

文章目录左上角找到commit选中你要忽略的文件右键New Changelist给这个文件夹名称和描述点击ok将要忽略的文件添加到这个文件夹左上角找到commit 选中你要忽略的文件右键New Changelist 给这个文件夹名称和描述点击ok 将要忽略的文件添加到这个文件夹...

编程日记 2025/9/16 12:08:18

2025-02-20 学习记录--C/C++-PTA 7-27 冒泡法排序

一、题目描述 ⭐️ 二、代码（C语言）⭐️ /** * 冒泡法实现升序 */#include <stdio.h>int main() {int N, // 整数个数 6K, // 扫描遍数 2num, // 待排序的整数 2 3 5 1 6 4numArr[100], // 待排序的整数合集 2 3 5 1…...

编程日记 2025/9/14 8:08:45

如何修改Windows系统Ollama模型存储位置

默认情况下，Ollama 模型会存储在 C 盘用户目录下的 .ollama/models 文件夹中，这会占用大量 C 盘空间，增加C盘“爆红”的几率。所以，我们就需要修改Ollama的模型存储位置 Ollama提供了一个环境变量参数可以修改Ollama的默认存在位…...

编程日记 2025/9/18 10:51:06

【Python爬虫(26)】Python爬虫进阶：数据清洗与预处理的魔法秘籍

【Python爬虫】专栏简介：本专栏是 Python 爬虫领域的集大成之作，共 100 章节。从 Python 基础语法、爬虫入门知识讲起，深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑，覆盖网页、图片、音频等各类数据爬取&#xff…...

编程日记 2025/9/10 22:06:04

NPM如何更换淘宝镜像——Node.js国内镜像配置教程

在国内使用 npm 安装 Node.js 包时，由于网络环境的原因，下载速度可能非常慢。为了解决这个问题，很多开发者会选择使用淘宝镜像（现在由 npmmirror.com 维护）。本文将带你一步一步完成更换 npm 源为淘宝镜像的配置&#…...

编程日记 2025/9/12 8:30:24

汽车免拆诊断案例 | 2010 款路虎揽胜车空调偶尔出风异常

故障现象　一辆2010款路虎揽胜车，搭载5.0 L发动机，累计行驶里程约为16万km。车主反映，接通空调开关后，有时出风忽大忽小，有时不出风，有时要等2 min左右才出风；有时两三天出现一次，…...

编程日记 2025/9/11 22:34:15

pytorch3d安装记录

官方安装教程： https://github.com/facebookresearch/pytorch3d/blob/main/INSTALL.md 通过pip 或conda 可以很容易安装上预编译好的包， 安装过程不会报错， 但是使用的时候就会报各种错误 ，原因是预编译好的包跟自己的环境不一定…...

编程日记 2025/9/14 12:57:31

服务器通过 ollama 运行deepseek r1

1、服务器环境简介 56核 CPU64G 内存无显卡已安装 Ollama 2、下载模型与配置正常可以通过 ollama pull 或 ollama run 命令直接下载，但通常会遇到连接超时、找不到网址等总理。因此，可以使用国内的模型站进行下载，在这里使用魔塔查找模型…...

编程日记 2025/9/11 13:29:42

ollama stream“:True django如何返回数据

在使用 Django 框架开发 Web 应用时，如果你想要通过 Ollama 流式返回数据，你可以通过 Django 的 HttpResponse 或者 StreamingHttpResponse 来实现。Ollama 主要用于处理文本生成任务，如聊天机器人、自动完成等，通常这些任务会产生…...

编程日记 2025/9/15 20:28:56

RabbitMQ 消息队列

1. 消息队列是什么？ 当用户注册成功后，就发送邮件。当邮件发送成功了，接口才会提示注册成功信息。但由于发送邮件，依赖于其他厂商的服务，有可能他们的接口会非常耗时。那么用户就一直要等着邮件发送成功了，…...

编程日记 2025/9/11 0:43:13

idea从远程gitee拉取项目

文章目录从gitee上面拿到项目地址填写远程地址,并且设置项目保存位置拉取成功从gitee上面拿到项目地址填写远程地址,并且设置项目保存位置拉取成功...

编程日记 2025/9/8 14:17:14

PHP集成软件用哪个比较好？

在Windows环境下，使用PHP时，通常需要一个集成开发环境（IDE）或者集成软件来简化开发和调试过程。以下是几款常用且推荐的PHP集成软件，每款都有其特点，可以根据需求进行选择： 1. XAMPP 特点&…...

编程日记 2025/9/16 5:43:27

Es的text和keyword类型以及如何修改类型

昨天同事触发定时任务发现es相关服务报了一个序列化问题， 今天早上捕获异常将异常堆栈全部打出来看，才发现是聚合的字段不是keyword类型的问题。到kibbna命令行执行也是一样的错误使用 /_mapping查看索引的字段类型，才发现userUniqueid是te…...

编程日记 2025/9/16 9:04:14

【找工作】C++和算法复习（自用）

文章目录 C头文件自定义排序函数stl 算法数据结构树状数组数学自用随便记录 C 排序 stl 头文件全能头文件： #include<bits/stdc.h>自定义排序函数 bool compare(const int &odd1,const int &odd2) {return odd1>odd2; }stl 枚举map map&…...

编程日记 2025/9/16 15:37:21

Python VsCode DeepSeek接入

Python VsCode DeepSeek接入创建API key 首先进入DeepSeek官网，https://www.deepseek.com/ 点击左侧“API Keys”，创建API key，输出名称为“AI” 点击“创建"，将API key保存，复制在其它地方。在VsCode中下载…...

编程日记 2025/9/16 15:37:19

开放表格式和对象存储架构指南

比较 Apache Iceberg、Delta Lake 和 Apache Hudi，并了解如何为您的数据湖仓一体选择合适的开放表格式。开放表格式和对象存储正在重新定义组织构建其数据系统的方式，为可扩展、高效且面向未来的数据湖仓一体奠定了基础。通过利用对象存储的独特优势&…...

编程日记 2025/9/19 2:59:23

Netty入门详解

引言 Netty 是一个基于 Java 的高性能、异步事件驱动的网络应用框架，用于快速开发可维护的高性能网络服务器和客户端。它提供了一组丰富的 API，使得开发人员能够轻松地处理各种网络协议，如 TCP、UDP 等，并且支持多种编解码方式&a…...

编程日记 2025/9/18 1:16:10

我国首条大型无人机城际低空物流航线成功首航

首航震撼开场：羊肉 “飞” 越 540 公里在夜色的笼罩下，榆阳马合通用机场的跑道上，一架大型固定翼无人机蓄势待发，机身被灯光照亮，宛如一只即将展翅翱翔的钢铁巨鸟。它的货舱里，满满装载着新鲜的榆林羊肉&a…...

编程日记 2025/9/18 15:08:20

【数据挖掘】--算法

【数据挖掘】--算法目录：1. 缺失值和数值属性处理1缺失值处理： 2. 用于文档分类的朴素贝叶斯3. 分治法：建立决策树4. 覆盖算法建立规则5. 挖掘关联规则6. 线性模型有效寻找最近邻暴力搜索（Brute-Force Search）kd树&am…...

编程日记 2025/9/18 18:16:51

C++初阶——简单实现vector

目录 1、前言 2、Vector.h 3、Test.cpp 1、前言简单实现std::vector类模板。相较于前面的string，vector要注意： 深拷贝，因为vector的元素可能是类类型，类类型元素可以通过赋值重载，自己实现深拷贝。迭代器失效…...

编程日记 2025/9/16 15:37:10

三、Three.js模型对象、材质

一、三维向量Vector3与模型位置点模型Points、线模型Line、网格网格模型Mesh等模型对象的父类都是Object3D，如果想对这些模型进行旋转、缩放、平移等操作，如何实现，可以查询Threejs文档Object3D对相关属性和方法的介绍 1、三维向量Vector3 …...

编程日记 2025/9/16 15:37:09

C# 背景透明抗锯齿（效果完美）

主要是通过 P/Invoke 技术调用 Windows API 函数 gdi32.dll/user32.dll，同时定义了一些结构体来配合这些 API 函数的使用，常用于处理图形绘制、窗口显示等操作。运行查看效果局部放大，抗锯齿效果很不错,尾巴毛毛清晰可见。 using System; u…...

编程日记 2025/9/16 15:37:07

Ubuntu 22.04 一键部署MinerU1.1.0

MinerU MinerU是一款将PDF转化为机器可读格式的工具（如markdown、json），可以很方便地抽取为任意格式。 MinerU诞生于书生-浦语的预训练过程中，我们将会集中精力解决科技文献中的符号转化问题，希望在大模型时代为科技发…...

编程日记 2025/9/16 15:37:05

10、k8s对外服务之ingress

service和ingress的作用 service的作用 NodePort：会在每个节点开放一个端口，端口号30000-32767。也是只能用于内网访问，四层转发。实现负载均衡。不能基于域名进行访问。 clusterip：service的默认类型，只能在集群…...

编程日记 2025/9/16 15:37:03

mysql面试题

一、基础概念什么是主键（Primary Key）？ 答案： 唯一标识表中每行数据的字段或字段组合，不允许 NULL 值，确保数据唯一性。外键（Foreign Key）的作用是什么？ 答案&#xf…...

编程日记 2025/9/16 4:05:06

什么是关系型数据库？什么是非关系型数据库？

关系型数据库：关系型数据库是基于关系模型的数据库，它将数据组织成二维表格的形式，每个表格称为一个表（Table），表中的每一行称为一条记录（Record）或元组（Tuple&#xff0…...

编程日记 2025/9/11 10:10:32

科技云报到：科技普惠潮流渐起，“开源”将带我们走向何方？

科技云报到原创。开源决定软件未来，已成为全球技术和产业创新的主导模式之一。“开源”思想的诞生，可以说是计算机发展史中极具理想主义和浪漫主义色彩的一页，是科技自由与技术极客思想的延伸。数字化浪潮奔涌，从软件开发的底…...

编程日记 2025/9/12 8:08:07

校园网架构设计与部署实战

一、学习目标掌握校园网分层架构设计原则理解多业务VLAN规划方法学会部署认证计费系统实现基础网络安全防护二、典型校园网场景需求分析：某中学需建设新型校园网络覆盖教学楼/宿舍/图书馆三区域区分教师/学生/访客网络权限满足2000终端并发接入 …...

编程日记 2025/9/15 0:33:33

【含开题报告+文档+PPT+源码】基于Springboot的乡村老龄居民信息管理系统

开题报告本文介绍了一个基于Spring Boot框架的乡村老龄居民信息管理系统。该系统旨在通过信息化手段，提高乡村老龄居民的生活质量，并为相关部门提供便捷的数据管理和服务支持。系统主要实现了用户注册登录、个人信息查看、健康数据录入、健康建议查询、…...

编程日记 2025/9/14 1:48:59

前端插件使用xlsx-populate，花样配置excel内容，根据坐添加标替换excel内容，修改颜色，合并单元格...。

需求要求：业务人员有个非常复杂得excel表格，各种表头等，但是模板是固定得。当然也可以实现在excel上搞出各种表格，但是不如直接用已有模板替换其中要动态得内容方便，这里我们用到CSDN得 xlsx-populate 插件。实列中我…...

编程日记 2025/9/14 1:49:02

文章目录

一、循环队列简介

二、循环队列的判空和判满

三、循环队列的实现

leetcode 622. 设计循环队列

相关文章：