Java中的Stack(栈)(如果想知道Java中有关Stack的知识点,那么只看这一篇就足够了!)

        前言:栈(Stack)是一种基础且重要的数据结构,以其后进先出(LIFO, Last In First Out)的特性广泛应用于计算机科学和编程中。


✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容:

目录

1.栈的初识

2.栈的自我实现

(1)数组实现:

(2)链表实现

3.栈中常用API

4.栈的应用场景

5.总结


1.栈的初识

        在开始学习使用栈之前,先让我们来了解一下什么是栈:

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

栈的主要特性包括:

  1. 后进先出(LIFO):最新压入栈的数据最先被弹出。
  2. 栈顶操作:所有的插入(push)和删除(pop)操作都只能在栈顶进行。

        如果使用我们日常生活中的案例来解释的话,就如同子弹弹夹,先装入的子弹后被打出,后装入的子弹,先被打出:

将其转换为编程语言图像(如图):

其中:

        ——压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

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

通过上述的讲解,这样我们就大致的了解了什么是栈(Stack)了!

2.栈的自我实现

        学习完了什么是栈之后,然我们试试能不能使用已有的知识体系来实现栈,在Java中自我实现栈的方式大致有两种:使用数组实现与使用链表实现

(1)数组实现:

public class ArrayStack {public int[] stack; // 用于存储栈元素的数组public int top; // 栈顶索引public ArrayStack(int size) {stack = new int[size]; // 初始化数组大小top = -1; // 初始化栈顶索引为-1,表示栈为空}// 将元素压入栈顶public void push(int value) {if (top == stack.length - 1) {throw new StackOverflowError("Stack is full"); // 如果栈已满,抛出异常}stack[++top] = value; // 将元素压入栈顶,并更新栈顶索引}// 弹出栈顶元素public int pop() {if (top == -1) {throw new EmptyStackException(); // 如果栈为空,抛出异常}return stack[top--]; // 返回栈顶元素,并更新栈顶索引}// 返回栈顶元素但不弹出public int peek() {if (top == -1) {throw new EmptyStackException(); // 如果栈为空,抛出异常}return stack[top]; // 返回栈顶元素}// 检查栈是否为空public boolean isEmpty() {return top == -1; // 如果栈顶索引为-1,表示栈为空}
}

现在我们再回顾一下上述代码的逻辑:

        1. 首先先定义了一个基于数组实现的栈类 ArrayStack。它包含一个用于存储栈元素的数组 stack 和一个指示栈顶位置的变量 top
        2. 然后使用构造方法 ArrayStack(int size) 来初始化栈的大小,并将 top 设置为 -1。

        3. push(int value) 方法将元素压入栈顶,如果栈满则抛出 StackOverflowErrorpop() 方法弹出栈顶元素,如果栈为空则抛出 EmptyStackExceptionpeek() 方法返回栈顶元素但不弹出,如果栈为空则抛出 EmptyStackExceptionisEmpty() 方法检查栈是否为空。

(2)链表实现

public class DoublyLinkedListStack {public Node head; // 链表头节点public Node tail; // 链表尾节点// 定义节点类private static class Node {int value; // 节点值Node next; // 指向下一个节点的指针Node prev; // 指向上一个节点的指针Node(int value) {this.value = value; // 初始化节点值this.next = null; // 初始化下一个节点指针为空this.prev = null; // 初始化前一个节点指针为空}}public DoublyLinkedListStack() {head = null; // 初始化头节点为空tail = null; // 初始化尾节点为空}// 将元素压入栈顶public void push(int value) {Node newNode = new Node(value); // 创建新节点if (tail == null) {head = tail = newNode; // 如果链表为空,头尾节点都指向新节点} else {tail.next = newNode; // 将新节点连接到链表尾部newNode.prev = tail; // 新节点的前驱指向当前尾节点tail = newNode; // 更新尾节点为新节点}}// 弹出栈顶元素public int pop() {if (tail == null) {throw new EmptyStackException(); // 如果栈为空,抛出异常}int value = tail.value; // 获取尾节点的值if (tail.prev == null) {head = tail = null; // 如果只有一个元素,清空链表} else {tail = tail.prev; // 更新尾节点为前驱节点tail.next = null; // 断开新尾节点的next指针}return value; // 返回弹出的值}// 返回栈顶元素但不弹出public int peek() {if (tail == null) {throw new EmptyStackException(); // 如果栈为空,抛出异常}return tail.value; // 返回尾节点的值}// 检查栈是否为空public boolean isEmpty() {return tail == null; // 如果尾节点为空,栈为空}
}

