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

数据结构与算法(七)--使用链表实现栈

一、前言

之前我们已经学习了链表的所有操作及其时间复杂度分析,我们可以了解到对于链表头的相关操作基本都是O(1)的,例如链表头增加、删除元素,查询元素等等那我们其实有一个数据结构其实可以完美利用到这些操作的特点,都是在某一段进行操作,那就是栈。本章我们通过链表去实现栈。并且比较用数组实现和用链表实现他们之间的差异。

二、用链表实现栈

2.1、代码实现

那么通过链表实现栈就很简单了,我们知道入栈和出栈都是从链表的同一端进行操作,那么我们只需调用链表的addFirst/removeFirst的方法即可,查找同理。
首先我们将链表栈命名为LinkedListStack,并且实现我们Stack的抽象类,然后设置一个内部属性为我们之前实现的链表,通过该链表完成实现需要重写的方法即可,代码如下:

public class LinkedListStack<T> implements Stack<T> {private LinkedList<T> linkedList;public LinkedListStack() {this.linkedList = new LinkedList<>();}@Overridepublic int getSize() {return linkedList.getSize();}@Overridepublic boolean isEmpty() {return linkedList.isEmpty();}@Overridepublic void push(T t) {linkedList.addFirst(t);}@Overridepublic T pop() {return linkedList.removeFirst();}@Overridepublic T peek() {return linkedList.getFirst();}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("Stack: top ");stringBuilder.append(linkedList);return stringBuilder.toString();}
}

测试一下:

public static void main(String[] args) {LinkedListStack<Integer> integerArrayStack = new LinkedListStack<>();for (int i = 0; i < 5; i++) {integerArrayStack.push(i);System.out.println(integerArrayStack);}integerArrayStack.pop();System.out.println(integerArrayStack);}

结果没有问题,通过链表实现栈就这样简单的实现了。
在这里插入图片描述

2.2、和数组栈比较性能

这个代码和之前数组队列和循环队列效率的对比很接近:

public class TestStackCompare {private static double testQueue(Stack<Integer> s, int opCount){long startTime = System.currentTimeMillis();Random random = new Random();for (int i = 0; i < opCount; i++) {s.push(random.nextInt(Integer.MAX_VALUE));}for (int i = 0; i < opCount; i++) {s.pop();}long endTime = System.currentTimeMillis();return (endTime - startTime)/1000.0;}public static void main(String[] args) {ArrayStack<Integer> integerArrayStack = new ArrayStack<>();LinkedListStack<Integer> integerLinkedListStack = new LinkedListStack<>();System.out.println("arrayStack,time:"+testQueue(integerArrayStack,1000000)+"s");System.out.println("linkedListStack,time:"+testQueue(integerLinkedListStack,1000000)+"s");}
}

那么我们运行下,发现两者效率近乎一致:
在这里插入图片描述
当然也有可能得到的结果是有差距的,对于arrayStack来说,时不时就需要扩容,这个对于某些操作系统来说比较耗费时间,而对于linkedListStack来说,它每次new Node就需要不断的开辟空间,这个操作又对于某些操作系统来说更耗费时间;而且这两者的差距会随着操作次数的增多不断拉大,因为扩容并不是每次扩容,而new Node确实是需要每次都new一个,例如我将操作次数放大为10000000次,这个时候两者的时间差距就比较大了:
在这里插入图片描述

所以仍然取决于你测试使用的操作系统,配置,jvm版本等等。但是其实我想强调的是,对于数组栈和链表栈来说,他们的各项操作的时间复杂度其实是一致的。他们之间没有复杂度之间的巨大差异。不像数组队列和循环队列,一个6s,一个0.01s,这之间的差距是非常大的。

相关文章:

数据结构与算法(七)--使用链表实现栈

一、前言 之前我们已经学习了链表的所有操作及其时间复杂度分析&#xff0c;我们可以了解到对于链表头的相关操作基本都是O(1)的&#xff0c;例如链表头增加、删除元素&#xff0c;查询元素等等。那我们其实有一个数据结构其实可以完美利用到这些操作的特点&#xff0c;都是在…...

分布式事务详解

摘要 分布式事务主要包括2pc、3pc、消息事务。 2pc指两阶段提交&#xff1a; 第一阶段是准备阶段&#xff1a;所有事务参与者检查执行能力并锁定对应资源&#xff0c;准备完成后将状态告知协调者。第二集段是提交状态&#xff1a;事务参与者全部准备好后&#xff0c;协调者发…...

车载通信架构 —— DDS协议介绍

车载通信架构 —— DDS协议介绍 我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 屏蔽力是信息过载时代一个人的特殊竞争力&#xff0c;任何消耗你的人和…...

nginx根据不同的客户端设备进行转发请求——筑梦之路

这里主要介绍七层负载方式实现。 环境说明&#xff1a; pc端 web-1 苹果ios端 web-2 安卓Android端 web-3 负载均衡 web-lb 配置示例&#xff1a; pc端&#xff1a; server {listen 9000; #监听9000server_name pc.xxx.com;charset utf-8;location / {root /…...

增强LLM:使用搜索引擎缓解大模型幻觉问题

论文题目&#xff1a;FRESHLLMS:REFRESHING LARGE LANGUAGE MODELS WITH SEARCH ENGINE AUGMENTATION 论文地址&#xff1a;https://arxiv.org/pdf/2310.03214.pdf 论文由Google、University of Massachusetts Amherst、OpenAI联合发布。 大部分大语言模型只会训练一次&#…...

