“探秘数据结构:栈的奇妙魔力“

每日一言

兰有秀兮菊有芳,怀佳人兮不能忘。 —刘彻-


栈的概念及结构

栈(Stack) :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。类似于一个垂直摞起来的盘子,想要拿或放只能从顶上,而不能从底部操作。
在这里插入图片描述

栈的一些操作

压栈(push):栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈(pop):栈的删除操作叫做出栈。出数据也在栈顶
获取栈顶元素(top):获取栈顶元素,但不将其从栈中移除。
判断栈是否为空(isEmpty):判断栈是否为空操作会返回一个布尔值,表示栈是否为空。

在这里插入图片描述

栈的实现

顺序栈

顺序栈是一种基于数组实现的栈数据结构。
在这里插入图片描述

代码实现

//准备工作

	int[] array;
    int size;//当前栈内的空间大小

    //创建栈,为栈分配存储空间
    public MyStack() {
        array = new int[3];
    }

//入栈

public void push(int val) {
        //检查是否需要扩容
        ensureCapacity();

        //入栈,并将栈的大小自增1
        array[size++] = val;
    }

//出栈

public int pop() {
		//因为top()方法中已经检查了栈是否为空,所以这里就不再检查了
        int val = top();
        size--;
        return val;
    }

//判断栈是否为空

public boolean isEmpty() {
        return size == 0;
    }

//获取栈顶元素

public int top() {
        if (isEmpty()) {
            System.out.println("栈为空!");
            return -1;//这里也可以写成抛出一个异常
        }
        return array[size - 1];
    }

//检查扩容

public void ensureCapacity() {
		//检查栈是否已满
        if (size == array.length) {
        	//已满,将栈的容量扩大一倍
            array = Arrays.copyOf(array, size * 2);
        }
    }

链栈

采用链式存储结构实现的栈称为链栈,链栈通常采用单链表来实现,因此其结构与单链表的结构相同由于栈的插入和删除操作仅限制在栈顶位置进行,所以采用单链表的表头指针作为栈顶指针。

代码实现
//准备工作

	private Element base;//栈底指针
    private Element top;//栈顶指针
    
    //栈中的每个节点
    private class Element {
        private int data;
        private Element next;
    }

//入栈

public void push(int val) {
        Element newElem = new Element();
        newElem.data = val;
        newElem.next = top;
        top = newElem;
    }

//出栈

 public int pop() {
        if(isEmpty()) {
            System.out.println("栈为空!");
            return -1;//这里也可以抛出异常
        }
        int val = top.data;
        top = top.next;
        return val;
    }

//判断栈是否为空

public boolean isEmpty() {
        //栈底指针和栈顶指针指向同一位置,此时栈为空
        return base == top;
    }

//获取栈顶元素

public int top() {
        return top.data;
    }

栈小结

⭐栈的特点是?
先进后出

⭐顺序栈与链栈哪个更好?

顺序栈和链栈各有优缺点,没有绝对的“更好”。选择哪种实现方式取决于问题的要求和特点。

⭐顺序栈(数组实现)的优点是:

  1. 存储空间连续,可以利用数组的随机访问特性,对栈的操作具有较高的效率。
  2. 实现简单,代码量较少。

⭐顺序栈(数组实现)的缺点是:

  1. 存储空间固定,创建栈时必须指定大小,大小无法动态调整。
  2. 当栈满时需要进行扩容,需要重新分配更大的内存空间,并将原有数据复制到新的内存空间中。

⭐链栈的优点是:

  1. 存储空间可以动态分配,不受固定大小的限制。
  2. 插入和删除元素的操作只需要修改指针,不需要移动大量的数据,相对较快。

⭐链栈的缺点是:

  1. 需要额外的指针指向下一个节点,增加了存储空间的开销。
  2. 由于每个节点需要存储指针,导致链栈的存储密度较低,对内存的利用率较低。

有关栈的一些题

1. 有效的括号

题目链接: 有效的括号

题目

