【数据结构】栈(stack)

目录

栈的概念

栈的方法

栈的实现

数组实现

push方法 压栈

pop方法 出栈

peek方法 获取栈顶元素

size方法 获取有效元素个数

链表实现

 结尾

完整代码 

数组实现栈代码

双向链表实现栈代码


栈的概念

栈是一种特殊的线性表,只允许在 固定的一段 进行插入和删除数据,配合下面图能有更清楚的认识。

压栈:栈的插入顺序叫做进栈/压栈/入栈,入数据在栈底

出栈:栈的删除操作叫做出栈,出数据在栈顶

栈里面放数据的顺序是 12 23 34,取出数据的顺序是34 23 12

更形象一点的例子,是枪子弹的打出顺序,最后的放进去的子弹会先被打出,

栈从虚拟机的角度有个特点:先进的后出

栈的方法

 栈的方法有一下六种

栈的实现

栈可以从数组方面实现,也可以从链表方面实现,下面会有对应的演示。

数组实现的栈叫做 顺序栈,链表实现的栈叫做 链式栈。

数组实现

先定义基本变量,因为是数组实现栈,所以定义数组elem以及useSize记录数组中有效元素个数。

public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}
}
push方法 压栈
    public void push(int val){elem[useSize] = val;useSize++;}

这部分代码看起来是符合我们要求的,是要把 val值 放入到 elem数组中,但这是一般情况,如果我们放 val值  时数组满了,是不是需要给数组扩容,这时候我们可以写一个判断数组是否为满的方法(isFull方法)。因为这个方法只有push方法才用得到,所以用private。

    private boolean isFull(){return useSize == elem.length;}

push方法完整为以下代码:

    public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}
pop方法 出栈

pop方法的功能是把栈顶的元素移出栈,同时打印一遍。在移除元素之前,要考虑到栈里有没有元素,没有元素就无法移除。所以需要写一个方法来判断(isEmpty方法)。

    private boolean isEmpty(){return useSize == 0;}

对于移除栈顶的元素,也就是最后加入的元素,我们可以采用useSize-1来实现,这样就能在打印数组的时候不去打印出栈顶的元素。

    public int pop(){if(isEmpty()){System.out.println("栈为空");//这里也可以写个异常来提醒}int cur = elem[useSize-1];useSize--;return cur;}

 如果要写一个异常来提醒的话,需要再写一个异常类

对应的pop方法为

    public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}
peek方法 获取栈顶元素

获取栈顶元素在上面的出栈方法中也提到了,不过上面是要把栈顶元素删除,这里只需要返回即可。

    public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}
size方法 获取有效元素个数

这里其实在定义初始变量的时候也有提到,便是其中 useSize 所代表的意思。

    public int size(){return useSize;}

链表实现

用链表实现栈,推荐使用双向链表来实现

因为 入栈 不管是头插法还是尾插法都可以是心啊,时间复杂度都是O(1)。

public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}

 结尾

区分三种不同的概念

栈:是一种数据结构

虚拟机栈:是JVM中一类内存

栈帧:是运行一个函数/方法,给这个函数开辟的一个内存

完整代码 

数组实现栈代码

CheckEmptyException类

public class CheckEmptyExpetion extends RuntimeException{public CheckEmptyExpetion() {}public CheckEmptyExpetion(String message) {super(message);}
}

MyStack类

import java.util.Arrays;public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}public void push(int val){if(isFull()){elem = Arrays.copyOf(elem,2*elem.length);}elem[useSize] = val;useSize++;}private boolean isFull(){return useSize == elem.length;}public int pop(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];useSize--;return cur;}public int peek(){if(isEmpty()){throw new CheckEmptyExpetion("栈为空");}int cur = elem[useSize-1];return cur;}private boolean isEmpty(){return useSize == 0;}public int size(){return useSize;}
}

双向链表实现栈代码

    public static void main(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack);}

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

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

相关文章

kafka发送消息-生产者发送消息的分区策略(消息发送到哪个分区中?是什么策略)

