当前位置： 首页 > article >正文

数据结构(Java版)第十期：栈和队列(一)

article 2025/1/20 12:59:11

专栏：数据结构(Java版)

个人主页：手握风云

目录

一、栈

1.1. 栈的概念

1.2. 栈的使用

1.3. 栈的模拟实现

二、栈的经典面试题

2.1. 逆波兰表达式

2.2. 有效的括号

2.3. 最小栈

一、栈

1.1. 栈的概念

       栈是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

       入栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

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

1.2. 栈的使用

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

    }
}

     我们点进去看一下Stack的源码：

public class Stack<E> extends Vector<E> {

    public Stack() {
    }

    public E push(E item) {
        addElement(item);

        return item;
    }

      下面是一些Stack的方法，我们来实现一下。

方法功能
Stack()创建一个空的栈
E push(E e)将e入栈并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素的个数
boolean empty()检查栈是否为空
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        System.out.println(stack.empty());//检查栈是否为空
        stack.push(5);//入栈
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println(stack.size());//获取栈的元素个数
        System.out.println(stack);
        System.out.println(stack.empty());
        System.out.println(stack.pop());//栈顶元素出栈
        System.out.println(stack.peek());//获取栈顶元素
    }
}

1.3. 栈的模拟实现

        Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是 Vector是线程安全的，我们可以直接用数组来实现栈。

import java.util.Arrays;

public class MyStack {
    private int[] elem;
    private int usedSize;
    private static final int DEFAULT = 10;

    public MyStack(){
        elem = new int[DEFAULT];
    }

    public void push(int val){//模拟入栈操作
        if(isFull()){//如果满了就扩容
            grow();
        }
        elem[usedSize] = val;
        usedSize++;
    }

    private void grow(){
        elem = Arrays.copyOf(elem,elem.length);
    }

    public boolean isFull(){//判断数组是否满了
        return usedSize == elem.length;
    }

    public int pop() {
        if(isEmpty()){
            throw new StackIsEmpty("栈为空");
        }
        usedSize--;//相当于把数据置为null
        return elem[usedSize-1];
    }

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

    public int peek() {
        if(isEmpty()){
            throw new StackIsEmpty("栈为空");
        }
        return elem[usedSize--];
    }

    public int size(){
        return usedSize;
    }
}
public class StackIsEmpty extends RuntimeException{
    public StackIsEmpty() {
        super();
    }

    public StackIsEmpty(String message) {
        super(message);
    }
}

public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack.size());
        int num1 = stack.pop();
        System.out.println(num1);
        int num2 = stack.peek();
        System.out.println(num2);
    }
}

二、栈的经典面试题

2.1. 逆波兰表达式

         逆波兰表达式，又称为后缀表达式，特点是运算符位于操作数之后。例如((2+1)*3)、(4+(13/5))是中缀表达式，转化为逆波兰表达式则为2 1 + 3 *、4 13 5 / +。

         本题方法参数给出的是字符串数组，我们要先将字符转化为数字。先用引用去遍历数组，如果是数字，就放入栈中；如果引用指向的是运算符，则将栈顶的两个元素出栈进行运算。如此循环往复，直至遍历完整个字符串数组。

import java.util.Stack;

