循环队列、双端队列

循环队列、双端队列

  • 1. 循环队列
  • 1.1 循环队列
  • 1.2 代码实现
  • 1.3 力扣622. 设计循环队列
  • 2. 双端队列

1. 循环队列

1.1 循环队列

在这里插入图片描述

  • 特殊的队列,首尾相连,空间可重复利用
  • 环形队列常使用数组实现,且为了方便队列的判空、判满处理,会浪费一个大小的空间,该空间不存储元素,比如待存储元素共n个,则开辟大小为n+1的数组实现循环队列
  • 循环队列,判空:head=tail;判满:(tail+1)%arr.length=head
  • head、tail分别为头指针、尾指针,初始化时均指向index=0位置;
  • head指向队头元素,tail指向队尾元素的下一个位置
  • 元素出队时,front_val=arr[head]
  • 元素入队时,arr[tail]=val、tail=(tail+1)%n
  • 队尾元素位置为:lastIndex=(tail-1+n)%n
  • 队列中有效元素下标为:[head,lastIndex]

初始化,队列为空:
在这里插入图片描述

队列满:
在这里插入图片描述

  • 涉及到下标移动,有两个计算公式,其中offset=offset%arr.length
    1)下标最后再往后(offset 小于 array.length): index = (index + offset) % arr.length
    2)下标最前再往前(offset 小于 array.length): index = (index + arr.length - offset) % arr.length

1.2 代码实现

public class LoopQueue{
    // 队列:存储数据
    private int[] data;
    // 队列实际长度,其中1个位置不存储数据
    private int n;
    // 头指针、尾指针
    private int head,tail;

    public LoopQueue(int size){
        data=new int[size+1];
        n=data.length;
        head=0;
        tail=0;
    }
    public boolean isEmpty() {
        return head==tail;
    }

    public boolean isFull() {
        return (tail+1)%n==head;
    }
    // 入队操作
    public boolean offer(int val) {
        if (isFull()){
            return false;
        }
        data[tail]=val;
        tail=(tail+1)%n;
        return true;
    }

    // 出队操作
    public int poll() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空,无法进行出队操作!");
        }
        int val=data[head];
        head=(head+1)%n;
        return val;
    }

    // 获取队头元素
    public int peek() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空,无法获取队头元素!");
        }
        return data[head];
    }

    // 遍历队列
    @Override
    public String toString() {
        StringBuilder content=new StringBuilder("[");
        int i=head;
        while (i!=tail){
            content.append(data[i]);
            if (i!=tail-1){
                content.append(",");
            }
            i=(i+1)%n;
        }
        content.append("]");
        return content.toString();
    }
}

1.3 力扣622. 设计循环队列

622. 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

class MyCircularQueue {
    int[] queue;
    int head;
    int tail;
    int n;
    public MyCircularQueue(int k) {
        queue=new int[k+1];
        head=0;
        tail=0;
        n=queue.length;
    }

    public boolean enQueue(int value) {
        if (isFull()){
            return false;
        }
        queue[tail]=value;
        tail=(tail+(1%n))%n;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()){
            return false;
        }
        head=(head+1)%n;
        return true;
    }

    public int Front() {
        if (isEmpty()){
            return -1;
        }
        int val=queue[head];
        return val;
    }

    public int Rear() {
        if (isEmpty()){
            return -1;
        }
        int val=queue[(tail-1+n)%n];
        return val;
    }

    public boolean isEmpty() {
        return head==tail;
    }

    public boolean isFull() {
        return (tail+1)%n==head;
    }
}

2. 双端队列

  • 双端队列deque 是 “double ended queue” 的简称,是指允许两端都可以进行入队和出队操作的队列;
    在这里插入图片描述
  • Java中使用Deque接口表示双端队列,其实现类有LinkedList、ArrayDeque两个;

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

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

相关文章

【数据可视化】第五章—— 基于PyEcharts的数据可视化

文章目录 1. pyecharts数据可视化介绍2.pyecharts安装与使用3.全局配置项和系列配置项3.1 全局配置项3.1.1 基本元素配置项3.1.2 坐标轴配置项3.1.3 原生图形配置项 3.2 系列配置项3.2.1 样式类配置项3.2.2 标记类型配置项3.2.3 其它类配置项 4&#xff…

4。计算机组成原理(2)存储系统

嵌入式软件开发,非科班专业必须掌握的基本计算机知识 核心知识点:数据表示和运算、存储系统、指令系统、总线系统、中央处理器、输入输出系统 这一部分主要讲解了CPU的组成和扩容、CPU与存储器(主存、辅存、缓存)的连接 一 存储…

基于人工智能AI视频分析的智慧安监解决方案

方案背景 为了保证对园区环境风险进行有效识别,传统视频监控存在视频结构化利用率低的问题,在实际使用过程中,安全管理人员工作效率低下,依靠人工肉眼查看灵活度低,风险漏报概率高,出现异常情况跟踪不及时&…

VS2019 c++ cmake项目 打包并使用 (lib\dlll)