生产者发送消息的分区策略&#xff08;消息发送到哪个分区中&#xff1f;是什么策略&#xff09; 1、默认策略&#xff0c;程序自动计算并指定分区1.1、指定key&#xff0c;不指定分区1.2、不指定key&#xff0c;不指定分区 2、轮询分配策略RoundRobinPartitioner2.1、创建配置…

使用idea快速创建springbootWeb项目(springboot+springWeb+mybatis-Plus)

idea快速创建springbootWeb项目 详细步骤如下 1&#xff09;创建项目 2&#xff09;选择springboot版本 3&#xff09;添加web依赖 4&#xff09;添加Thymeleaf 5&#xff09;添加lombok依赖 然后点击create进入下一步 双击pom.xml文件 6&#xff09;添加mybatis-plus依赖 …

【系统分析师】-案例篇-数据库

1、分布式数据库 1&#xff09;请用300字以内的文字简述分布式数据库跟集中式数据库相比的优点。 &#xff08;1&#xff09;坚固性好。由于分布式数据库系统在个别结点或个别通信链路发生故障的情况下&#xff0c;它仍然可以降低级别继续工作&#xff0c;系统的坚固性好&…

Ubuntu搭建FTP服务器

目录 1.ftp简介 2.vsftpd 2.1.介绍 2.2.安装与卸载 2.3.综合案例 - 本地用户模式 2.4.1.创建FTP用户 2.4.2.配置vsftpd 2.4.3.配置防火墙 1.ftp简介 一般来讲&#xff0c;人们将计算机联网的首要目的就是获取资料&#xff0c;而文件传输是一种非常重要的获取资料的方…

Docker 修改镜像源

由于docker hub 被禁&#xff0c;导致 docker 拉取镜像失败&#xff0c;解决办法就是使用国内的镜像源&#xff0c;目前国内的镜像源还是很多的&#xff0c;例如阿里云、腾讯云、华为云等等&#xff0c;下面演示一个更换成阿里云的步骤。 1. 阿里云获取加速地址 1.1 首先登录阿…

Git —— 1、Windows下安装配置git

Git简介 Git 是一个免费的开源分布式版本控制系统&#xff0c;旨在处理从小型到 快速高效的超大型项目。 Git 易于学习&#xff0c;占用空间小&#xff0c;性能快如闪电。 它超越了 Subversion、CVS、Perforce 和 ClearCase 等 SCM 工具 具有 cheap local branching、 方便的暂…

HIVE 数据仓库工具之第一部分(讲解部署)

HIVE 数据仓库工具 一、Hive 概述1.1 Hive 是什么1.2 Hive 产生的背景1.3 Hive 优缺点1.3.1 Hive的优点1.3.2 Hive 的缺点 1.4 Hive在Hadoop生态系统中的位置1.5 Hive 和 Hadoop的关心 二、Hive 原理及架构2.1 Hive 的设计原理2.2 Hive 特点2.3 Hive的体现结构2.4 Hive的运行机…

Linux 配置wireshark 分析thread 使用nRF-Sniffer dongle

Linux 配置wireshark nRF-Sniffer-for-802.15.4 1.下载固件和配置文件 https://github.com/NordicSemiconductor/nRF-Sniffer-for-802.15.4 2.烧写固件 使用nRF Connect for Desktop 中的 programmer 4.3烧写 https://www.nordicsemi.com/Products/Development-tools/nrf-conne…

【layUI】点击导出按钮,导出excel文件

要实现的功能如下&#xff1a;根据执行状态判断是否可以导出。如果可以导出&#xff0c;点击导出&#xff0c;在浏览器里下载对应的文件。 代码实现 html里&#xff1a; <table class"layui-hide" id"studentTable" lay-filter"studentTable&…

Dubbo3框架概述

1 什么是分布式系统? 《分布式系统原理与范型》定义: “分布式系统是若干独立计算机的集合,这些计算机对于用户来说就像单个相关系统” 分布式系统(distributed system)是建立在网络之上的软件系统。 简单来说:多个(不同职责)人共同来完成一件事! 任何一台服务器都无法…

