数据结构——栈的实现（java实现）与相应的oj题

🕗 发布于 2024-07-21 16:44 数据结构 开发语言

一栈

栈的概念:

栈也是一种线性表，栈只允许在表的一端进行插入与删除操作，所以栈中数据的特征的先进后出（先进来的后出去）。
栈顶：是栈进行插入与删除操作的表的一端
栈底：不允许插入删除操作的一端
压栈：将数据插入到栈中
出栈：将数据移除栈
在这里插入图片描述

栈的实现：

栈的底层可以由数组实现，也可以由链表实现
栈由数组实现时，栈的压栈与出栈的时间复杂度均为O（1）。
栈由单链表实现时，
如果采用尾插法，压栈操作时间复杂度为O（n）,如果有last指针，则
压栈时间复杂度为O(1),但是出栈的时间复杂度一定为O（n）。
如果采用头插法，则压栈与出栈的时间复杂度均为O（1）.
栈由双链表实现时，不论采用头插法与尾插法，时间复杂度均为O(1)。

栈的数组实现

当栈使用数组实现时，栈的插入与删除操作，时间复杂度均为O（1）；

public class MyStack {
    static   int  DEFAULT_SIZE  = 10; //设置默认的数组大小
    private   int [] element ;        //实现栈的数组
    int usedsize = 0 ;                //栈中有效元素的个数
//默认构造方法
public MyStack() {}
//入栈
    public void push(int val) {}
//出栈
    public int pop() {}
    //获取栈顶元素 但是不删除
    public int peek() { }
     //获取栈元素个数
    public int size(){} 
    //判空
    public boolean isEmpty() { }       
}

默认构造方法

默认申请10个空间

public MyStack(){
        this.element = new int[10];
    }

压栈

思想：先判断栈满没满，如果满了则扩容，然后进行压栈

  public void push(int data){
        //先判断栈是否有空间
        if(usedsize==element.length){
            //如果没有空间
            //则扩容
            this.element = Arrays.copyOf(element,2*element.length);
        }
        //保证空间后
       this.element[usedsize++] = data;
  }

获取栈元素的个数

思想：直接返回usedsize

 public int size(){
        return usedsize;
    }

出栈

思想：先判断栈是否为空，为空则抛出异常，不为空，则返回栈顶元素值，并且usedsize-1.

  public int pop(){
        //要判断栈是否为空，如果为空，则退出
      try{
          if (isEmpty()) {
              //2. 问题出现,构造参数的形参问题，super()调用父类的构造方法
              throw new EmptyException("EmptyException异常报错");
          }
      }catch (EmptyException e){
              e.printStackTrace();
      }
        int val =   this.element[usedsize-1];
        usedsize -- ;
        return val;
    }

获取栈顶元素

思想：与出栈逻辑相同，只是usedsize值不需-1 。

 public int  peek(){
        try{
            if (isEmpty()) {
                throw new EmptyException("EmptyException异常报错");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return    this.element[usedsize-1];
    }

判断当前栈是否为空

思想：直接判断usedsize 是否为0即可。

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

java提供的Stack类

在这里插入图片描述

Stack实现的接口：

在这里插入图片描述

  接口说明   1.  继承Cloneable接口支持克隆
  其他接口，暂时还没搞明白，以后更新补充

LinkedList也可以当Stack使用

java提供的LinkedList类也可以当做栈来使用，LinkedList的方法列表如下：
在这里插入图片描述

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> stack =  new LinkedList<>();
        stack.push(5);
        stack.push(2);
        stack.pop();
        stack.pop();
        stack.pop();
    }
}

在这里插入图片描述

虚拟机栈，栈帧，栈的三个概念

虚拟机栈是JVM中的一块内存。
栈帧是为一个方法，函数分配的内存。
栈是一种数据结构。

二栈的一些算法题：

（1）逆序打印单链表。

采用递归的方法：

// 递归方式
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 + " ");
   }
}

（2）括号匹配

题解：1 . 对于这个题无法直接看出其数学模型，必须先画图，列出各种情况，再判断
在这里插入图片描述
从图中可以分析出，要实现判断括号匹配

就要使得每一个左括号和右括号能够与对应位置的右括号进行匹配判断
且当所有的左括号（右括号）判断完时，其对应的右括号（左括号）也判断完毕，即满足左括号个数与右括号个数相当的情况。
如果第一个括号是右括号，说明此括号没有对应的左括号，说明一定为字符串一定括号不匹配。

