栈和队列(上)-栈

1. 栈的概念

        引入:

        我们平时拿羽毛球,是从盒子顶部的羽毛球开始拿的,而顶部的元素是我们最后放进去的.

        栈: 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.总而言之就是一个后进先出的线性表

压栈: 在栈里面插入元素,也叫做进栈/压栈/入栈.入数据是在栈顶

出栈: 在栈里面删除元素,也叫做出栈.出数据在栈顶

 2. 实现栈的方式

        我们实现栈可以用数组来实现,也可以用链表来实现栈.

        从上图中可以看到,Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的.

       我们也可以用链表来实现栈,我们如果用双链表来实现栈就很方便不管在把头当栈顶还是把尾当栈顶,出入栈都是O(1),但是如果用单链表,把它的尾巴当栈顶,那么出入栈就是O(n),用头当栈顶和双链表一样是O(1)

3. 栈的底层实现

        我们为了更好的理解栈,我们来自己实现一个栈

        首先我们写一个IStack接口

        然后我们写一个MyStack类实现这个接口,我们先来解释一下接口的一些变量,我们实现MyStack是使用的数组来实现的,所以我们先定义一个elem数组,我们再创建一个usedSize变量来记录有效数据的个数,然后设置一个默认容量,并且生成俩个构造方法,一个无参数的构造方法,在创建栈的时候默认容量是10,一个有参的构造方法,我们要大就设置多大的值.

        3.1  判断栈是不是满 isFull()

        当usedSize的大小和elem数组的大小一样的时候,我们就知道栈满了,如果不一样则没满.

        3.2 判断栈是不是空的 empty()

        如果usedSize的大小为0,说明栈里面没有元素了.

        3.3 计算栈的有效数据的数目(栈的大小) size()

        我们设置count变量,然后遍历整个栈,进行计数,其实也可以直接返回usedSize.

        3.4 入栈 push(int x)

        我们的usedSize下标就相当于一个下标,表示没有元素在数组里面的下标,因此我们直接借助usedSize即可,也就是elem[usedSize] = x;usedSize++;这就是入栈操作,不过在把元素放进去之前我们要判断栈是不是满了,如果满了我们就要进行二倍扩容也就是

                                   elem =Arrays.copyOf(elem,2*elem.length);

        3.5 出栈  pop()

        我们的出栈,首先要判断栈是不是空,如果式空我们需要抛出异常,在这个基础上,我们进行出栈操作,我们先保存出栈的元素的值,然后操作usedSize下标即可,因为我们入栈也是通过usedSize下标,就算数组下标之前有值,我们也可以直接覆盖掉.

        

        

        3.6 查看栈顶元素 peek()

        我们查看栈顶元素同样要看栈是不是空的,然后我们直接返回usedSize-1下标的elem数组的值即可.

整体代码:

package 栈和队列;import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;public class MyStack implements IStack{//我们的栈底层是个数组private int[] elem;private int usedSize;//有效数据的个数private static final int DEFALUT_CAPACITY = 10;public MyStack() {elem = new int[DEFALUT_CAPACITY];}public MyStack(int capacity) {elem = new int[capacity];}@Overridepublic void push(int x) {//TODO 入栈//先判断栈是不是满的if(isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}//把usedSize位置赋值为xelem[usedSize] = x;usedSize++;}@Overridepublic int pop() {//TODO 出栈//先判断是不是没有元素if(empty()){//抛异常throw new EmptException("栈空,无法出栈! ");}//我们的usedSize相当于存储了下标int old = elem[usedSize - 1];usedSize--;//这个就相当于删除,虽然原来位置还是有值,但是我们后期push会覆盖掉原先的值//如果是引用类型: elem[usedSize] = null;return old;}@Overridepublic int peek() {//TODO 看栈顶元素//先判断是不是没有元素if(empty()){//抛异常throw new EmptException("栈空,无法出栈! ");}return elem[usedSize - 1];//直接返回即可}@Overridepublic int size() {int count = 0;for (int i = 0; i < usedSize; i++) {count++;}return count;}@Overridepublic boolean empty() {return usedSize == 0;}@Overridepublic boolean isFull() {if (usedSize == elem.length){return true;}return false;}
}

4. java提供的栈的方法的使用和介绍

        下面是栈的方法:

方法功能
Stack()构造一个空的栈
E push(E e)入栈并返回e
E pop()出栈并返回栈顶元素
E peek()获取栈顶元素
int size()获取栈种有效元素的个数
boolean empty()检测栈是否为空

E这里表示泛型,泛型表示引用数据类型.

        我们来使用一下:

