【LeetCode】环形队列实现

目录

  • 前言
  • 1. 环形队列概念
  • 2. 循环队列实现设计
  • 3. 功能实现
    • 3.1 定义
    • 3.2 初始化
    • 3.3 判断队列是否为空
    • 3.4 判断队列是否为满
    • 3.5 入栈
    • 3.6 出栈
    • 3.7 获取队头数据
    • 3.8 获取队尾数据
    • 3.9 销毁
  • 4. 总结
  • 5. 完整通过代码

前言

之前我们学习环形链表相关问题，现在我们来看看环形队列有什么不同呢

循环队列题目链接

1. 环形队列概念

循环队列是一种线性数据结构，其操作依然是先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
最大的特点就是可以用利用这个队列之前用过的空间。
在这里插入图片描述


2. 循环队列实现设计

循环链表可以使用数组或链表实现
我这里用数组实现
如果需要存放是k个数据，我们就需要开辟k+1个数据空间，不然就无法判定空和满，导致数据插入和删除异常
需要两个变量来标识头（head）和尾（tail），出队front就向前移动，入队rear向前移动，但是这样会造成一个问题数组越界，循环就很好解决了这个问题，越界了就回到第一个数据位置。

  • 判空：head == tail
  • 盘满：head+1 == tail

3. 功能实现

3.1 定义

我们使用数组实现，需要一个数组，还有2个标志头(head)和尾(tail)的变量，和一个标志存放多少数据的变量k

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;

3.2 初始化

首先我们需要创建队列结构体，在给里面成员赋值，之前说了我们需要k+1数据的空间，防止不知道满了和空的情况，head和tail刚开始都是0，k还是实参传过来的，我们需要的是k+1数据的空间
在这里插入图片描述

MyCircularQueue* myCircularQueueCreate(int k) {
    // 创建队列结构体
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
    // 为队列里的数组创建k+1空间
    cq->a = (int*)malloc((k+1) * sizeof(int));
    cq->head = cq->tail = 0;
    cq->k = k;
    
    return cq;
}

3.3 判断队列是否为空

head和tail相等，就是空，不是就有数据

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    // head和tail相等就是空
    return obj->head == obj->tail;
}

3.4 判断队列是否为满

因为多开了一个数据空间，所以可以判断队列是否为满，tail+1 == head，就满了，多开一个数据的空间，可以保证满了的时候，tail和head无论什么情况，都至少有一个空间的距离，但是tail可能会越界，我需要取余
a只要取余b， a % b，余数一定是 0——b - 1，所以tail取余就不会越界，正好也满足了越界回到第一个数据位置。
而且还需要注意优先级问题，tail和k都是先加1，在进行取余
(obj->tail+1) % (obj->k+1) == obj->head

在这里插入图片描述

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // tail+1取余k+1，等于head，就是满
    return (obj->tail+1) % (obj->k+1) == obj->head; 
}

3.5 入栈

  1. 满了的就不能入数据了
  2. 插入数据tail就会增加，可能会越界，同样需要取余

在这里插入图片描述

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    // 队列满了，就不能插入数据
    if (myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->tail] = value;
    obj->tail++;
    
    // 插入数据会导致tail下标越界，越界处理：越界了就回到开始位置
    obj->tail %= obj->k+1;
    return true;
}

3.6 出栈

  1. 队列为空不能出数据
  2. 出栈，head就会向前移动，同样也会有越界问题，也需要取余
    在这里插入图片描述
ool myCircularQueueDeQueue(MyCircularQueue* obj) {
    // 队列为空，不能删除数据
    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->head++;
    // 删除数据会导致head下标越界，越界处理：越界了就回到开始位置
    obj->head %= obj->k+1;
    return true;
}

3.7 获取队头数据

队列为空不能取数据，返回数据的head位置的数据即可

int myCircularQueueFront(MyCircularQueue* obj) {
     // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 返回头下标的数据
    return obj->a[obj->head];
}

3.8 获取队尾数据

队列为空不能取数据，由于是先插入数据，后++，我们要取tail数据，需要-1，这个有两个情况，需要特殊处理

  • tail不为0，直接取数组tail - 1位置即可
  • tail为0，我们减1，tail为-1就会越界，返回最后一个数据的下标就是k的位置，这里有两种解决方法1、if判断 2、取余
  1. if判断
int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // tail等于0会越界，取消返回最后一个数据的下标
    if (obj->tail == 0)
        return obj->a[obj->k];

    return obj->a[obj->tail - 1];
}
  1. 取余
    由于空间长短是k+1，下标是k，他们之间最少也会差1，所以当前位置tail+k，在取余k+1，刚好就返回了tail的位置的前一个数据位置
    tail+k = k+1
    tail - 1

int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 由于空间长短是k+1，下标是k，他们之间最少也会差1
    // 所以当前位置tail+k，在取余k+1，刚好就返回了tail前一个数据位置
    // tail+k = k+1
    // tail - 1
    int tail = (obj->tail+obj->k) % (obj->k+1);
    return obj->a[tail];
}

