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

栈及其栈的模拟实现和使用

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,1
2. 一个栈的初始状态为空。现将元素 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 概念 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO &#xff08; Last In First Out &#xff09;的原则…...

HarmonyOS开发:开源一个刷新加载组件

前言 系统Api中提供了下拉刷新组件Refresh&#xff0c;使用起来也是非常的好用&#xff0c;但是风格和日常的开发&#xff0c;有着巨大的出入&#xff0c;效果如下&#xff1a; 显然上面的效果是很难满足我们实际的需求的&#xff0c;奈何也没有提供的属性可以更改&#xff0c;…...

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新店运营秘籍自养号测评技术

跨境行业的前途虽然大好&#xff0c;但要想真正从中分一杯羹并非易事。东南亚市场前景大好&#xff0c;而作为其主流在线购物网站之一&#xff0c;Lazada吸引了众多卖家和买家。作为新手来说&#xff0c;注册好Lazada之后&#xff0c;店铺下一步该怎么做呢&#xff1f;赶紧来看…...

python:逐像素处理遥感数据时间序列数据(求时间序列最大值、最大值所对应的索引、最大值所在的时间)

作者:CSDN @ _养乐多_ 本文记录了使用gdal、ras、numpy 库实现遥感时间序列数据逐像素处理的代码。并以求NADVI时间序列最大值为例。代码可扩展到其他多种对时间序列的处理,比如MK趋势分析,求时间序列中值、众数、标准差、和,时间序列拟合、异常检测、机器学习预测等多种应…...

SpringCloudGateway--过滤器(自定义filter)

目录 一、概览 二、通过GatewayFilter实现 三、继承AbstractGatewayFilterFactory 一、概览 当使用Spring Cloud Gateway构建API网关时&#xff0c;可以利用Spring Cloud Gateway提供的内置过滤器&#xff08;filter&#xff09;来实现对请求的处理和响应的处理。过滤器可以…...

【docker】安装 showdoc

1. 下载镜像 2.新建存放showdoc数据的目录 3.启动showdoc容器 4.打开网页 1. 下载镜像 # 原版官方镜像安装命令(中国大陆用户不建议直接使用原版镜像&#xff0c;可以用后面的加速镜像) docker pull star7th/showdoc # 中国大陆镜像安装命令&#xff08;安装后记得执行docke…...

智慧公厕:科技赋予公共卫生新生命,提升城市管理品质

在现代化城市中&#xff0c;公共卫生设施的发展与提升一直是对城市管理者和市民的共同期望。然而&#xff0c;传统的公共厕所常常令人困扰&#xff0c;脏乱臭成为难题。为了解决这一难题&#xff0c;广州中期科技科技有限公司全新升级的智慧公厕整体解决方案&#xff0c;补誉为…...

深度学习_2 数据操作之数据预处理

数据操作 机器学习包括的核心组件有&#xff1a; 可以用来学习的数据&#xff08;data&#xff09;&#xff1b;如何转换数据的模型&#xff08;model&#xff09;&#xff1b;一个目标函数&#xff08;objective function&#xff09;&#xff0c;用来量化模型的有效性&…...

在美团和阿里6年,很难却也真实...

先简单的说下&#xff0c;本人6年工作经验&#xff0c;曾就职于某大型国企&#xff0c;公司研究院成员&#xff0c;也就职过美团担任高级测试开发工程师&#xff0c;有丰富的高并发大型项目经验。 后端高并发、高性能、高可用性开发&#xff0c;自动化测试框架开发以及软件自动…...

2、NLP文本预处理技术:词干提取和词形还原

一、说明 在上一篇文章中&#xff0c;我们解释了文本预处理的重要性&#xff0c;并解释了一些文本预处理技术。在本文中&#xff0c;我们将介绍词干提取和词形还原主题。 词干提取和词形还原是两种文本预处理技术&#xff0c;用于将单词还原为其基本形式或词根形式。这些技术的…...

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下配置的虚拟环境&#xff0c;想到将其整个放到新建的docker(ubuntu20.04)下使用&#xff0c;操作步骤如下&#xff1a; # 一、在ubuntu1下打包虚拟环境 # 安装conda-pack pip install conda-pack# 进入需要打包的虚拟环境,这里将目标虚拟环境名称为goal_env…...

云原生-AWS EC2使用、安全性及国内厂商对比

目录 什么是EC2启动一个EC2实例连接一个实例控制台ssh Security groups规则默认安全组与自定义安全组 安全性操作系统安全密钥泄漏部署应用安全元数据造成SSRF漏洞出现时敏感信息泄漏网络设置错误 厂商对比参考 本文通过实操&#xff0c;介绍了EC2的基本使用&#xff0c;并在功…...

【Proteus仿真】【Arduino单片机】简易电子琴

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用无源蜂鸣器、按键等。 主要功能&#xff1a; 系统运行后&#xff0c;按下K1-K7键发出不同音调。 二、软件设计 /* 作者&#xff1a;嗨小易&a…...

QT5.15.2 for Android 真机调试

一、准备就绪 1、一台安卓手机 1&#xff09;手机需要进入开发者选项 2&#xff09;准备一根USB线&#xff0c;需要用usb线连接电脑 2、QT5需要 Android搭建好环境&#xff08;教程可以访问我另一篇文章&#xff09; 二、调试 1、用usb线连接好电脑并进入开发者选项&…...

Mysql my.cnf配置文件参数详解

Linux 操作系统中 MySQL 的配置文件是 my.cnf&#xff0c;一般会放在 /etc/my.cnf 或 /etc/mysql/my.cnf 目录下。 如果你使用 rpm 包安装 MySQL 找不到 my.cnf 文件&#xff0c;可参考如下&#xff1a; 第一步&#xff1a; 通过cd命令 cd /usr/share/mysql 来到这个目录&#…...

linux下构建rocketmq-dashboard多架构镜像——筑梦之路

接上篇&#xff1a;linux上构建任意版本的rocketmq多架构x86 arm镜像——筑梦之路-CSDN博客 这里来记录下构建rocketmq-dashboard多架构镜像的方法步骤。 当前rocketmq-dashboard只有一个版本&#xff0c;源码地址如下&#xff1a; https://dist.apache.org/repos/dist/rele…...

git,ssh,sourcetree代码管理

安装Git并建立与GitHub的ssh连接 1、安装git&#xff0c;设置git的用户信息&#xff08;需要通过用户信息来显示你是谁&#xff09; 2、配置SSH&#xff0c; 因为本地Git仓库和GitHub仓库之间的传输是通过SSH加密传输的&#xff0c;GitHub需要识别是否是你推送&#xff0c;Git…...

Jenkins中解决下载maven包巨慢的问题

背景介绍 我们在使用jenkins构建maven项目时由于依赖很多第三方jar包&#xff0c;默认会从maven中央仓库下载&#xff0c;由于maven中央仓库服务器是国外的&#xff0c;所以下载很慢&#xff0c;甚至会超时 解决办法 增加jenkins maven 源配置 如下图所示&#xff0c;增加m…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

PHP和Node.js哪个更爽?

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

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...