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

kotlin实现ArrayDeque

Deque双端队列,一直在使用,却从未了解过源码。
内部逻辑其实很简单

  1. 可扩容数组
  2. 循环队列,循环栈
  3. 扩容倍数1.5,size=size+(size shr 1)
  4. 只从两端存取元素
fun main() {val deque = MyArrayDeque()repeat(16) {deque.addLast(it)}while (deque.isNotEmpty()) {println(deque.removeLast())}}class MyArrayDeque {// 存元素,不能存null,初始容量为16,避免频繁扩容,一次扩容1.5倍private var arr = arrayOfNulls<Int>(16)// 头尾节点,tail一直为nullprivate var head: Int = 0private var tail: Int = 0// 实际容量private var size: Int = 0fun addFirst(value: Int) {// 扩容grow()head = dec(head)arr[head] = valuesize++}fun addLast(value: Int) {// 扩容grow()arr[tail] = valuetail = inc(tail)size++}fun removeFirst(): Int {if (isEmpty()) {return -1}val res = arr[head]!!head = inc(head)size--return res}fun removeLast(): Int {if (isEmpty()) {return -1}tail = dec(tail)size--return arr[tail]!!}// 加一fun inc(i: Int) = if (i == arr.lastIndex) 0 else i + 1// 减一fun dec(i: Int) = if (i == 0) arr.lastIndex else i - 1// 扩容,内部不一定扩容private fun grow() {// 至少还有一个容量if (size < arr.size - 1) {return}// 一次扩容1.5倍val newArr = arrayOfNulls<Int>(arr.size + (arr.size shr 1))// 从0开始if (head < tail) {for (i in head..<tail) {newArr[i - head] = arr[i]}} else {// 临时下标var index = 0// 现存头部for (i in head..arr.lastIndex) {newArr[index++] = arr[i]}// 尾部移动后面for (i in 0..<tail) {newArr[index++] = arr[i]}}// 扩容后,head和tail重新计算arr = newArrhead = 0tail = size}fun size() = sizefun isEmpty() = size() == 0fun isNotEmpty() = size() > 0override fun toString(): String {if (size == 0) {return ""}val sb = StringBuilder()if (head < tail) {for (i in head..<tail) {if (sb.isNotEmpty()) {sb.append(", ")}sb.append(arr[i])}} else {for (i in head..arr.lastIndex) {if (sb.isNotEmpty()) {sb.append(", ")}sb.append(arr[i])}for (i in 0..<tail) {// 此时一定有至少一个元素,不用判断sb.append(", ").append(arr[i])}}return sb.toString()}
}

相关文章:

kotlin实现ArrayDeque

Deque双端队列&#xff0c;一直在使用&#xff0c;却从未了解过源码。 内部逻辑其实很简单 可扩容数组循环队列&#xff0c;循环栈扩容倍数1.5&#xff0c;sizesize(size shr 1)只从两端存取元素 fun main() {val deque MyArrayDeque()repeat(16) {deque.addLast(it)}while …...

java时间格式化

1&#xff0c;CST时间格式化&#xff0c;这个一般是返回值的类型为 Date 类型&#xff0c;如果不做处理&#xff0c;返给前端的就是时间戳&#xff0c;当然也可以更改返回值类型为 String&#xff0c;这样就不用处理了。方法如下&#xff1a; /*** 格式化时间* param date Thu…...

ArduPilot开源飞控之AP_Baro_SITL

ArduPilot开源飞控之AP_Baro_SITL 1. 源由2. back-end抽象类3. 方法实现3.1 AP_Baro_SITL3.2 _timer3.3 temperature_adjustment3.4 wind_pressure_correction3.5 update 4. 参考资料 1. 源由 鉴于ArduPilot开源飞控之AP_Baro中涉及Sensor Driver有以下总线类型&#xff1a; …...

基于Java的病人跟踪治疗管理系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...

RCD吸收电路的工作原理及参数计算方法详解

在电子电力技术和自动化控制领域内&#xff0c;RCD吸收电路非常重要&#xff0c;它的作用是吸收瞬间过电压和过电路免受电压波动的影响&#xff0c;因此被广泛应用在各种设备及系统中&#xff0c;今天凡亿将带领小伙伴们来了解下RCD吸收电路的工作原理及计算方法。 1、RCD吸收电…...

leetcode做题笔记169. 多数元素

给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3] 输出&#xff1a;3 示例 …...

FATFS f_printf 如何支持写入浮点数据。

参考原子和网上的移植最新的fatfs系统后,挂载打开文件始终返回13错误代码,在自己的项目中移植最新的fatfs0.15版本解决问题,使用f_printf能成功进行浮点数据写入了 参考的文章如下: https://zhuanlan.zhihu.com/p/444427537 问题描述 在使用fatfs的f_printf向文件.csv中写入…...