给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

  • 示例 1:
    输入:s = “()”
    输出:true

  • 示例 2:
    输入:s = “()[]{}”
    输出:true

  • 示例 3:
    输入:s = “(]”
    输出:false

提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成


思路

  1. 遍历字符串中的每个字符。
  2. 如果字符是一个开括号(即’(', ‘[’, ‘{’),它会被压入栈中。
  3. 如果字符是一个闭括号,则检查栈是否为空。如果栈为空,意味着没有相应的开括号,字符串无效。如果栈不为空,则检查栈的顶部是否包含相应的开括号。如果是,栈的顶部元素将被弹出。如果不是,意味着字符串无效。
  4. 在遍历字符串的所有字符之后,检查栈是否为空。如果栈为空,意味着所有的开括号已经匹配并从栈中弹出,字符串有效。如果栈不为空,意味着还有剩余的开括号,字符串无效。

代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.add(ch);
            }else {
                if(stack.isEmpty()){
                    return false;
                }else { 
                    if (ch == ')' && stack.peek() == '(' ||
                        ch == ']' && stack.peek() == '[' ||
                        ch == '}' && stack.peek() == '{' ) {
                    stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}

2. 逆波兰表达式求值

题目链接: 逆波兰表达式求值

题目

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数(运算对象)都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

  • 示例 1:
    输入:tokens = [“2”,“1”,“+”,“3”,“*”]
    输出:9
    解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

  • 示例 2:
    输入:tokens = [“4”,“13”,“5”,“/”,“+”]
    输出:6
    解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

  • 示例 3:
    输入:tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
    输出:22
    解释:该算式转化为常见的中缀算术表达式为:
    ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    = ((10 * (6 / (12 * -11))) + 17) + 5
    = ((10 * (6 / -132)) + 17) + 5
    = ((10 * 0) + 17) + 5
    = (0 + 17) + 5
    = 17 + 5
    = 22

提示:
1 <= tokens.length <= 104
tokens[i] 是一个算符(“+”、“-”、“*” 或 “/”),或是在范围 [-200, 200] 内的一个整数

思路

用循环遍历整个字符串数组,如果当前字符为数字,则入栈;如果当前字符为运算符,则将栈中的两个数字弹出,根据运算符参与相应的运算。最后栈当中会剩余一个最终结果,return返回这个结果。

代码

class Solution {
    public boolean isOperation(String tmp) {
    return tmp.equals("+") || tmp.equals("-") ||tmp.equals("*") ||tmp.equals("/");
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            String tmp = tokens[i];
            if(!isOperation(tmp)) {
                stack.add(Integer.valueOf(tmp));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (tmp) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
}

3. 栈的压入、弹出序列

题目链接:栈的压入、弹出序列

题目

描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000
  2. -1000<=pushV[i]<=1000
  3. pushV 的所有数字均不相同

示例1

输入:[1,2,3,4,5],[4,5,3,2,1]

返回值:true

说明:可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列,返回true

示例2

输入:[1,2,3,4,5],[4,3,5,1,2]

返回值:false

说明:
由于是[1,2,3,4,5]的压入顺序,[4,3,5,1,2]的弹出顺序,要求4,3,5必须在1,2前压入,且1,2不能弹出,但是这样压入的顺序,1又不能在2之前弹出,所以无法形成的,返回false

思路

  1. 定义一个整型变量j用于指示出栈数组popV的位置,初始化为0;定义一个Stack对象stack来模拟入栈过程。
  2. 使用循环遍历入栈数组pushV,
  3. 如果当前入栈元素不等于出栈数组popV中指针j所指向的元素,则将当前入栈元素压入栈stack中。
  4. 如果当前入栈元素等于出栈数组popV中指针j所指向的元素,则进行出栈操作:
  5. 将指针j向后移动一位,表示出栈数组中的下一个元素。
  6. 检查栈顶元素是否与popV[j]相等,如果相等,则继续出栈,直到栈为空或者栈顶元素与popV[j]不相等。
  7. 判断最终栈是否为空:遍历结束后,如果栈为空,则说明入栈和出栈顺序是匹配的,返回true;否则返回false。

代码

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int[] pushV, int[] popV) {
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < pushV.length; i++) {
            if(pushV[i] != popV[j]) {
                stack.push(pushV[i]);
            } else {
                j++;
                while(!stack.isEmpty() && j < popV.length && popV[j] == stack.peek()) {
                    j++;
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }
}

结语

栈的特点:先进后出

有两种实现栈的方法,我该用哪个?

如果存储空间的大小事先已知且固定,并且对栈的操作效率要求较高,可以选择顺序栈。如果存储空间的大小不确定,或者频繁地进行插入和删除操作,并且对栈的大小没有严格的限制,可以选择链栈。


都看到这里啦!真棒(*^▽^*)

可以给作者一个免费的赞赞吗,这将会鼓励我继续创作,谢谢大家

编程小白写作,如有纰漏或错误,欢迎指正


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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3+vite 模板vue3-element-admin框架如何关闭当前页面跳转 tabs

使用模版: 有来开源组织 / vue3-element-admin 需要关闭的.vue 页面增加以下方法 //setup 里import {LocationQuery, useRoute, useRouter} from "vue-router"; const router useRouter(); function close() {console.log(|--router.currentRoute.value, router.cur…

【MySQL系列】使用 ALTER TABLE 语句修改表结构的方法

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

每日一题 第六十三期 洛谷 树状数组模板

【模板】树状数组 1 题目描述 如题&#xff0c;已知一个数列&#xff0c;你需要进行下面两种操作&#xff1a; 将某一个数加上 x x x 求出某区间每一个数的和 输入格式 第一行包含两个正整数 n , m n,m n,m&#xff0c;分别表示该数列数字的个数和操作的总个数。 第二…

4.2 JavaWeb Day05分层解耦

三层架构功能 controller层接收请求&#xff0c;响应数据&#xff0c;层内调用了service层的方法&#xff0c;service层仅负责业务逻辑处理&#xff0c;其中要获取数据&#xff0c;就要去调用dao层&#xff0c;由dao层进行数据访问操作去查询数据&#xff08;进行增删改查&…

YOLOv8结合SCI低光照图像增强算法!让夜晚目标无处遁形!【含端到端推理脚本】

这里的"SCI"代表的并不是论文等级,而是论文采用的方法 — “自校准光照学习” ~ 左侧为SCI模型增强后图片的检测效果,右侧为原始v8n检测效果 这篇文章的主要内容是通过使用SCI模型和YOLOv8进行算法联调,最终实现了如上所示的效果:在增强图像可见度的同时,对图像…

Scala中如何使用Jsoup库处理HTML文档?

在当今互联网时代&#xff0c;数据是互联网应用程序的核心。对于开发者来说&#xff0c;获取并处理数据是日常工作中的重要一环。本文将介绍如何利用Scala中强大的Jsoup库进行网络请求和HTML解析&#xff0c;从而实现爬取京东网站的数据&#xff0c;让我们一起来探索吧&#xf…

【容易不简单】love 2d Lua 俄罗斯方块超详细教程

源码已经更新在CSDN的码库里&#xff1a; git clone https://gitcode.com/funsion/love2d-game.git 一直在找Lua 能快速便捷实现图形界面的软件&#xff0c;找了一堆&#xff0c;终于发现love2d是小而美的原生lua图形界面实现的方式。 并参考相关教程做了一个更详细的&#x…

C++算法——滑动窗口

一、长度最小的子数组 1.链接 209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 2.描述 3.思路 本题从暴力求解的方式去切入&#xff0c;逐步优化成“滑动窗口”&#xff0c;首先&#xff0c;暴力枚举出各种组合的话&#xff0c;我们先让一个指针指向第一个&…

【Qt学习笔记 01】Qt 背景介绍

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt 背景介绍 文章编号&#xff1a;Qt 学习笔记 / 01 文章目录 Qt 背景…

AttributeError: ‘Namespace‘ object has no attribute ‘EarlyStopping‘

报错原因 这个报错信息表明在Python脚本train.py中尝试访问命令行参数args.EarlyStopping时出错&#xff0c;具体错误是AttributeError: Namespace对象没有名为EarlyStopping的属性。 在Python的argparse模块中&#xff0c;当我们通过命令行传递参数并解析时&#xff0c;解析…

UGUI 进阶

UI事件监听接口 目前所有的控件都只提供了常用的事件监听列表 如果想做一些类似长按&#xff0c;双击&#xff0c;拖拽等功能是无法制作的 或者想让Image和Text&#xff0c;RawImage三大基础控件能够响应玩家输入也是无法制作的 而事件接口就是用来处理类似问题 让所有控件都…

10秒钟用python接入讯飞星火API(保姆级)

正文&#xff1a; 科大讯飞是中国领先的人工智能公众公司&#xff0c;其讯飞星火API为开发者提供了丰富的接口和服务&#xff0c;以支持各种语音和语言技术的应用。 步骤一&#xff1a;注册账号并创建应用 首先&#xff0c;您需要访问科大讯飞开放平台官网&#xff0c;注册一个…

dcoker 下redis设置密码

修改Docker里面Redis密码 Redis是一个开源的内存数据结构存储系统&#xff0c;常用于缓存、消息队列和数据持久化等场景。在使用Docker部署Redis时&#xff0c;默认情况下是没有设置密码的&#xff0c;这可能会导致安全隐患。因此&#xff0c;为了保证数据的安全性&…

2024环境,资源与绿色能源国际会议(ICERGE2024)

2024环境&#xff0c;资源与绿色能源国际会议(ICERGE2024) 会议简介 2024环境、资源与绿色能源国际会议(ICERGE2024)将于2024年在三亚举行。该会议是一个围绕环境、资源与绿色能源研究领域的国际学术交流活动。 会议主题包括但不限于环境科学、环境工程、资源利用、绿色能源开…

微信小程序上传代码到远程仓库

个人介绍 hello hello~ &#xff0c;这里是 code袁~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的…

MySQL安装卸载

目录 1.概述 2.安装 2.1.安装 2.2.配置 3.卸载 3.1.停服务 3.2.卸载组件 3.3.删除安装目录 3.4.删除数据目录 3.5.检查残留 1.概述 MySQL是一个广受欢迎的关系型数据库管理系统&#xff0c;最初由瑞典的MySQL AB公司开发&#xff0c;现在是Oracle旗下的产品。作为最流…

海外媒体宣发技巧解析从而提升宣发效果

在当今全球化的媒体环境下&#xff0c;海外媒体宣发是企业和品牌推广的重要手段。然而&#xff0c;要在海外市场取得成功&#xff0c;一味地复制国内的宣发策略是行不通的。要想提升宣发效果&#xff0c;就必须了解并掌握一些海外媒体宣发的技巧。世媒讯一家从事海内外媒体的推…

1111111

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…

【中文视觉语言模型+本地部署 】23.08 阿里Qwen-VL:能对图片理解、定位物体、读取文字的视觉语言模型 (推理最低12G显存+)

项目主页&#xff1a;https://github.com/QwenLM/Qwen-VL 通义前问网页在线使用——&#xff08;文本问答&#xff0c;图片理解&#xff0c;文档解析&#xff09;&#xff1a;https://tongyi.aliyun.com/qianwen/ 论文v3. : 一个全能的视觉语言模型 23.10 Qwen-VL: A Versatile…

简直了,被“Java并发锁”问题追问到自闭...

分享是最有效的学习方式。 博客&#xff1a;https://blog.ktdaddy.com/ 故事 地铁上&#xff0c;小帅双目空洞地望着窗外…绝望&#xff0c;发自内心地感到绝望… 距离失业已经过去两个月了&#xff0c;这是小帅接到的第四次面试邀请。“回去等通知吧…”,简简单单的六个字&a…