WPF向Avalonia迁移(一、一些通用迁移项目)

通用变更 WPF&#xff1a;Visibility 其他参考文档 WPF&#xff1a; <TextBlock Visibility"Visible"/><TextBlock Visibility"Collapsed"/><TextBlock Visibility"Hidden"/>Avalonia &#xff1a; <TextBlock IsVisib…...

lua学习笔记

单行注释&#xff1a; 多行注释&#xff1a; 命名&#xff1a; Lua不支持下划线大写字母&#xff0c;比如&#xff1a;_ABC 但支持&#xff1a;_abc 关键字&#xff1a; 全局变量&#xff1a; 直接变量名 内容就是全局 局部变量&#xff1a; 加上local即可 nil&#xff1…...

修改 ModelScope 默认缓存路径

修改 ModelScope 默认缓存路径 设置 MODELSCOPE_CACHE 和 MODELSCOPE_MODULES_CACHE 两个环境变量。 export MODELSCOPE_CACHE<your_favourite_path>/hub export MODELSCOPE_MODULES_CACHE<your_favourite_path>/modelscope_modules完结&#xff01;...

【ES实战】索引别名的使用说明

索引别名 文章目录 索引别名带有过滤器的别名RoutingWrite Index REST单一添加一个别名示例: 索引创建是增加别名删除别名检索现有别名示例: 索引别名可以通过API的方式进行操作一个索引别名可以映射到一个或一个以上的索引索引名和索引别名不能重复&#xff0c;在集群中都是唯…...

QT信号与槽机制 和 常用控件介绍

QT信号与槽机制 1、信号(signal): 所谓信号槽 (观察者模式)信号本质是事件。信号展现方式就是函数。当某一个事件发生之后&#xff0c;则发出一个信号(signal). 2、槽(slot): 就是对信号响应的函数&#xff0c;槽就是一个函数。槽函数与普通函数区别槽函数可以与一个信号关联&…...

【css-banner图片自适应】

<picture><source media"(max-width: 480px)" srcset"图片地址"><source media"(min-width: 481px)" srcset"图片地址"><img src"图片地址" id"homebanner"></picture>img{height:…...

【k8s管理操作】

k8s管理操作 一、k8s管理操作1.陈述式资源管理2.声明式资源管理 二、k8s基础信息常看&#xff08;命令&#xff09;增删改查项目的生命周期&#xff1a;创建-->发布-->更新-->回滚-->删除 headless clusterIP 无头模式 金丝雀发布&#xff08;Canary Release&#…...

【java基础学习】之DOS命令

#java基础学习 1.常用的DOS命令&#xff1a; dir:列出当前目录下的文件以及文件夹 md: 创建目录 rd:删除目录cd:进入指定目录 cd.. :退回到上级目录 cd\ : 退回到根目录 del:删除文件 exit:退出dos命令行 1.dir:列出当前目录下的文件以及文件夹 2.md: 创建目录 …...

学习记录——StyleGAN2+SA-UNet

SA-UNet for Retinal Vessel improvment using StyleGAN2 作者提出了一种改进视网膜图像分割的方法,通过创建图像及其相应的分割地图来实现。作者的解决方案包括使用DRIVE数据集1对StylGAN2进行训练,并使用目前在分割DRIVE图像方面取得最先进结果的SA-UNet模型对新合成的图像…...

JVM222

文章目录 JVM222运行时数据区的内部结构线程程序计数器&#xff08;PC寄存器&#xff09;虚拟机栈 JVM222 运行时数据区的内部结构 概述 本节主要讲的是运行时数据区&#xff0c;也就是下图这部分&#xff0c;它是在类加载器加载完成后的阶段&#xff0c;如下图&#xff1a; …...

C语言 指针

含义 从根本上看&#xff0c;指针是一个值为内存地址的变量&#xff08;或数据对象&#xff09;。指针变量的值是地址。 要创建指针变量&#xff0c;先要声明指针变量的类型 作用 1.实现复杂的数据结构&#xff0c;例如数组、链表、队列和堆栈等&#xff1b; 2.能方便地表…...

YOLOv8血细胞检测(7):小目标大目标一网打尽,轻骨干重Neck的轻量级GFPN | 阿里ICLR2022 GiraffeDet

💡💡💡本文改进:小目标大目标一网打尽GFPN,提升大小目标检测性能 GFPN | 亲测在血细胞检测项目中涨点,map@0.5 从原始0.895提升至0.904 收录专栏: 💡💡💡YOLO医学影像检测:http://t.csdnimg.cn/N4zBP ✨✨✨实战医学影像检测项目,通过创新点验证涨点可…...

广度优先(BFS)(例子:迷宫)

广度优先搜索算法&#xff08;BFS&#xff09;是一种用于图形和树数据结构的搜索算法。该算法从根节点开始搜索&#xff0c;然后依次访问每个相邻节点。在搜索过程中&#xff0c;每个节点都标记为已访问&#xff0c;以避免重复访问。BFS算法适用于寻找最短路径的问题&#xff0…...

【安卓源码】安卓Watchdog 机制

在Android系统中&#xff0c;也设计了一个软件层面Watchdog&#xff0c;用于保护一些重要的系统服务&#xff0c;比如&#xff1a;AMS、WMS、PMS等&#xff0c;由于以上核心服务运行在system_server进程里面&#xff0c;所以当以上服务出现异常时&#xff0c;通常会将system_se…...

inscode连接不上gpu,持续8小时,为了数据不丢失续费了6小时,我只想知道什么时候可以连接

并且给我相应的补偿...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...