3.9 销毁

同样也有两层结构，我们需要前销毁里层，在销毁外层
在这里插入图片描述

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

4. 总结

循环队列用数组实现就需要多注意数组越界问题


5. 完整通过代码

typedef struct {
    int* a;
    int head;	// 头
    int tail;	// 尾
    int k;		// 队列长度
} MyCircularQueue;

// 由于要先调用这两个函数，所以先声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    // 创建队列结构体
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
    // 为队列里的数组创建k+1空间
    cq->a = (int*)malloc((k+1) * sizeof(int));
    cq->head = 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++;
    
    // 插入数据会导致tail下标越界，越界处理：越界了就回到开始位置
    obj->tail %= obj->k+1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    // 队列为空，不能删除数据
    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->head++;
    // 删除数据会导致head下标越界，越界处理：越界了就回到开始位置
    obj->head %= obj->k+1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
     // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 返回头下标的数据
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    // 队列为空，不能取数据
    if (myCircularQueueIsEmpty(obj))
        return -1;

    // 由于空间长短是k+1，下标是k，他们之间最少也会差1
    // 所以当前位置tail+k，在取余k+1，真好就返回了前一个数据位置
    // tail+k = k+1
    // tail - 1

    // 取余法
    //int tail = (obj->tail+obj->k) % (obj->k+1);
    //return obj->a[tail];

     if (obj->tail == 0)
        return obj->a[obj->k];

    return obj->a[obj->tail - 1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    // head和tail相等就是空
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // tail+1取余k+1，等于head，就是满
    return (obj->tail+1) % (obj->k+1) == obj->head; 
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->head = obj->tail = obj->k = 0;
    free(obj);
}

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

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

相关文章

抖音爆火的QQ价格评估前端源码

抖音爆火的QQ价格评估前端源码

最近抖音很火直播给别人测qq价值多少，这个源码只有前端， 包含激活码验证页，评估页 源码免费下载地址抄笔记 (chaobiji.cn)
阅读更多...
流畅的python-学习笔记_符合python风格的对象

流畅的python-学习笔记_符合python风格的对象

对象表示形式 查看对象说明，可以通过__repr__和__str__方法，前者主要用于开发者，后者主要用于用户，这两个方法分别对内置函数repr和str函数提供支持 向量类 备选构造方法 classmethod和staticmethod staticmethod用的不是特别…
阅读更多...
力扣每日一练(螺旋矩阵)

力扣每日一练(螺旋矩阵)