public class Solution {
    public int evalRPN(String[] tokens){
        Stack<Integer> stack = new Stack<>();
        int len = tokens.length;
        for (int i = 0; i < len; i++) {//遍历字符串数组
            String str = tokens[i];
            if(!isOperator(str)){
                Integer num = Integer.valueOf(str);//将字符转化为数字
                stack.push(num);
            }else{//如果是运算符，则栈顶两个元素出栈
                Integer num1 = stack.pop();
                Integer num2 = stack.pop();
                switch (str){
                    case "+":
                        stack.push(num2+num1);
                        break;
                    case"-":
                        stack.push(num2-num1);
                        break;
                    case"*":
                        stack.push(num2*num1);
                        break;
                    case"/":
                        stack.push(num2/num1);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String val){//先判断字符串是数字还是运算符
        if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){
            return true;
        }
        return false;
    }
}

2.2. 有效的括号

        题目中要求字符串只有大、中、小括号，返回true的条件为：当我们遍历完字符串之后并且栈为空。如果说，当我们左右括号不匹配时，比如"([))"，就返回false；当我们遍历完字符串之后，如果栈不为空，也返回false，比如"(()"；当我们还没有遍历完字符串，栈已经为空，也会返回false，比如"({}))"。

import java.util.Stack;

public class Solution {
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch1 = s.charAt(i);
            if(ch1 == '{' || ch1 == '[' || ch1 == '('){
                stack.push(ch1);//将左括号入栈
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char ch2 = stack.peek();//获取入栈的左括号，与右括号进行匹配
                if((ch2=='{'&&ch1=='}') || (ch2=='['&&ch1==']') || (ch2=='('&&ch1==')')){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}

2.3. 最小栈

         如果我们抛开这道题，获取栈中的最小元素，我们就可以去遍历这个栈来找出我们的最小元素。但这道题限制我们需要在让时间复杂度为常数，所以说，一个栈是不能解决问题的，还需要在引入一个栈stack。

        对于push方法，普通栈当中，所有数据都要放入，最小栈要对我们的普通栈第一次push进行维护。如果最小栈不为空，那么需要比较刚存放的数据与最小栈栈顶的数据进行比较，以对里面的最小值进行更新。这样顺便解决了getMin的实现，直接从最小栈栈顶获取。

        对于pop方法，如果弹出的数据不是最小栈的栈顶数据，则只需要弹出普通栈的栈顶数据就行，否则则要弹出最小栈的栈顶数据。top相当于peek方法，只获取普通栈的栈顶元素。

       这4个方法基本实现完成，但还有一个问题。如上图所示，如果我们再放入一个-1进入普通栈，那么最小栈需不需要再放入-1呢？答案是需要。因为按照我们的pop方法，把-1弹出，minstack也要弹出。

完整代码：

import java.util.Stack;

public class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int peekMinVal = minStack.peek();
            if(val <= peekMinVal){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int val = stack.pop();
        if(val == minStack.peek()){
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

http://www.kler.cn/a/510699.html

相关文章：

  • 【部署】将项目部署到云服务器
  • vue集成高德地图API实现坐标拾取功能
  • 浙江安吉成新照明电器：Acrel-1000DP 分布式光伏监控系统应用探索
  • Go语言之路————条件控制：if、for、switch
  • 无人机（Unmanned Aerial Vehicle, UAV）路径规划介绍
  • 阿里云通义实验室自然语言处理方向负责人黄非：通义灵码2.0，迈入 Agentic AI
  • 【Django】多个APP设置独立的URL
  • 基于ChatGPT的论文写作辅助工具研究
  • AI 编程工具—Cursor AI 对话模式详解 内嵌对话模式
  • 【C语言】_自定义类型：联合体
  • 国产编辑器EverEdit -重复行
  • 第4章：Python TDD消除重复与降低依赖实践
  • 深度学习python基础(第一节) 变量和数据类型
  • 设计微服务的过程
  • 从Cursor到Replit Agent：AI编程技术全面综述
  • 【Python】endote参考文献格式获取,从PubMed
  • Next.js 实战 (八)：使用 Lodash 打包构建产生的“坑”？
  • 【NLP高频面题】LSTM的前向计算如何进行加速？
  • 遥感应用论文精选
  • C++ 面向对象（继承）
  • 机器学习皮马印第安人糖尿病数据集预测报告
  • C#，入门教程(03)——Visual Studio 2022编写彩色Hello World与动画效果
  • # 爬楼梯问题：常见数列的解法总结
  • 冬季深圳小览
  • Pytorch深度学习指南 卷I --编程基础（A Beginner‘s Guide） 第0章
  • “深入浅出”系列之C++：（6）CMake构建项目