postman忘记密码提交没响应

现象&#xff1a;通过客户端进到账户页面一直无响应&#xff0c;可copy the url 到浏览器进入页面&#xff0c;使用浏览器提交几次还是没响应。 实测有用方法&#xff1a; 1、通过手机进入官网 https://www.getpostman.com &#xff0c;找到忘记密码入口。 2、多提交几次后&…...

初学vue,想自己找个中长期小型项目练练手,应该做什么?

前言 可以试着做一两个完整的后台管理项目后再去做其他的&#xff0c;下面推荐一些github上的vue后台管理的项目&#xff0c;可以自己选择性的练一下手 Vue2 1、iview-admin Star: 16.4k 基于 iview组件库开发的一款后台管理系统框架&#xff0c;提供了一系列的强大组件和基…...

【牛客面试必刷TOP101】Day11.BM63 跳台阶和 BM67 不同路径的数目(一)

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;牛客面试必刷TOP101 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01;&#xff01;&…...

[NOIP 2022] 建造军营 题解

题目 P1 边双缩点 观察样例二&#xff0c;可以发现边双内的边可选可不选。由此考虑边双缩点&#xff0c;Tarjan 找桥即可&#xff0c;缩点后变成一棵树。 P2 设计状态 用最终合法答案形态截这颗树&#xff0c;设计 f u f_u fu​ 表示 u u u 子树内非空&#xff0c;且子树…...

射频识别技术(RFID)在智能制造模具管理中的应用

背景介绍 模具是工业生产的核心装备&#xff0c;被誉为“工业之母”&#xff0c;广泛应用于机械、汽车、轻工、电子、化工、冶金、建材等各个行业&#xff0c;是制造加工企业的重要资产&#xff0c;然而&#xff0c;传统的人工纸质记录方式已无法满足模具管理的需求&#xff0…...

奖品定制经营商城小程序的作用是什么

奖品是激励人员团体很好的方式&#xff0c;也是荣誉象征&#xff0c;奖牌、奖杯、高端礼盒等&#xff0c;同时市场中团体非常多&#xff0c;其需求也是很多&#xff0c;尤其定制方面&#xff0c;就更是不用说。 对奖品定制企业来说&#xff0c;除了线下门店获客经营外&#xf…...

深度学习常用脚本总结

&#x1f468;‍&#x1f4bb;个人简介&#xff1a; 深度学习图像领域工作者 &#x1f389;工作总结链接&#xff1a;https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结&#xff0c;每个链接都是一些常用demo&#xff0c…...

hive数据表创建

目录 分隔符 分区表 二级分区 分桶表 外部表 分隔符 CREATE TABLE emp( userid bigint, emp_name array<string>, emp_date map<string,date>, other_info struct<deptname:string, gender:string>) ROW FORMAT DELIMITED FIELDS TERMINATED BY \t COL…...

查看本机Arp缓存,以及清除arp缓存

查看Arp缓存目录 Windows 系统使用 winR&#xff0c;输入cmd 在命令窗口输入 arp -a 删除Arp缓存目录 在命令窗口输入 arp -d * 查看主机路由表...

Unity MRTK Hololens2眼动交互

/** ** UnityVersion : 2021.3.6f1* Description : 眼部交互基类* Author: * CreateTime : 2023-10-11 09:43:20* Version : V1.0.0* * */using System.Collections.Generic; using Microsoft.MixedReality.Toolkit.Input; using UnityEngine;namespace MRTKExtend.EyeTrackin…...

接口自动化测试 —— 协议、请求流程

一、架构 CRM客户关系管理系统 SAAS Software As A Service 软件即服务 PAAS Platform AS A Service 平台即服务 快速交付→ 快&#xff1a;自己去干、有结果、事事有回音、持续改进 单体架构——》垂直架构——》面向服务架构——》微服务架构&#xff08;分布式&#xf…...

JDK安装详细教程

JDK安装详细教程 国内大多数使用的是1.8的版本&#xff0c;对于初学者来说这个版本很友善&#xff0c;不过由于我安装过了1.8&#xff0c;所以我这里演示JDK21 的安装&#xff0c;过程并无区别&#xff0c;只在下载时注意选择1.8版本。1.8就是JDK8. 文章目录 JDK安装详细教程一…...

vulnhub_Fowsniff靶机渗透测试

Fowsniff靶机 靶机地址&#xff1a;https://www.vulnhub.com/entry/fowsniff-1,262/ 文章目录 Fowsniff靶机信息收集web渗透密码碰撞POP3邮件服务器渗透获取权限权限提升靶机总结 信息收集 通过nmap扫描&#xff0c;靶机开放22 80 110 143端口&#xff0c;110是pop3邮件服务…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...