open62541 使用账号密码认证示例

一、官方源码示例 源码参考 服务端官方示例&#xff1a; /* This work is licensed under a Creative Commons CCZero 1.0 Universal License.* See http://creativecommons.org/publicdomain/zero/1.0/ for more information. */#include <open62541/plugin/accesscont…

QtWebEngineView加载本地网页

直接加载放在exe同级目录下的资源是不行的&#xff0c;需要把资源通过qrc放到exe里面&#xff0c;然后通过类似qrc:/robotHtml/index.html这样的路径加载才行。 mWebView new QWebEngineView(parent);// mWebView->load(QUrl::fromLocalFile("./robotHtml/index.html&…

【网络安全】XML-RPC PHP WordPress漏洞

未经许可,不得转载。 文章目录 前言WordPressWordPress中的Xmlrpc.php利用前提:Xmlrpc可访问深度利用1、用户名枚举2、跨站点端口攻击(XSPA)或端口扫描3、使用xmlrpc.php进行暴力攻击前言 本文将解释xmlrpc.php WordPress 漏洞及利用方式,并以三种攻击方法进行阐发: 1、…

代码随想录算法训练营第四十一天 | 121. 买卖股票的最佳时机 , 122.买卖股票的最佳时机II , 123.买卖股票的最佳时机III

目录 121. 买卖股票的最佳时机 思路 暴力 贪心 动态规划 1.确定dp数组&#xff08;dp table&#xff09;以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 方法一&#xff1a; 贪心 方法二&#xff1a;动态规划1 方法三&#xf…

国内外大模型汇总:Open AI大模型、Google大模型、Microsoft大模型、文心一言大模型、通义千问大模型、字节豆包大模型、智普清言大模型

Open AI大模型 特点&#xff1a; 多模态能力&#xff1a;如GPT-4o&#xff0c;能接受文本、音频、图像作为组合输入&#xff0c;并生成任意形式的输出。 情感识别与回应&#xff1a;具备情感识别能力&#xff0c;能根据对话者的情绪做出有感情的回应。 几乎无延迟&#xff…

XSS LABS - Level 14 过关思路

关注这个靶场的其他相关笔记&#xff1a;XSS - LABS —— 靶场笔记合集-CSDN博客 0x01&#xff1a;关卡配置 这一关有些特殊&#xff0c;需要链接到外部站点&#xff0c;但是这个站点已经挂了&#xff0c;无法访问&#xff1a; 所以笔者就根据网上的资料&#xff0c;对这一关进…

k8s的安装

概念 全写&#xff1a;Kubernets k8s作用&#xff1a;用于自动部署、拓展、管理容器化部署的应用程序。它是半开源的&#xff0c;核心是在谷歌里面&#xff0c;它的底层是由go语言开发的。可以理解成负责自动化运维管理多个容器化的应用的集群。也可以理解为容器编排框架的工…

2k1000LA 调试4G

问题&#xff1a; 其实算不上 调试&#xff0c; 之前本来4G是好的&#xff0c;但是 我调试了触摸之后&#xff0c;发现4G用不了了。 其实主要是 pppd 这个命令找不到。 首先来看 为什么 找不到 pppd 这个命令。 再跟目录使用 find 命令&#xff0c;能够找到这个命令&#…

PyCharm中python语法要求——消去提示波浪线

PyCharm中python语法要求——消去提示波浪线 关闭代码规范检查 在Setting里边搜索pep&#xff0c;取消勾选pep8 coding style violation 问题产生 解决问题 按照下图操作&#xff0c;也可直接CtrlAlts弹出设置页面 在 Settings 中 &#xff1a; Editor > Color Sheame >…

百度搜索的RLHF性能优化实践

作者 | 搜索架构部 导读 本文大语言模型在未经标注的大量文本上进行预训练后&#xff0c;可能产生包含偏见、泄露隐私甚至对人类构成威胁的内容。OpenAI 最先提出了基于人类反馈的强化学习算法(Reinforcement Learning fromHuman Feedback, RLHF)&#xff0c;将人类偏好引入到…