现在我们再回顾一下上述代码的逻辑:

        首先我们先定义了一个基于双向链表实现的栈类 DoublyLinkedListStack。它包含头节点和尾节点,使用内部的 Node 类表示每个节点。然后我们实现了一下主要的方法包括:

  • push(int value):将新元素压入栈顶。

  • pop():弹出栈顶元素,如果栈为空则抛出异常。

  • peek():返回栈顶元素但不弹出,若栈为空则抛出异常。

  • isEmpty():检查栈是否为空,返回布尔值。

这样我们就用现有的知识体现来实现了栈(Stack)了!

3.栈中常用API

        学习完了自我实现栈(Stack)之后,现在让我们看看Java中自带的Stack如何使用吧:

栈中常用的方法主要包括以下几种:

  1. push(E item):将元素压入栈顶。
  2. pop():移除并返回栈顶元素。
  3. peek():返回栈顶元素但不移除。
  4. isEmpty():检查栈是否为空。

现在让我们使用一个实例来进行讲解:

import java.util.Stack;public class StackExample {public static void main(String[] args) {//创建一个栈Stack<Integer> stack = new Stack<>();// 压入栈顶stack.push(1);stack.push(2);stack.push(3);// 查看栈顶元素System.out.println("栈顶元素: " + stack.peek());// 弹出栈顶元素System.out.println("弹出栈顶元素: " + stack.pop());// 查看栈顶元素System.out.println("栈顶元素: " + stack.peek());// 检查栈是否为空System.out.println("栈是否为空: " + stack.isEmpty());}
}

——这样我们就大致的了解了在Java中如何去操作一个创建出来的栈了!

4.栈的应用场景

        学习完栈之后,读者可能会发出疑问,栈到底有什么用处呢?栈在实际应用中有许多场景,下面列举几个典型的应用:

  1. 表达式求值:如中缀表达式转后缀表达式的计算。
  2. 函数调用:栈用于保存函数调用过程中的局部变量和返回地址。
  3. 括号匹配:用于检查括号是否成对匹配。
  4. 浏览器的前进后退:使用栈保存历史页面,以便用户前进和后退。
  5. 深度优先搜索(DFS):在图或树的遍历中使用。

        这里我们只举出第一个(表达式求值)来讲解(其他读者如果有兴趣进一步学习,可以自行查找学习!

表达式求值即为:中缀表达式转换为后缀表达式(也称逆波兰表达式),以下为百度的解释:

其作用主要体现在以下几个方面:

  1. 简化计算:后缀表达式不需要括号,操作符和操作数的顺序明确,计算时更简单。

  2. 便于计算机处理:计算机处理后缀表达式更高效,避免了运算优先级的复杂性。

  3. 支持堆栈算法:后缀表达式可以直接使用栈来进行求值,适合实现逆波兰表示法。

  4. 提高表达式解析速度:在编译器和解释器中,后缀表达式有助于快速解析和执行表达式。

了解完了什么是逆波兰表达式之后,我们使用一道例题来进行讲解:

题目链接:----->. - 力扣(LeetCode)

解题的大致思路为:

import java.util.Stack;public class PostfixEvaluation {public static int evaluate(String expression) {Stack<Integer> stack = new Stack<>(); // 创建一个栈用于存储操作数// 遍历后缀表达式中的每个字符for (char c : expression.toCharArray()) {if (Character.isDigit(c)) {// 如果是数字,将其压入栈中stack.push(c - '0');} else {// 如果是操作符,从栈中弹出两个操作数int b = stack.pop(); // 弹出栈顶元素作为右操作数int a = stack.pop(); // 弹出下一个元素作为左操作数// 根据操作符进行计算,并将结果压入栈中switch (c) {case '+':stack.push(a + b);break;case '-':stack.push(a - b);break;case '*':stack.push(a * b);break;case '/':stack.push(a / b);break;}}}return stack.pop(); // 返回栈顶元素,即最终结果}public static void main(String[] args) {String expression = "231*+9-"; // 后缀表达式示例System.out.println("后缀表达式求值结果: " + evaluate(expression)); // 输出结果}
}

这样我们就大致的理解了栈的用处了!

5.总结

        栈是一种基础且重要的数据结构,它的后进先出特性在许多应用场景中发挥了重要作用。在Java中,栈可以通过数组和链表实现,java.util.Stack类也提供了现成的栈实现。

        通过理解栈的基本概念和常用方法,以及掌握如何使用双向链表自我实现栈,我们可以在实际编程中更加灵活地运用这一数据结构。栈在表达式求值、函数调用、括号匹配、浏览器前进后退和深度优先搜索等方面都有广泛的应用,熟练掌握栈的使用将极大提高我们的编程能力。


以上就是本篇文章的全部内容了~~~

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

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

相关文章

VS code EXPLORER 中不显示指定文件及文件夹设置(如.pyc, __pycache__, .vscode 文件)

VS code EXPLORER 中不显示指定文件及文件夹设置 引言正文方法1打开方式1打开方式2 方法2 引言 VS code 号称地表最强轻量级编译器&#xff0c;其最大的优势在于用户可以根据自己的需求下载适合自己的 extension。从而定制个性化的编译器。然而&#xff0c;本人今天遇到了一个…

【machine learning-七-线性回归之成本函数】

监督学习之cost function 成本函数权重、偏置如何实现拟合数据成本函数是如何寻找出来w和b&#xff0c;使成本函数值最小化&#xff1f; 在线性回归中&#xff0c;我们说到评估模型训练中好坏的一个方法&#xff0c;是用成本函数来衡量&#xff0c;下面来详细介绍一下 成本函数…

IPv6路由基础

RIPng RIPng是一种较为简单的内部网关协议&#xff0c;是RIP在IPv6网络中的应用。RIPng主要用于规模较小的网络中&#xff0c;比如校园网以及结构较简单的地区性网络。由于RIPng的实现较为简单&#xff0c;在配置和维护管理方面也远比OSPFv3和IS-IS for IPv6容易&#xff0c;因…

黑马头条APP手工测试项目

1.app有关概念 APP测试范围&#xff1a; 业务功能测试 专项测试&#xff1a;兼容性测试 、安装/卸载/升级测试、交叉事件测试 、push消息推送测试、性能测试、其他测试&#xff08;用户体验、权限/边界、权限&#xff09; 功能测试测试对象&#xff1a; 功能点&#xff08;单…

JAVA虚拟机----JVM

(一)认识JVM JVM 是 Java Virtual Machine 的简称&#xff0c;意为 Java虚拟机。 虚拟机是指通过软件模拟的具有完整硬件功能的、运⾏在⼀个完全隔离的环境中的完整计算机系统。 常⻅的虚拟机&#xff1a;JVM、VMwave、Virtual Box。 &#xff08;二&#xff09;JVM运…

EmguCV学习笔记 C# 12.3 OCR

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 EmguCV是一个基于OpenCV的开源免费的跨平台计算机视觉库,它向C#和VB.NET开发者提供了OpenCV库的大部分功能。 教程VB.net版本请访问…

EmguCV学习笔记 C# 12.2 WeChatQRCode

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 EmguCV是一个基于OpenCV的开源免费的跨平台计算机视觉库,它向C#和VB.NET开发者提供了OpenCV库的大部分功能。 教程VB.net版本请访问…

【Android】Handler用法及原理解析

文章目录 用处基本用法用法一&#xff1a;使用sendMessage和handleMessage方法用法二&#xff1a;使用post方法 法一工作原理Handler的sendMessageMessage成员变量 MessageQueueLooper主线程自动初始化子线程手动创建prepareloop Handler的dispatchMessage 法二工作原理Handler…

electron多标签页模式更像客户端

Electron多标签页模式是指在Electron框架中实现的类似Web浏览器的多标签页功能。Electron是一个使用Web技术&#xff08;HTML、CSS和JavaScript&#xff09;来创建跨平台桌面应用程序的框架。在Electron中实现多标签页模式&#xff0c;通常需要借助一些特定的库或组件&#xff…

PMP--二模--解题--11-20

文章目录 14.敏捷--实践--每日站会--团队成员利用每日站会对彼此做出小的承诺&#xff0c;发现问题&#xff0c;并确保团队工作顺利进行。&#xff08;不是项目经理说&#xff0c;是团队成员&#xff09;11、 [单选] 在每日站会上&#xff0c;项目经理与团队成员逐个交流&#…

VMware ESXi 7.0U3q macOS Unlocker 集成驱动版更新 OEM BIOS 2.7 支持 Windows Server 2025

VMware ESXi 7.0U3q macOS Unlocker 集成驱动版更新 OEM BIOS 2.7 支持 Windows Server 2025 VMware ESXi 7.0U3q macOS Unlocker & OEM BIOS 2.7 集成网卡驱动和 NVMe 驱动 (集成驱动版) ESXi 7.0U3 标准版集成 Intel 网卡、Realtek USB 网卡 和 NVMe 驱动 请访问原文链…

口哨声、歌声、boing声和biotwang声:用AI识别鲸鱼叫声

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

web基础—dvwa靶场(八)XSS

XSS(DOM) 跨站点脚本&#xff08;XSS&#xff09;攻击是一种注入攻击&#xff0c;恶意脚本会被注入到可信的网站中。当攻击者使用 web 应用程序将恶意代码&#xff08;通常以浏览器端脚本的形式&#xff09;发送给其他最终用户时&#xff0c;就会发生 XSS 攻击。允许这些攻击成…

[Unity Demo]从零开始制作空洞骑士Hollow Knight第五集:再制作更多的敌人

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、制作敌人另个爬虫Crawler 1.公式化导入制作另个爬虫Crawler素材2.制作另个爬虫Crawler的Crawler.cs状态机3.制作敌人另个爬虫Crawler的playmaker状态机二、…

大型语言模型 (LLM) 劫持攻击不断升级,导致每天损失超过 100,000 美元

Sysdig 威胁研究团队 (TRT) 报告称&#xff0c;LLMjacking&#xff08;大型语言模型劫持&#xff09;事件急剧增加&#xff0c;攻击者通过窃取的云凭证非法访问大型语言模型 (LLM)。 这一趋势反映了 LLM 访问黑市的不断增长&#xff0c;攻击者的动机包括个人使用和规避禁令和制…

DNS服务

一.DNS介绍 DNS应用层协议 Domain Name System 域名系统 作用&#xff1a;实现域名解析&#xff0c;解析主机名所对应的IP地址&#xff0c; 在网络环境中设备与设备之间要想相互通信只能依赖IP地址&#xff0c;DNS服务器的作用是实现域名解析。 如上图所示&#xff0c;DNS存…

英飞凌 PSoC6 RT-Thread 评估板简介

概述 2023年&#xff0c;英飞凌&#xff08;Infineon&#xff09;联合 RT-Thread 发布了一款 PSoC™ 62 with CAPSENSE™ evaluation kit 开发板 &#xff08;以下简称 PSoC 6 RTT 开发板&#xff09;&#xff0c;该开发套件默认内置 RT-Thread 物联网操作系统。PSoC 6 RTT 开…

Matplotlib | 一文搞定Matplotlib从入门到实战演练!

文章目录 1 什么是Matplotlib1.1 Matplotlib的安装1.2 Matplotlib的基本使用 2 绘制直线3 绘制折线设置标签文字和线条粗细设置中文标题风格的设置 4 绘制曲线绘制曲线yx^2绘制正弦曲线和余弦曲线画布分区 5 绘制散点图绘制不同种类不同颜色的线 6 绘制条形图&#xff08;柱状&…

计算机网络 ---- OSI参考模型TCP/IP模型

目录 一、OSI参考模型 1.1 学习路线 1.2 OSI参考模型和TCP/IP模型 1.3 具体设备与具体层次对应关系 1.3.1 物理层 1.3.2 数据链路层 1.3.3 网络层 1.3.4 传输层 1.3.5 会话层、表示层、应用层 1.4 各层次数据传输单位 二、TCP/IP模型 2.1 学习路线 2.2 TCP/I…

对 JavaScript 原型的理解

笔者看了一些有关 JavaScript 原型的文章有感而发&#xff0c;就将所感所悟画了下来如果有理解错误和不足的地方&#xff0c;欢迎各位大佬指出&#xff0c;笔者感激不尽