实现思想：遍历字符串，遇到左括号则存入栈中，遇到右括号则与栈顶元素比较，相匹配，则继续循环，如果不匹配或栈为空，则返回false。

class Solution1 {
    public boolean isValid(String s) {
        Stack <Character> stack = new Stack<>();
       //采用for循环，这样可以找到字符串中的字符
        for(int i =0;i<s.length();i++) {
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') {
                //问题，java提供的栈是否需要手动扩容？
                stack.push(ch);
            } else {
                //如果是右括号的内容
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char ch2 = stack.peek();   //当获取栈顶元素时，栈可能为空
                    //栈区不能为空
                    if (((ch == '}' && ch2 == '{') || (ch == ']' && ch2 == '[') || (ch == ')' && ch2 == '('))) {
                        //说明匹配，
                        //将栈顶的元素去除
                        stack.pop();
                    } else {
                        //如果不匹配，情况1 如果栈中还没有左括号，则一定不匹配，
                        return false;
                    }
                }
            }
        }
         // 如果栈表为空，说明匹配完毕
        if(stack.isEmpty()){
            return true;
        }
       return false;
    }
}

（3）逆波兰表达式求值

逆波兰表达式

逆波兰表达式即后缀表达式，后缀表达式是由中缀表达式转换而成。
所谓中缀表达式即我们平常所写的±*/的算式
我们平常所写的中缀表达式中是有优先级的，即先乘除，后加减，有括号先算括号里面的
但是计算机是不能够识别优先级的，为了能够使计算机计算，我们将中缀表达式的规则
表达成后缀表达式的形式，这样计算机便能够计算算式。

中缀表达式转换成后缀表达式的的规则：

先将中缀表达式中能够加括号的部分都加上括号
然后将所有的运算符移到所在最近扩号之外。
然后去除掉所有括号即得到后缀表达式。

后缀表达式的运算规则：
遍历整个表达式，遇到运算符时，则将运算符前面的两个数作为操作数计算
得出的结果替代两个操作数，然后继续遍历表达式，循环上次操作。

在这里插入图片描述
本题：只是要求按照后缀表达式的规则计算结果
实现思想：遍历表达式，遇到操作数即将操作数压入栈中，遇到运算符，则进行两次出栈
，获取两个操作数进行计算（需要注意的是第一次出栈的是右操作数，第二次出栈的是左操作数）
然后将计算的结果再进行压栈，然后循环此操作。

class Solution {
    public int evalRPN(String[] tokens) {
        //创建一个栈，创建栈时不需要考虑栈的空间大小
        Stack<Integer> stack = new Stack<>();
        //采用foreach进行遍历栈
        for (String str : tokens) {
            if (!isOperator(str)) {
                int a = Integer.parseInt(str);
                stack.push(a);
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                //如果为运算符
                switch (str) {
                    case "+" : stack.push(val1 + val2);
                        break;
                    case "-" :  stack.push(val1 - val2);
                         break;
                    case "*" : stack.push(val1 * val2);
                         break;
                    case "/" : stack.push(val1 / val2);
                        break;
                }
            }
        }
        return stack.peek();
    }

总结
1. 字符串形式的运算符不能直接转换成运算符
2. 后缀表达式先进栈的是左操作数，后进栈的是右操作数，当我们需要出栈时，第一次获取栈顶元素是右操作数，第二次获取栈顶元素才是左操作数。

（4）出入栈次序匹配

在这里插入图片描述

class Solution2{
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i< pushV.length;i++) {
            stack.push(pushV[i]);
            while(!stack.empty() && j < popV.length &&
                    stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }

        return stack.empty();
    }
}

（5）最小栈

题解：
如果只用一个栈的话，我们不可能实现题目的要求，只有能将栈的最小值时刻储存起来才能实现题目的要求。因此我们实现两个栈，一个栈用于存储数据，另一个最小栈用于存放栈当前的最小值。

在这里插入图片描述实现思想：入栈的规则：

普通栈一定要放，最小栈如果为空，或者栈顶元素小于压入的数据，则放入最小栈中
如果压入的数据与最小栈栈顶元素相当，也放入最小栈中。（因为最小栈中的元素必须与普通栈的最小值保持同步即必须与出栈的规则相匹配）。
出栈的规则：
如果普通栈的栈顶元素与最小栈栈顶元素相同，则最小栈也需要出栈。

