当前位置: 首页 > 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小时,我只想知道什么时候可以连接

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

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...