【Java--数据结构】栈的应用

时间：2024-07-20 07:12:01

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

目录

将递归转化为循环

逆波兰表达式

有效的括号

栈得压入、弹出系列

最小栈

将递归转化为循环

把递归代码实现为非递归代码

比如：逆序打印链表

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

逆波兰表达式

也叫后缀表达式（运算符在操作数的后面）,好处是：忽略运算符的优先级

我们平时运算加减乘除的式子其实是 中缀表达式 

比如式子a+b*c+(d*e+f)*g转成逆波兰表达式 abc*+de*f+g*+

逆波兰表达式的运算规则：

  1. 将操作数压入栈中
  2. 遇到运算符弹出操作数（分别作为右操作数和左操作数）计算
  3. 将计算的结果压入栈中

比如式子1+2*3+（4*5+6）*7

逆波兰表达式1 2 3*4 5*6 +7 *+

  • 将1 2 3压入栈内，
  • 遇到*，取出2和3，计算2*3得6
  • 将6压入栈
  • 又遇到+，取出6和1，计算6+1得7

……

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

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

​

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<tokens.length;i++){
            String tmp=tokens[i];
            if(!isOperation(tokens[i])){
                Integer val=Integer.valueOf(tmp);//将字符转化为整形
                stack.push(val);
            }else{
                Integer val2=stack.pop();//val2作为右操作数
                Integer val1=stack.pop();
                switch(tmp){
                    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.pop();
    }
        
        //判断字符是否是 运算符
    public boolean isOperation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
}

有效的括号

oj链接

​

括号匹配：栈最终为空，且字符串已经遍历完了

不匹配：

  • 左括号与右括号不匹配    [ ( ] )
  • 字符串没有遍历完，遇到了右括号，但栈为空   (  )  ）））
  • 字符串遍历完，但栈里还有左括号（（（  ）
  • 右括号在前面 ）（（
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.push(ch);
            }else{
                //遇到右括号
                if(stack.empty()){
                    return false;//栈为空，没有左括号与之匹配
                }else{
                    //取栈顶元素左括号 看与当前右括号是否匹配
                    char chL=stack.peek();
                    if(chL=='('&&ch==')'
                    ||chL=='['&&ch==']'
                    ||chL=='{'&&ch=='}'){
                        stack.pop();//说明当前这个括号匹配，所以要扔出去
                    }else{
                        return false;
                    } 

                }
            }
        }
        return stack.empty();//如果循环走完，栈为空，返回真
    }
}

栈得压入、弹出系列

oj链接

​

1. 遍历pushV数组，入栈，每次入栈后判断和popV数组的下标j是否一致

2.不一样,继续i++（继续进栈）；

一样,出栈，j++

3.出栈时，若一直一样就一直出，遇到不一样的，i++继续入栈；

注意：

  1. j的条件：不能越界（超过popV的长度）
  2. 栈不能为空
  3. stack.peek()==popV[j] 引用类型时要用equals判断，这里为简单类型int.
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(j<popV.length&&!stack.empty()&&
            stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

最小栈

oj链接

​

 分别创建两个栈：普通栈 和 最小栈

push存放元素的过程：

  1. 如果是第一次存放元素，普通栈和最小栈都得存放元素；
  2. 如果不是第一次存放，普通栈里放，需要比较的普通栈的栈顶元素和最小栈的，只有小于等于才能放入最小栈里。

pop取元素的过程（返回值是普通站的元素）：

每次pop元素时需要判断出栈的元素是不是和最小栈的栈顶元素一样，若一样，最小栈也得pop

top瞄一眼（相当于peek，返回的是普通栈的值）

getMin获取最小栈的栈顶元素

import java.util.Stack;

class MinStack {
    public Stack<Integer> stack;
    public Stack<Integer> minStack;

    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            Integer peekVal=minStack.peek();
            if(val<=peekVal){
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if (stack.empty()) {
            return;
        }
        int popVal=stack.pop();
        if(popVal==minStack.peek()){
            minStack.pop();
        }

    }
    
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

相关文章