54. 螺旋矩阵 - 力扣（LeetCode） 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 示例 1： 输入：matrix [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,…
阅读更多...
数据库提权

数据库提权

1.此时实验需要用到的软件： （1）phpStudy该程序包集成最新的ApachePHPMySQL phpMyAdminZendOptimizer,一次性安装,无须配置即可使用,是非常方便、好用的PHP调试环境.该程序不仅包括PHP调试环境,还包括了开发工具、开发手册等.总之学习PHP只需…
阅读更多...
STM32——TIMER（定时器）篇

STM32——TIMER（定时器）篇

技术笔记！ 1. 定时器概述（了解） 1.1 软件定时器原理 使用纯软件（CPU死等）的方式实现定时（延时）功能 缺点：1. 延时不准确 2. CPU死等。 1.2 定时器定时原理 1.…
阅读更多...
在Codelab对llama3做Lora Fine tune微调

在Codelab对llama3做Lora Fine tune微调

Unsloth 高效微调大模型的工具，通过Unsloth微调Llama3, Mistral, Gemma 速度提升2-5倍，内存减少70%！ Codelab 创建一个jupyter notebook 选择 T4 GPU 安装Fine tune 相关的lib %%capture import torch major_version, minor_version torch…
阅读更多...
等保测评—Linux-CentOS标准范例截图

等保测评—Linux-CentOS标准范例截图

密码输入错误无法登录 用户账户情况包含root、guanli、shenji 查看审计用户权限 身份鉴别： cat /etc/passwd，核查用户名和 UID，是否存在同样的用户名和 UID cat /etc/shadow，查看文件中各用户名状态 ， 核查密码一栏为…
阅读更多...
day1Qt作业

day1Qt作业

#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {this->resize(540,415);//窗口大小this->setFixedSize(540,415);//固定窗口大小this->setWindowTitle("QQ");//标题this->setWindowIcon(QIcon("E:\\hqyjap…
阅读更多...
获取转转数据，研究完转转请求，tx在算法方面很友好。

获取转转数据，研究完转转请求，tx在算法方面很友好。

本篇文章仅供学习讨论。 文章中涉及到的代码、实例，仅是个人日常学习研究的部分成果。 如有不当，请联系删除。 在研究完阿里的算法以后（其实很难说研究完，还有很多内容没有研究透，只能说暂时告一段落）&…
阅读更多...
【CTF Web】XCTF GFSJ0475 get_post Writeup（HTTP协议+GET请求+POST请求）

【CTF Web】XCTF GFSJ0475 get_post Writeup（HTTP协议+GET请求+POST请求）

get_post X老师告诉小宁同学HTTP通常使用两种请求方法，你知道是哪两种吗？ 解法 用 Postman 发送一个 GET 请求，提交一个名为a,值为1的变量。 http://61.147.171.105:65402/?a1用 Postman 发送一个 POST 请求，提交一个名为b,值为…
阅读更多...
Embeddings原理、使用方法、优缺点、案例以及注意事项

Embeddings原理、使用方法、优缺点、案例以及注意事项

Embeddings是一种将高维数据映射到低维空间的技术，常用于处理自然语言处理（NLP）和计算机视觉（CV）任务。Embeddings可以将复杂的高维数据转换为低维稠密向量，使得数据可以更容易地进行处理和分析。本文将介绍…
阅读更多...
国内首发 | CSA大中华区启动《AI安全产业图谱（2024）》调研

国内首发 | CSA大中华区启动《AI安全产业图谱（2024）》调研

在人工智能（AI）技术的快速发展浪潮中，AI安全已成为全球关注的焦点。为应对AI安全带来的挑战，确保AI技术的健康发展，全球范围内的研究机构、企业和技术社区都在积极探索解决方案。 在这一背景下，CSA大中华区…
阅读更多...
在2G到4g小区重选过程中，4g频点没有优先级信息，最后UE无法重选到4g，是否正常？

在2G到4g小区重选过程中，4g频点没有优先级信息，最后UE无法重选到4g，是否正常？

这个确实是老问题了，要翻开GSM 的协议找答案。 GSM cell reselection算法分为cell ranking based和priority based两种方式。cell ranking based 只能从GSM重选到UTRAN；而priority based则可以重选到UTRAN和EUTRA。 根据priority based重选算法的描述&am…
阅读更多...
【WP】第一届 “帕鲁杯“ - CTF挑战赛 Web 全解

【WP】第一届 “帕鲁杯“ - CTF挑战赛 Web 全解

Web Web-签到 考点：审计py代码 from flask import Flask, request, jsonify import requests from flag import flag # 假设从 flag.py 文件中导入了 flag 函数 app Flask(__name__)app.route(/, methods[GET, POST]) def getinfo():url request.args.get(url)i…
阅读更多...
java08基础(值传递和引用传递 类和对象)

java08基础(值传递和引用传递 类和对象)

目录 一. 值传递和引用传递 1. 值传递 2. 引用传递 二. 面向对象思想 三. 类和对象 1. 类 2. 对象 2.1 使用 2.2 成员变量和局部变量区别 2.3 操作成员方法 2.4 this关键字(初始) 2.5 构造方法 (见java09) 一. 值传递和引用传递 1. 值传递 值传递是指在调用函数时将…
阅读更多...
webpack4和webpack5区别1---loader

webpack4和webpack5区别1---loader

webpack4处理图片和字体的loader file-loader file-loader的作用是处理webpack中的静态资源文件。File Loader可以将各种类型的文件，如图像、字体、视频等转换为模块并加载到Web应用程序中。它通过import或require语句引入文件资源，并将其放置在输出目…
阅读更多...
多链路聚合设备是什么

多链路聚合设备是什么

多链路聚合设备属于通信指挥装备。 乾元通多链路聚合设备，它能够将多个网络链路聚合成一个逻辑链路，以实现高速、稳定、可靠的数据传输。多链路聚合设备的核心技术包括链路聚合、负载均衡、故障切换等，能够智能管理和优化利用不同网络链路&a…
阅读更多...
概率论 科普

概率论 科普

符号优先级 概率公式中一共有三种符号：分号 ; 、逗号 , 、竖线 | 。 ; 分号代表前后是两类东西，以概率P(x;θ)为例，分号前面是x样本，分号后边是模型参数。分号前的 表示的是这个式子用来预测分布的随机变量x，分号后的…
阅读更多...
第一篇：刚接触测试你应该知道什么

第一篇：刚接触测试你应该知道什么

欢迎你接触软件测试这一行业。 刚接触它时，你肯定或多或少会有疑惑，我该做什么？大家口口相传的软件测试就是 【点点点】 真的是你日常的工作吗？ 那么本文我将陪你一起，对我们刚接触到测试这个工作以后，应该…
阅读更多...
为什么电子商务安全是速度和保护之间的平衡行为

为什么电子商务安全是速度和保护之间的平衡行为

微信搜索关注公众号网络研究观，获取更多信息。 电子商务世界是一把双刃剑。虽然它为企业和消费者提供了便利和可访问性，但它也为网络犯罪分子提供了诱人的目标。在这个不断变化的环境中，优先考虑安全不再是一种选择；而是一种选择&…
阅读更多...
最新文章

Copyright @ 2022~2023