【数据结构与算法】栈—模拟实现Stack和栈相关算法题

水深无声 2023-09-27 13:26 32阅读 0赞

#### 文章目录 ####

*  栈的定义
 *  Stack模拟实现
 *  相关算法题
 *   *  1.栈的压入弹出序列
     *  2.逆波兰表达式(后缀表达式)⭐
     *   *  1.什么是逆波兰表达式?
         *  如何转换成逆波兰表达式
         *  逆波兰表达式如何计算
     *  3.有效的括号
 *  总结

## 栈的定义 ##

> 栈作为一种数据结构，是一种**只能在一端进行插入和删除操作的特殊线性表**。它按照**后进先出(先进后出)的原则存储数据**，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

在Java的集合类中栈是Stack  
它的底层是一个数组,所以模拟实现就用数组来实现  
当然栈分为顺序栈和链式栈,也可以使用链表的方式来实现

## Stack模拟实现 ##

![在这里插入图片描述][af343c35e8fa4bd18f9a49fee437653d.png]  
Stack中有以上这些方法:

*  push() :把数据压入堆栈顶部。
 *  pop() :移除堆栈顶部的对象，并作为此函数的值返回该对象。
 *  peek() :查看堆栈顶部的对象，但不从堆栈中移除它。
 *  empty() : 判断堆栈是否为空
 *  search() : 查找数据并返回对应的下标

import java.util.Arrays;
    //数组实现栈
    public class MyStack {
        
    
        public int[] elem;
        public int usedSize;
        public static final int DEFAULT_SIZE = 10;
    
        public MyStack() {
        
            this.elem = new int[DEFAULT_SIZE];
        }
    
        /**
         * 弹出
         * @return
         */
        public int pop(){
        
            if(empty()){
        
                throw new Myemptyexption("栈为空!");//自定义异常
            }
            return this.elem[--usedSize];
        }
    
        public boolean empty(){
        
            if(this.usedSize == 0){
        
                return true;
            }
            return false;
        }
        
        /**
         * 压栈
         * @return
         */
        public int push(int val){
        
            if(!isFull()){
        
                this.elem = Arrays.copyOf(this.elem,2*elem.length);
            }
            this.elem[this.usedSize] = val;
            this.usedSize++;
            return val;
        }
    	//判断数组是否满了
        public boolean isFull(){
        
            if(this.usedSize == this.elem.length){
        
                return true;
            }
            return false;
        }
        
        /**
         *返回栈顶元素
         * @return
         */
        public int peek(){
        
            if(empty()){
        
                throw new Myemptyexption("栈为空!");
            }else{
        
                return this.elem[usedSize-1];
            }
        }
        
        /**
         * 查找元素对应的下标
         * @param val
         * @return
         */
        public int search(int val) {
        
            for (int i = 0; i < usedSize; i++) {
        
                if (this.elem[i] == val) {
        
                    return i;
                }
            }
            return -1;
        }
    }

上面的代码是实现栈的主体部分,其中还用自定义异常  
自定义异常代码如下:

public class Myemptyexption extends RuntimeException{
        
        public Myemptyexption() {
        
            super();
        }
        public Myemptyexption(String message) {
        
            super(message);
        }
    }

运行并测试如图:  
![在这里插入图片描述][28d4bf4f113a4acea4f0d57be61e9cca.png]  
以上只是我自己模拟实现栈的想法,不一定和Stack底层源码的思路一样,大家如果要研究Stack的底层,还是建议去看官方源码

## 相关算法题 ##

要真正掌握知识最重要还是刷题,接下来有几道栈相关的算法题,一起看看吧

### 1.栈的压入弹出序列 ###

题目链接:[传送门][Link 1]

> 描述  
> 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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

解题思路:  
创建一个栈,先将push数组中的元素依次进行入栈,入栈后栈顶元素要和pop数组的元素进行比较,如果相等就出栈,pop数组指向下一个元素,继续比较如果不相等再次入栈,直到结束.最后对栈进行判断如果空就为true 如果不为空就是false

public boolean IsPopOrder(int [] pushA,int [] popA) {
        
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for (int i = 0; i < pushA.length; i++) {
        
                stack.push(pushA[i]);
                while(j < popA.length && !stack.empty() && stack.peek()==popA[j]){
        
                    j++;
                    stack.pop();
                }
            }
            return stack.empty();
        }

![在这里插入图片描述][b88b44c4d08649ad8ba3b56e4a52304e.png]

### 2.逆波兰表达式(后缀表达式)⭐ ###

题目链接:[传送门][Link 2]

> 根据 逆波兰表示法，求表达式的值。
> 
> 有效的算符包括 +、-、\*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。  
> 注意 两个整数之间的除法只保留整数部分。  
> 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

> 示例 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.什么是逆波兰表达式? ####

> 逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法

> 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b) \* (c+d)转换为ab+cd+ \*

其中 (a+b) \* (c+d) 这样的表达式是中缀表达式 ,而转换后的 ab+cd+\* 是后缀表达式(逆波兰表达式)