class MinStack {
   //创建两个栈
   Stack <Integer> stack  =  new Stack<>(); //普通栈
   Stack <Integer> minStack = new Stack<>();//最小栈
    public MinStack() {
    }
public void push(int val) {
         //压栈，压入数据
         //普通栈一定要压入
         stack.push(val);
         //然后判断最小栈是否压入
         if(minStack.empty()){
            minStack.push(val);
         }else{
            if(val<=minStack.peek()){
                 minStack.push(val);
            }
         }
  }
  public void pop() {
          //出栈
          //普通栈一定出栈
             int val =  stack.pop();
          //最小栈出栈：
          //如果两栈的栈顶元素相同，则出栈
          if(val == minStack.peek()){
            minStack.pop();
          }
    }
    public int top() {
            //获取栈顶元素
            if(!stack.empty()){
                   return stack.peek();
            }
            return -1 ;
    }
    public int getMin() {
           if(minStack.empty()){
            return -1;
           }
           return minStack.peek();
    }
    }

总结：

在使用栈时，最常用的运用是根据栈先进后出的特性，将一段有序的数据转为逆序后，再进行操作使用。

原文地址：https://blog.csdn.net/2301_77993957/article/details/140461194

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【面试题】数据结构：顺序表和链表的区别？
下一篇：Redis 散列

PL/SQL执行.sql文件
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/iamlzyoco/article/det
阅读更多2024-11-14
PyAEDT：Ansys Electronics Desktop API 简介
在本文中，我将向您介绍 PyAEDT，这是一个 Python 库，旨在增强您对 Ansys Electronics Desktop 或 AEDT 的体验。通过利用 PyAADT 的强大功能，您可以将分
阅读更多2024-11-14
Python从0到100（七十二）：Python OpenCV-OpenCV实现手势音量控制（文末送书）
本次实验需要使用OpenCV和mediapipe库进行手势识别，并利用手势距离控制电脑音量。cv2：OpenCV库，用于读取摄像头视频流和图像处理。mediapipe：mediapipe库，用于手部关
阅读更多2024-11-14
YOLOv11多模态结合CFT模块融合可见光+红外光双输入
这期是在上期YOLOv10的基础上，使用YOLOv11结合Transformer复现了论文《Cross-Modality Fusion Transformer for Multispectral Ob
阅读更多2024-11-14
鸿蒙学习生态应用开发能力全景图-三方库（3）
鸿蒙生态三方库，是在鸿蒙系统上可重复使用的软件库，可帮助开发者重用技术资产，快速开发鸿蒙生态应用、元服务，提升开发效率。鸿蒙生态中心仓聚合了丰富的鸿蒙生态开发三方库，方便开发者一站式获取。 C/C+
阅读更多2024-11-14
android studio新建activity提示 require androidX support
在Android Studio中创建Activity时出现的“require androidX support”提示通常意味着你的项目配置需要使用AndroidX库来支持。AndroidX是原Andr
阅读更多2024-11-14
Brave127编译指南 Windows篇：部署depot_tools（三）
在下一篇文章《Brave127编译指南 Windows篇：配置Git（四）》中，我们将详细讲解如何在Windows系统上安装和配置Git，为您的开发工作提供全面的版本控制支持。在Brave浏览器的编译
阅读更多2024-11-14
去地面算法——depth_clustering算法调试（1）
depth_clustering算法调试
阅读更多2024-11-14
网络安全与零信任架构：构建新一代信息保护体系
作为一种全新的网络安全理念，零信任架构（Zero Trust Architecture, ZTA）重新定义了信息保护的方式，强调对所有访问请求的验证与监控，以实现更高的安全性。而零信任架构是当前网络安
阅读更多2024-11-14
【3D Slicer】的小白入门使用指南四
● 开放解剖（OA）浏览器是由神经影像分析中心开发的，基于网络浏览器技术构建的图谱查看器。● OA浏览器将解剖模型和分割图像与语义信息结合起来。本教程提供了对OA浏览器技术的介绍。本教程中的示例基于S
阅读更多2024-11-14

数据结构——栈的实现（java实现）与相应的oj题

文章目录

一 栈

栈的概念:

栈的实现：

栈的数组实现

默认构造方法

压栈

获取栈元素的个数

出栈

获取栈顶元素

判断当前栈是否为空

java提供的Stack类

Stack实现的接口：

LinkedList也可以当Stack使用

虚拟机栈，栈帧，栈的三个概念

二 栈的一些算法题：

（1） 逆序打印单链表。

（2）括号匹配

（3）逆波兰表达式求值

逆波兰表达式

（4） 出入栈次序匹配

（5）最小栈

总结：

相关文章

一栈

二栈的一些算法题：

（1）逆序打印单链表。

（4）出入栈次序匹配