栈及其栈的模拟实现和使用
1. 栈(Stack)
1.1 概念
栈 :一种特殊的线性表,其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO ( Last In First Out )的原则。压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 。出栈:栈的删除操作叫做出栈。 出数据在栈顶 。

1.2 栈的使用
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈,并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
1.3 栈的模拟实现
栈和ArrayList类似,都是动态的顺序表 ,我们用数组来实现。
首先,我们自己创建一个类MyStack,里面定义一个数组成员变量,用来模拟实现栈 ,代码:
public class MyStack implements IStack{private int[] elem;private int usedSize; //数组中元素的个数private static final int DEFAULT_CAPACITY = 10; //默认数组大小public MyStack() {elem = new int[DEFAULT_CAPACITY];}
}
对于栈的实现:入栈操作
在入栈的时候,要先判断数组是否已满,如果满,则对数组进行扩容;不满,则直接在数组的最后加入元素。
public void push(int x) {if (full()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize]=x;usedSize++;}public boolean full() {if (usedSize == elem.length) {return true;}return false;}
对于栈的实现:出栈操作
在出栈的时候,首先判断一下栈是否为空,为空的话抛出EmptyException异常,实现栈是否为空,代码:
public boolean empty() {//栈为空,也就是数组里面没有元素return usedSize == 0;}
出栈操作:
public int pop() {if(empty()) {throw new EmptyException("栈为空!"); //自定义异常}int old = elem[usedSize-1];usedSize--; //相当于删除return old;}
自定义异常:
public class EmptyException extends RuntimeException{public EmptyException(String msg) {super(msg);}
}
对栈的实现:peek()操作
peek()操作是查看栈顶元素的值,若栈为空,则抛出EmptyException异常;不空,直接返回数组最后一个元素的值即可。
public int peek() {if(empty()) {throw new EmptyException("栈为空!");}return elem[usedSize-1];}
对栈的实现:栈的大小
栈的大小,直接返回数组元素的个数即可。
public int size() {return usedSize;}
1.4 栈的应用场景
1. 改变元素的序列
1. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是(C)A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,12. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈,然后再依次出栈,则元素出栈的顺序是(B )。A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA
2. 将递归转化为循环
比如:逆序打印链表
// 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}
// 循环方式
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}
相关文章:
栈及其栈的模拟实现和使用
1. 栈(Stack) 1.1 概念 栈 :一种特殊的线性表,其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO ( Last In First Out )的原则…...
HarmonyOS开发:开源一个刷新加载组件
前言 系统Api中提供了下拉刷新组件Refresh,使用起来也是非常的好用,但是风格和日常的开发,有着巨大的出入,效果如下: 显然上面的效果是很难满足我们实际的需求的,奈何也没有提供的属性可以更改,…...
XSSFWorkbook读取模板,批量填充并导出文件
1、pom文件导入 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.0</version> </dependency> <dependency><groupId>org.apache.poi</groupId><artifactId>…...
Lazada新店运营秘籍自养号测评技术
跨境行业的前途虽然大好,但要想真正从中分一杯羹并非易事。东南亚市场前景大好,而作为其主流在线购物网站之一,Lazada吸引了众多卖家和买家。作为新手来说,注册好Lazada之后,店铺下一步该怎么做呢?赶紧来看…...
python:逐像素处理遥感数据时间序列数据(求时间序列最大值、最大值所对应的索引、最大值所在的时间)
作者:CSDN @ _养乐多_ 本文记录了使用gdal、ras、numpy 库实现遥感时间序列数据逐像素处理的代码。并以求NADVI时间序列最大值为例。代码可扩展到其他多种对时间序列的处理,比如MK趋势分析,求时间序列中值、众数、标准差、和,时间序列拟合、异常检测、机器学习预测等多种应…...
SpringCloudGateway--过滤器(自定义filter)
目录 一、概览 二、通过GatewayFilter实现 三、继承AbstractGatewayFilterFactory 一、概览 当使用Spring Cloud Gateway构建API网关时,可以利用Spring Cloud Gateway提供的内置过滤器(filter)来实现对请求的处理和响应的处理。过滤器可以…...
【docker】安装 showdoc
1. 下载镜像 2.新建存放showdoc数据的目录 3.启动showdoc容器 4.打开网页 1. 下载镜像 # 原版官方镜像安装命令(中国大陆用户不建议直接使用原版镜像,可以用后面的加速镜像) docker pull star7th/showdoc # 中国大陆镜像安装命令(安装后记得执行docke…...
智慧公厕:科技赋予公共卫生新生命,提升城市管理品质
在现代化城市中,公共卫生设施的发展与提升一直是对城市管理者和市民的共同期望。然而,传统的公共厕所常常令人困扰,脏乱臭成为难题。为了解决这一难题,广州中期科技科技有限公司全新升级的智慧公厕整体解决方案,补誉为…...
深度学习_2 数据操作之数据预处理
数据操作 机器学习包括的核心组件有: 可以用来学习的数据(data);如何转换数据的模型(model);一个目标函数(objective function),用来量化模型的有效性&…...
在美团和阿里6年,很难却也真实...
先简单的说下,本人6年工作经验,曾就职于某大型国企,公司研究院成员,也就职过美团担任高级测试开发工程师,有丰富的高并发大型项目经验。 后端高并发、高性能、高可用性开发,自动化测试框架开发以及软件自动…...
2、NLP文本预处理技术:词干提取和词形还原
一、说明 在上一篇文章中,我们解释了文本预处理的重要性,并解释了一些文本预处理技术。在本文中,我们将介绍词干提取和词形还原主题。 词干提取和词形还原是两种文本预处理技术,用于将单词还原为其基本形式或词根形式。这些技术的…...
Fabric官方示例测试网络搭建
目录 一、参考文档二、环境依赖三、Fabric源码安装3.1、创建链目录3.2、下载源码3.3、修改安装脚本3.4、开始安装3.4.1、执行安装脚本3.4.2、手动下载ca和二进制配置包 四、启动测试网络五、使用测试网络5.1、创建应用通道5.2、部署链码5.3、发送交易 六、关闭测试网络 一、参考…...
ubuntu20.04 conda pack 打包虚拟环境,直接将其用到其他终端
在本机ubuntu20.04下配置的虚拟环境,想到将其整个放到新建的docker(ubuntu20.04)下使用,操作步骤如下: # 一、在ubuntu1下打包虚拟环境 # 安装conda-pack pip install conda-pack# 进入需要打包的虚拟环境,这里将目标虚拟环境名称为goal_env…...
云原生-AWS EC2使用、安全性及国内厂商对比
目录 什么是EC2启动一个EC2实例连接一个实例控制台ssh Security groups规则默认安全组与自定义安全组 安全性操作系统安全密钥泄漏部署应用安全元数据造成SSRF漏洞出现时敏感信息泄漏网络设置错误 厂商对比参考 本文通过实操,介绍了EC2的基本使用,并在功…...
【Proteus仿真】【Arduino单片机】简易电子琴
文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器,使用无源蜂鸣器、按键等。 主要功能: 系统运行后,按下K1-K7键发出不同音调。 二、软件设计 /* 作者:嗨小易&a…...
QT5.15.2 for Android 真机调试
一、准备就绪 1、一台安卓手机 1)手机需要进入开发者选项 2)准备一根USB线,需要用usb线连接电脑 2、QT5需要 Android搭建好环境(教程可以访问我另一篇文章) 二、调试 1、用usb线连接好电脑并进入开发者选项&…...
Mysql my.cnf配置文件参数详解
Linux 操作系统中 MySQL 的配置文件是 my.cnf,一般会放在 /etc/my.cnf 或 /etc/mysql/my.cnf 目录下。 如果你使用 rpm 包安装 MySQL 找不到 my.cnf 文件,可参考如下: 第一步: 通过cd命令 cd /usr/share/mysql 来到这个目录&#…...
linux下构建rocketmq-dashboard多架构镜像——筑梦之路
接上篇:linux上构建任意版本的rocketmq多架构x86 arm镜像——筑梦之路-CSDN博客 这里来记录下构建rocketmq-dashboard多架构镜像的方法步骤。 当前rocketmq-dashboard只有一个版本,源码地址如下: https://dist.apache.org/repos/dist/rele…...
git,ssh,sourcetree代码管理
安装Git并建立与GitHub的ssh连接 1、安装git,设置git的用户信息(需要通过用户信息来显示你是谁) 2、配置SSH, 因为本地Git仓库和GitHub仓库之间的传输是通过SSH加密传输的,GitHub需要识别是否是你推送,Git…...
Jenkins中解决下载maven包巨慢的问题
背景介绍 我们在使用jenkins构建maven项目时由于依赖很多第三方jar包,默认会从maven中央仓库下载,由于maven中央仓库服务器是国外的,所以下载很慢,甚至会超时 解决办法 增加jenkins maven 源配置 如下图所示,增加m…...
用VNA实测滤波器群时延:手把手教你避开IQ信号失真的坑(附校准技巧)
射频滤波器群时延实战:VNA测量技巧与IQ信号保真解决方案 在无线通信系统设计中,滤波器的群时延特性往往是被忽视的关键参数。许多工程师在评估滤波器性能时,主要关注插入损耗、带外抑制等传统指标,却忽略了群时延波动可能导致的信…...
探索拖火车混合A星路径规划算法
拖火车混合a星路径规划算法 在路径规划领域,各种算法层出不穷,今天咱就唠唠拖火车混合A星路径规划算法。这算法融合了传统A星算法的优势,并针对特定场景进行了创新,就像是给A星算法穿上了特制的“战衣”,以应对更复杂…...
EasyPreferences:ESP32类型安全的嵌入式配置管理库
1. EasyPreferences 库概述EasyPreferences 是专为 ESP32 平台设计的轻量级、类型安全的非易失性配置管理库。它并非对 ESP-IDFnvs_flash或 Arduino-ESP32PreferencesAPI 的简单封装,而是构建在其之上的抽象管理层,核心目标是解决嵌入式系统中长期存在的…...
OpenClaw技能市场巡礼:Phi-3-mini-128k-instruct适配的十大实用工具
OpenClaw技能市场巡礼:Phi-3-mini-128k-instruct适配的十大实用工具 1. 为什么需要技能市场? 当我第一次接触OpenClaw时,最让我惊喜的不是它能够操控鼠标键盘的能力,而是它背后那个充满可能性的技能市场。作为一个长期与命令行打…...
openclaw连接飞书操作表格
01意义 将智能助手从电脑网页端连接到手机飞书,从此无需守在电脑前,用手机就能随时指挥它干活。未来,飞书中需要手动操作的任务,都可以交由 AI 智能助手来完成。它还能帮你构建企业知识库,随着飞书终端 CLI 能力的增强…...
linux下的pwm子系统
概念:PWM的概念就不多说了,pwm子系统如下:设备树:rk3568设备树pwm控制器里面已经配置了时钟,所以只需要使能节点就好了/* 使能 PWM12 节点 配置使用指定的引脚 状态设置为正常工作 */&pwm12 {status "okay";pinctrl-0 <&pwm12m1_…...
收藏备用!小白程序员必看,大模型核心原理拆解(通俗易懂版)
本文专为CSDN小白程序员、AI入门者打造,用“技术拆解通俗类比”的方式,深入解析大模型的核心原理,避开专业术语壁垒。明确大模型的AI分支定位,拆解其三大底层逻辑,补充微调、提示工程的实操要点,澄清新手常…...
RexUniNLU部署教程:Kubernetes集群中水平扩缩容RexUniNLU服务的Helm Chart实践
RexUniNLU部署教程:Kubernetes集群中水平扩缩容RexUniNLU服务的Helm Chart实践 1. 为什么需要在K8s中部署RexUniNLU? 你可能已经试过在本地跑通 python test.py,也成功启动了 server.py 提供的 FastAPI 接口。但当真实业务流量进来——比如…...
cv_unet_image-colorization多分辨率适配实测:手机扫描件/胶片扫描图效果对比
cv_unet_image-colorization多分辨率适配实测:手机扫描件/胶片扫描图效果对比 1. 项目背景与技术原理 基于UNet架构深度学习模型开发的本地化图像上色工具,采用了阿里魔搭开源的图像上色算法。这个工具能够智能识别黑白图像中的物体特征、自然场景和人…...
科技企业如何利用智能手段提升研发效率?
观点作者:科易网-国家科技成果转化(厦门)示范基地 现状概述:传统研发模式的瓶颈与挑战 在全球科技创新加速迭代的背景下,科技企业面临的核心挑战之一是如何提升研发效率。传统研发模式往往存在以下痛点: 信…...
