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

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 + " ");}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/177546.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

初识FFmpeg

前言 无意间见到群里的小伙伴展示视频工具。功能比较多&#xff0c;包括视频编码修改&#xff0c;画质处理&#xff0c;比例处理、名称提取&#xff0c;剪辑、标题拆解。因此开始了FFmpeg学习。以下摘自百度百科的解释。 FFmpeg是一套可以用来记录、转换数字音频、视频&#xf…

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

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

视频平台跨网级联视频压缩解决方案

一、 简介 视频监控领域对带宽有着较大的需求&#xff0c;这是因为视频流需要实时占用网络带宽资源。视频监控的传输带宽是组网结构的基础保障&#xff0c;关系到视频监控的稳定性、可靠性和可拓展性等因素。例如&#xff0c;720P的视频格式每路摄像头的比特率为2Mbps&#xff…

【机器学习合集】模型设计之网络宽度和深度设计 ->(个人学习记录笔记)

文章目录 网络宽度和深度设计1. 什么是网络深度1.1 为什么需要更深的模型浅层学习的缺陷深度网络更好拟合特征学习更加简单 2. 基于深度的模型设计2.1 AlexNet2.2 AlexNet工程技巧2.3 VGGNet 3. 什么是网络宽度3.1 为什么需要足够的宽度 4. 基于宽度模型的设计4.1 经典模型的宽…

在IDEA运行spark程序(搭建Spark开发环境)

建议大家写在Linux上搭建好Hadoop的完全分布式集群环境和Spark集群环境&#xff0c;以下在IDEA中搭建的环境仅仅是在window系统上进行spark程序的开发学习&#xff0c;在window系统上可以不用安装hadoop和spark&#xff0c;spark程序可以通过pom.xml的文件配置&#xff0c;添加…

【洛谷算法题】P5710-数的性质【入门2分支结构】

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5710-数的性质【入门2分支结构】&#x1f30f;题目描述&#x1f30f;输入格式&a…

开源库存管理系统InvenTree的安装

本文是应网友 shijie880500 要求折腾的&#xff1b; 什么是 InvenTree &#xff1f; InvenTree 是一个开源的库存管理系统&#xff0c;提供强大的低级别库存控制和零件跟踪。InvenTree 系统的核心是 Python/Django 数据库后端&#xff0c;它提供了一个管理界面&#xff08;基于…

绝缘检测原理和绝缘电阻计算方法

文章目录 简介绝缘检测功能绝缘检测原理绝缘电阻检测的常用方法不平衡电桥法 绝缘电阻绝缘电阻的计算 绝缘检测开启或关闭为什么根据 V1 &#xff1c; V2 或 V1 ≥ V2 判断是上桥臂并入电阻还是下桥臂并入电阻 简介 绝缘检测是判断动力&#xff08;正、负&#xff09;总线与外…

Flutter三棵树的创建流程

一、Flutter常见的家族成员 Widget常见的家族成员 Element常见的家族成员 Render常见的家族成员 二、示例代码对应的Flutter Inspector树 示例代码&#xff1a;MyApp->MyHomePage->ErrorWidget&#xff0c;包含了StatelessWidget、StatefulWidget、LeafRenderObjectWid…

位运算与简单应用

一.位运算的基本概念&#xff1a; 首先&#xff0c;位运算是针对二进制的&#xff0c;(数字本来int,4字节,下面假设为1字节)。比如数字12&#xff0c;它的二进制本来是&#xff1a; 0000 0000 0000 0000 0000 0000 0000 1100 因为前面的数字大都是0&#xff0c;所以为了简写…

火影忍者游戏攻略大公开!成为忍者大师的秘诀揭秘

大家好&#xff01;作为火影忍者游戏的玩家&#xff0c;我们都希望能够在游戏中成为优秀的忍者大师&#xff0c;战胜强大的对手。为了帮助大家实现这一目标&#xff0c;我想分享一些实用的攻略和技巧。 首先&#xff0c;熟悉忍者技能是成为忍者大师的基础。在火影忍者游戏中&am…

C语言_自定义类型详解

文章目录 前言一.结构体的声明1.1结构体的基础知识1.2结构的声明1.3特殊声明1.4结构体的自引用在结构中包含一个类型为该结构本身的成员是否可以&#xff1f;正确的自引用方式匿名结构体类型和typedef的结合形式 1.5 结构体变量的定义和初始化结构体定义与初始化结构体里嵌套结…

【Linux进程】再谈软件—操作系统(Operator System)

目录 操作系统(Operator System) 概念 设计OS的目的 如何理解 "管理"——先描述再组织 系统调用和库函数概念 总结 操作系统(Operator System) 概念 任何计算机系统都包含一个基本的程序集合&#xff0c;称为操作系统(OS)。 笼统的理解&#xff0c;操作系统…

【python】路径管理+路径拼接问题

路径管理 问题相对路径问题绝对路径问题 解决os库pathlib库最终解决 问题 环境&#xff1a;python3.7.16 win10 相对路径问题 因为python的执行特殊性&#xff0c;使用相对路径时&#xff0c;在不同路径下用python指令会有不同的索引效果&#xff08;python的项目根目录根据执…

利用Graviton2和S3免费套餐搭建私人网盘

网盘是一种在线存储服务&#xff0c;提供文件存储&#xff0c;访问&#xff0c;备份&#xff0c;贡献等功能&#xff0c;是我们日常中不可或缺的一种服务。很多互联网公司都为个人和企业提供免费的网盘服务。但这些免费服务都有一些限制&#xff0c;比如限制下载速度&#xff0…

下载树莓派对应的64位Ubuntu系统步骤

说点废话&#xff1a;因为ros2需要安装在64位Ubuntu上面&#xff0c;所以安装64位最合适&#xff1b; 第一步打开https://cn.ubuntu.com/ 网站&#xff1b;选择下载--->iot----> 选择这个镜像文件下载。我觉得镜像文件是img格式的&#xff0c;跟iso文件区别是&#xff…

vue详细安装教程

这里写目录标题 一、下载和安装node二、创建全局安装目录和缓存日志目录三、安装vue四、创建一个应用程序五、3x版本创建六、创建一个案例 一、下载和安装node 官网下载地址&#xff1a;https://nodejs.org/en/download 选择适合自己的版本&#xff0c;推荐LTS&#xff0c;长久…

【计算机网络】计算机网络中的基本概念

文章目录 局域网LAN基于网线直连基于集线器组建基于交换机组建基于交换机和路由器组建 广域网WANIP地址端口号协议为什么要有协议知名协议的默认端口 五元组协议分层TCP/IP五层模型封装和分用 网络互连就是将多台计算机连接在一起&#xff0c;完成数据共享。数据共享本质是网络…

C++设计模式_23_Command 命令模式

我们将Command 和Visitor归为“行为变化”模式。 Command 命令模式与函数对象十分类似&#xff0c;但在C主流框架中&#xff0c;函数对象&#xff08;function object&#xff09;应用的更为广泛。 文章目录 1. “行为变化”模式1.1 典型模式 2. 动机( Motivation )3. 模式定义…