public class T1 {public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈,栈中剩余1 2 3,栈顶元素为3System.out.println(s.pop()); // 3出栈,栈中剩余1 2 栈顶元素为3if (s.empty()) {System.out.println("栈空");} else {System.out.println(s.size());}}
}
结果:
4
4
3
2

5. 栈、虚拟机栈、栈帧的区别

栈: 一种规定只能在一端进行插入或者删除的线性表,是一种后进先出的数据结构.

虚拟机栈: 是Java虚拟机(JVM)的一个概念,每个线程运行的时候都会创建自己的虚拟机栈.

简而言之: JVM划分的一块内存.

栈帧: 是用于支持Java虚拟机进行方法调用和方法执行的数据结构,是虚拟机栈的一部分,每次发生方法的调用就会为该方法创建一个新的栈帧并压入栈顶.

简而言之: 方法调用的时候会在虚拟机给方法开辟一块内存.

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

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

相关文章

温泉押金原路退回系统, 押金+手牌+电子押金单——未来之窗行业应用跨平台架构

一、温泉手牌收押金必要性 1. 防止手牌丢失&#xff1a;手牌是顾客在温泉内存储个人物品和进出更衣室的重要凭证。收押金可以让顾客更加重视手牌&#xff0c;降低丢失的概率。比如说&#xff0c;有的顾客可能会因为粗心大意随手放置手牌&#xff0c;如果没有押金的约束&…

STM32之外部中断(实验对射式传感器计次实验)

外部中断配置 #include "stm32f10x.h" // Device headeruint16_t CountSensor_Count;void CountSensor_Init(void) {//RCC--> GPIO--> AFIO--> EXTI--> NVIC五步RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOB, ENABLE); //开启GPIOB时…

图---java---黑马

图 概念 图是由顶点(vertex)和边(edge)组成的数据结构&#xff0c;例如 该图有四个顶点&#xff1a;A&#xff0c;B&#xff0c;C&#xff0c;D以及四条有向边&#xff0c;有向图中&#xff0c;边是单向的。 有向 vs 无向 如果是无向图&#xff0c;那么边是双向的&#x…

aarch64-opencv341交叉编译,并在arm上部署helloopencv

背景 当需要在jetson xavier nx或者rk 3562等平台上开发关于视觉检测的工程时&#xff0c;由于arm板子资源不足或者不能联网等原因&#xff0c;通常在虚拟机上利用交叉编译器编译得到可执行程序&#xff0c;然后部署到arm板上。 aarch64-opencv341交叉编译 ubuntu虚拟机中先…

【Linux】环境下升级redis

一、摘要 最近漏洞扫描服务器发现&#xff0c;Redis 缓冲区溢出漏洞(CVE-2024-31449)&#xff0c;解决办法redis更新到6.2.16、7.2.6或7.4.1及以上版本。 二、漏洞描述 漏洞描述&#xff1a;经过身份验证的用户可能会使用特制的 Lua 脚本来触发位库中的堆栈缓冲区溢出&#…

Kaggle比赛复盘

Kaggle - LLM Prompt Recovery 解决方案报告 比赛背景/目标 大型语言模型&#xff08;Large Language Models&#xff0c;LLMs&#xff09;通常被用于改写或对文本进行风格修改。本次Kaggle竞赛的目标是根据给定的改写文本&#xff0c;还原用于将原始文本转换为改写文本的LLM…

MetaArena推出《Final Glory》:引领Web3游戏技术新风向

随着区块链技术的日益成熟&#xff0c;Web3游戏成为了游戏产业探索的新方向&#xff0c;将去中心化经济与虚拟世界结合在一起&#xff0c;形成了一个全新的生态体系。然而&#xff0c;尽管Web3游戏展示了令人兴奋的可能性&#xff0c;但其背后的技术障碍依旧严峻&#xff0c;特…

Android Activity SingleTop启动模式使用场景

通知栏 当用户点击通知栏中的通知时,可以使用单顶启动模式来打开对应的活动,并确保只有一个实例存在。 简单集成极光推送 创建应用 获取appkey参数 切换到极光工作台 极光sdk集成 Project 根目录的主 gradle 配置 Module 的 gradle 配置 Jpush依赖配置 配置推送必须…

华为原生鸿蒙操作系统:我国移动操作系统的新篇章

华为原生鸿蒙操作系统&#xff1a;我国移动操作系统的新篇章 引言 在移动操作系统领域&#xff0c;苹果iOS和安卓系统一直占据主导地位。然而&#xff0c;随着华为原生鸿蒙操作系统的正式发布&#xff0c;这一格局正在发生深刻变化。作为继苹果iOS和安卓系统后的全球第三大移动…