背景 最近项目中经常调用第三方库、带头文件、lib和dll的库,需要使用cmake进行项目管理,之前一直比较糊涂这方面,在这里做一个整理总结 编译汇编过程 静态链接方式: 把lib里面编译好的东西(函数、变量等&#xff09…

海量请求下,高并发接口的设计思路

1. 背 景 虽然现在很多人,动不动就提什么高并发、请求量多大,数据量多少多少,但我可以很认真地说,那都是他妈的在吹牛! 生产环境,真正有大请求量的,就那么几个业务场景,而且多是面…

算法记录 | Day56 动态规划

583.两个字符串的删除操作 思路: 1.确定dp数组(dp table)以及下标的含义:dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数…

网络协议与攻击模拟-05-ICMP协议

ICMP 协议 1、理解 ICMP 协议 2、理解 ICMP 重定向 3、会使用 wireshark 分析 ICMP 重定向流量实验 一、 ICMP 基本概念 1、 ICMP 协议 Internet 控制报文协议,用于在 IP 主机、路由器之间传递控制消息,控制消息指网络通不通、主机是否可达、路由是否…

iview-admin首页的图表数据渲染问题

iview-admin的首页有几个图表&#xff0c;应该是作者自己封装的&#xff0c;有个问题是在mounted时&#xff0c;从后台获取数据&#xff0c;应该把图表根据数据重新渲染一下。 <chart-bar id"myChart" style"height: 260px;" :value"barData"…

全方位揭秘!大数据从0到1的完美落地之Shuffle和调优

MapReduce高级 shuffle阶段 概述 MapReduce会确保每个reducer的输入都是按键排序的。从map方法输出数据开始、到作为输入数据传给reduce方法的过程称为shuffle。在此&#xff0c;我们将学习shuffle是如何工作的&#xff0c;因为它有助于我们理解工作机制&#xff08;如果需要…

前端008_类别模块_新增功能

类别模块_新增功能 1、需求分析2、新增窗口实现3、列表引用新增组件4、关闭弹出窗口5、校验表单数据6、提交表单数据6.1、Mock 添加新增模拟接口6.2、Api 调用接口6.3、测试新增功能1、需求分析 点击 新增 按钮后,对话框形式弹出新增窗口输入分类信息后,点击 确定 提交表单数…

【递推专题】常见的递推“模型”总结

目录 1.斐波那契数列分析&#xff1a;代码&#xff1a; 2.平面分割问题分析&#xff1a; 3.汉诺塔问题分析&#xff1a; 4.卡特兰数分析&#xff1a; 5.第二类斯特林数总结&#xff1a; 1.斐波那契数列 分析&#xff1a; 斐波那契数列又称兔子数列&#xff0c;其原理来源于兔子…

测试知识总结

1.影响ui自动化稳定性 异常弹出对话框 --异常场景库 页面控件元素属性的细微变化--模糊匹配 延迟 --- retry 数据 -- 数据已被使用 2. 移动端应用细分为三大类&#xff1a;Web App、Native App&#xff08;原生应用&#xff09; 和 Hybrid App&#xff08;混合应用&…

第二十四章 Unity 纹理贴图

通常情况下&#xff0c;3D网格模型只能展示游戏对象的几何形状&#xff0c;而表面的细节则纹理贴图提供。纹理贴图通过UV坐标“贴附”在模型的表面。当然&#xff0c;这个过程不需要我们在Unity中完成&#xff0c;而是在建模软件中完成的。通常情况下&#xff0c;我们通过3ds m…

JavaScript:二叉树(前序遍历,中序遍历,后序遍历,递归法,统一迭代法)

文章目录 二叉树递归法迭代法 144. 二叉树的前序遍历 - 力扣&#xff08;LeetCode&#xff09;二叉树的递归遍历递归法作图分析代码和思路分析 二叉树的迭代遍历前序遍历迭代分析代码及思路分析 94. 二叉树的中序遍历递归法作图举例递归流程 迭代法代码 145. 二叉树的后序遍历 …

制作Alpine Linux镜像报错errors: 15 distinct packages available

1.执行报错 执行docker build -t 镜像:版本 -f Dockerfile . 报错&#xff1a; 2.查看网上的解决思路 网上文档解决思路&#xff1a; 这边我做了一下改变把这些写入了dockerfile 加了几个RUN RUN rm -rf /var/cache/apk RUN mkdir -p /var/cache/apk RUN apk update -v 发现还…

mongodb分片集群搭建

1.本次搭建使用三台centos7主机搭建伪集群&#xff0c;关闭防火墙和selinux服务 2.mongodb架构相当于9个分片节点&#xff0c;3个路由节点&#xff0c;3个配置节点&#xff0c;主机信息如下图所示 主机名称主机ip地址端口服务A10.1.60.11420001&#xff0c;21001&#xff0c;…

Visual Studio 2019离线安装包获取和安装教程

摘要 介绍Visual Studio 2019离线安装方法和配置及注意事项 关键词 VS2019 离线安装 Visual Studio 2019版本与以往的2015、2013、2012版本不同&#xff0c;采用了新的模块化安装方法。微软官方也并未提供ISO镜像&#xff0c;根据官方提供的离线下载方案&#xff08;docs.mic…

JMeter开发web及手机APP自动化脚本练习

&#xff08;一&#xff09;开发web自动化脚本练习 一、打开浏览器代理服务器设置 我这里用的是360浏览器&#xff0c;打开浏览器代理服务器设置&#xff0c;端口要与jmeter中的端口设置保持一致哦。 二、JMeter设置代理 JMeter设置代理&#xff08;jmeter中的端口要与360浏览…

数据发送流程

在发送模式下&#xff0c;UART 的串行数据发送电路主要包括一个发送移位寄存器(TSR)&#xff0c;TSR 功能是将数据 逐个移位送出。待发数据必须先写到发送缓冲区中。 TXIFx 是发送中断标志位&#xff0c;可配置为发送缓冲区空或TSR 空。 数据的发送支持7bit 、8bit 或9bit 数据…

JAVA基础:Scanner类中next(), nextLine(), hasNext(), hasNextLine()

一、next() : 只读缓冲区中空格之前的数据,并且光标指向本行。二、nextLine() : 读取除回车以外的所有符号(整行内容)&#xff0c;光标定位在下一行三、hasNext() &#xff1a;检查下一个标记&#xff08;token&#xff09;&#xff0c;也就是以空格、制表符或换行符为分隔符的…
最新文章