#### 如何转换成逆波兰表达式 ####

先给大家介绍如何将中缀表达式转换为后缀表达式  
最简单最粗暴的方式就是从左到右为每一步的运算加括号.如何改变运算符的位置  
![在这里插入图片描述][8717a35f1f9c4238a3ae1ed23eb2ecd1.png]  
上面的式子大家可以逐个去除括号  
先算的是 b\*c 和 d/ f 所以 \* 移到bc的后面 / 移到df的后面然后类似依次进行去除

#### 逆波兰表达式如何计算 ####

逆波兰表达式的计算就要用的栈了  
`方法如下: 将后缀表达式的数字进行入栈操作,然后遇到运算符就从栈里面弹出两个元素,再将计算好的数放回栈里面,以此类推`  
例如示例1的:2,1,+,3, \*  
2 1先入栈 然后是+ 1 2出栈进行相加为3 再入栈 下一个3也入栈 后面是\* 因此两个3再出栈进行相乘 结果就为9  
`注意:在出栈时第一个数作为右操作数,第二个为左操作数 不能交换顺序,如果交换 运算符两侧的数就会变 ,此时如果是+ 的话结果不变 ,但如果不是结果就会出错`

接下来就是用代码来实现计算过程了  
代码实现:

public int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack<>();
            for (String x:tokens){
        
                if (!isOperation(x)) {
        
                    stack.push(Integer.parseInt(x));
                } else {
        
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch (x){
        
                        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();
        }
        public boolean isOperation(String s){
        
            if(s.equals("+") || s.equals("-") ||s.equals("*") ||s.equals("/")){
        
                return true;
            }
            return false;
        }

![在这里插入图片描述][0e0c162f2ae84723bc7b3de04ce48cc1.png]

### 3.有效的括号 ###

题目链接:[传送门][Link 3]

> 给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。
> 
> 有效字符串需满足：
> 
> 1.  左括号必须用相同类型的右括号闭合。
> 2.  左括号必须以正确的顺序闭合。
> 3.  每个右括号都有一个对应的相同类型的左括号。

> 示例 1：  
> 输入：s = “()”  
> 输出：true

> 示例 2：  
> 输入：s = “()\[\]\{\}”  
> 输出：true

> 示例 3：  
> 输入：s = “(\]”  
> 输出：false

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

`解题思路`:首先将元素进行入栈操作,从第二开始,入栈前要与栈顶元素进行匹配,如果能构成一个完成的括号,就出栈.因此如果字符串遍历完成,栈里面元素为空,就是匹配成功,  
**注意**:因为这里是三个括号,不能通过左括号和右括号的数量进行判断  
代码实现如下:

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;
                    }
                    char top = stack.peek();
                    if(ch==')'&&top=='(' || ch=='}'&&top=='{' || ch==']'&&top=='['){
        
                        //当前括号是匹配的 就出栈
                        stack.pop();
                    }else{
        
                        //不匹配
                        return false;
                    }
                }
            }
            if(stack.empty()){
        
                return true;
            }else {
        
                return false;
            }
        }

![在这里插入图片描述][9f959c3f48e04437bdb4c9d51bfa8262.png]

## 总结 ##

*  栈的实现方式有很多种,我是用数组来实现的,也可以用链表来实现
 *  栈虽然比较简单,但是它的算法题不一定简单,算法题还是建议多做几遍
 *  中缀表达式如何转逆波兰表达式(后缀表达式),又如何去进行计算这部分要掌握(很重要)

![在这里插入图片描述][c498ecb070ec44e8b4e8232983c60a64.png_pic_center]

[af343c35e8fa4bd18f9a49fee437653d.png]: https://img-blog.csdnimg.cn/af343c35e8fa4bd18f9a49fee437653d.png
[28d4bf4f113a4acea4f0d57be61e9cca.png]: https://img-blog.csdnimg.cn/28d4bf4f113a4acea4f0d57be61e9cca.png
[Link 1]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[b88b44c4d08649ad8ba3b56e4a52304e.png]: https://img-blog.csdnimg.cn/b88b44c4d08649ad8ba3b56e4a52304e.png
[Link 2]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/
[8717a35f1f9c4238a3ae1ed23eb2ecd1.png]: https://img-blog.csdnimg.cn/8717a35f1f9c4238a3ae1ed23eb2ecd1.png
[0e0c162f2ae84723bc7b3de04ce48cc1.png]: https://img-blog.csdnimg.cn/0e0c162f2ae84723bc7b3de04ce48cc1.png
[Link 3]: https://leetcode.cn/problems/valid-parentheses/
[9f959c3f48e04437bdb4c9d51bfa8262.png]: https://img-blog.csdnimg.cn/9f959c3f48e04437bdb4c9d51bfa8262.png
[c498ecb070ec44e8b4e8232983c60a64.png_pic_center]: https://img-blog.csdnimg.cn/c498ecb070ec44e8b4e8232983c60a64.png#pic_center