Python酷库之旅-第三方库Pandas(170)

目录 一、用法精讲 781、pandas.arrays.IntervalArray.contains方法 781-1、语法 781-2、参数 781-3、功能 781-4、返回值 781-5、说明 781-6、用法 781-6-1、数据准备 781-6-2、代码示例 781-6-3、结果输出 782、pandas.arrays.IntervalArray.overlaps方法 782-1…

shodan3,vnc空密码批量连接,ip历史记录查找

shodan语法&#xff0c;count&#xff0c;honeyscore count 今天带大家继续学习shodan&#xff0c;今天会带大家学一学这个count命令&#xff0c;再学学其他小命令好其实关键命令也没那么多&#xff0c;就是很方便记忆一下就学会了这样子。 shodan count "/x03/x00/x00…

Docker下载途径

Docker不是Linux自带的&#xff0c;需要我们自己安装 官网&#xff1a;https://www.docker.com/ 安装步骤&#xff1a;https://docs.docker.com/engine/install/centos/ Docker Hub官网(镜像仓库)&#xff1a;https://hub.docker.com/ 在线安装docker 先卸载旧的docker s…

JMeter实战之——模拟登录

本篇介绍使用JMeter 如何对需要登录的站点进行压力测试。 基本Session验证的机制 使用session进行请求验证的机制是一种常见的Web应用认证方式。 该认证方式的主要内容如下&#xff1a; 一、登录过程 用户输入&#xff1a;用户在登录页面输入用户名和密码。发送请求&#x…

JDBC: Java数据库连接的桥梁

什么是JDBC&#xff1f; Java数据库连接&#xff08;Java Database Connectivity&#xff0c;简称JDBC&#xff09;是Java提供的一种API&#xff0c;允许Java应用程序与各种数据库进行交互。JDBC提供了一组标准的接口&#xff0c;开发者可以利用这些接口执行SQL语句、处理结果集…

XQT_UI 组件|02| 按钮 XPushButton

XPushButton 使用文档 简介 XPushButton 是一个自定义的按钮类&#xff0c;基于 Qt 框架构建&#xff0c;提供了丰富的样式和功能选项。它允许开发者轻松创建具有不同外观和行为的按钮&#xff0c;以满足用户界面的需求。 特性 颜色设置&#xff1a;支持多种颜色选择。样式设…

Python之Excel自动化处理(三)

一、Excel数据拆分-xlrd 1.1、代码 import xlrd from xlutils.copy import copydef get_data():wb xlrd.open_workbook(./base_data/data01.xlsx)sh wb.sheet_by_index(0){a: [{},{},{}],b:[{},{},{}],c:[{},{},{}],}all_data {}for r in range(sh.nrows):d {type:sh.cell…

css知识点梳理2

1. 选择器拓展 在 CSS 中&#xff0c;可以根据选择器的类型把选择器分为基础选择器和复合选择器&#xff0c;复合选择器是建立在基础选择器之上&#xff0c;对基本选择器进行组合形成的。 ​ 复合选择器是由两个或多个基础选择器&#xff0c;通过不同的方式组合而成的&#xf…

《a16z : 2024 年加密货币现状报告》解析

加密社 原文链接&#xff1a;State of Crypto 2024 - a16z crypto译者&#xff1a;AI翻译官&#xff0c;校对&#xff1a;翻译小组 当我们两年前第一次发布年度加密状态报告的时候&#xff0c;情况跟现在很不一样。那时候&#xff0c;加密货币还没成为政策制定者关心的大事。 比…

服务器数据恢复—EXT3文件系统下邮件数据被误删的数据恢复案例

服务器数据恢复环境&#xff1a; 邮件服务器中有一组由8块盘组成的RAID5阵列, 上层是Linux操作系统EXT3文件系统。 服务器故障&#xff1a; 由于误删除导致文件系统中的邮件数据丢失。 服务器数据恢复过程&#xff1a; 1、将故障服务器中所有硬盘做好标记后取出&#xff0c;硬…

Python实现Android设备录屏功能及停止录屏功能

1、功能概述&#xff1f; 提供源码下载 之前通过ADB命令实现了实时的录屏功能。但是很遗憾&#xff0c;虽然通过adb命令录屏非常方便&#xff0c;但由于权限限制&#xff0c;无法在安卓系统较高的设备上使用。现选择使用另一开源工具来解决这一问题&#xff0c;并记录使用详细…