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

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

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

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

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

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...