对于数据结构！真的不是一般的难！！太难了！！

之前写过几十道链表，顺序表相关的练习题！感觉也就那样吧！！但是，现如今，接触到堆和队列，二叉树等，发现原来数据结构真的不是一般的难度！！！对自己的能力表示深深的怀疑中……

上面仅仅是部分的吐槽阶段，但是，作为Java领域的新星！必须要努力学！！那么开始，言归正传：进入今日的主题吧！！

150. 逆波兰表达式求值

给你一个字符串数组 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] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

对于上述题目题干部分想必大家已经看懂了吧！！对于逆波兰表达式，我们在百度百科中有：

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法[1] 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。 原文链接为：https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F/9841727感兴趣的各位老铁，可以进去看一下！！

下面请看笔者的代码为：

import java.util.Stack;public class Solution {public int evalRPN(String[] tokens){Stack stack =new Stack<>();for (String x:tokens) {if (!isOperation(x)){//不是运算符stack.push(Integer.parseInt(x));//x是String类型，需要转换为整型}else {int num1=stack.pop();int num2=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();}//判断是否为运算符！private boolean isOperation(String x){if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")){return true;}return false;}
}

其实对于该代码并不是很难，主要难点还是在于：思路！！逆波兰表达式是什么？？想必这个是很多人都没有接触到的知识概念！！

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

提示：

• 1 <= s.length <= 104

• s 仅由括号 '()[]{}' 组成

经过上述的题目分析，我们可以得出：

我们可以进行一下分析：

1. 应用栈的方式，把左括号放入栈里，遇到右括号就出栈，进行比较！

2. 左括号多：字符串遍历完成，但是栈不空

3. 右括号多，字符串没完，栈空了！

4. 不匹配

经过上述的分析，我们有着如下的简单代码：

//栈里面放的一定是左括号public boolean isValid(String s){Stack 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 ch2=stack.peek();//偷看——》左括号if (ch==')'&&ch2=='(' || ch=='}' && ch2=='{'||ch==']'&&ch2=='['){stack.pop();//先匹配在出栈}else {return false;//不匹配}}}if (!stack.empty()){//遍历完成，判断栈是否为空return false;}return true;}

经过上述的代码，想必大家能够理解笔者的思路了吧！！

剑指 Offer 31. 栈的压入、弹出序列

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

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出：true

解释：我们可以按以下顺序执行：

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

输出：false

解释：1 不能在 2 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000

2. 0 <= pushed[i], popped[i] < 1000

3. pushed 是 popped 的排列。

对于这个题目，我们需要知道的是：在入栈的时候，可以出栈！！这种，向来是我们进行考研，或者期末考试的主要解题！！

解题思路：以popped为模板，依次按照pushed的顺序push(压栈），同时，判断栈顶是否与模板popped指向的相同？相同则出栈不同则继续！！

   public boolean isPopOrder(int[] pushed , int[] popped){Stack stack=new Stack<>();int j=0;for (int i = 0; i < pushed.length; i++) {//遍历数组stack.push(pushed[i]);//放入栈while (j

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素val推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

提示：

• -231 <= val <= 231 - 1

• pop、top 和 getMin 操作总是在 非空栈 上调用

• push, pop, top, and getMin最多被调用 3 * 104 次

思路:开辟一个栈：minStack最小栈，当普通栈放入元素的时候，判断最小栈是否为空，若最小栈为空，则最小栈与普通栈都放入第一个元素，若最小栈不为空，则在普通栈放入元素的时候，通过将要放入的元素与最小栈已有的元素进行比较，若<=，则放入最小栈中…………

import java.util.Stack;public class MinStack {//最小栈private Stack stack;//普通栈private  Stack minStack;//最小栈public MinStack(){//初始化栈对象stack=new Stack<>();minStack=new Stack<>();}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(){//出栈if (!stack.empty()){//栈不为空Integer val=stack.pop();//普通栈的元素出栈//维护最小栈if (val.equals(minStack.peek())){minStack.pop();}}}public int top(){if (!stack.empty()){//普通栈return stack.peek();}return -1;}public int getMin(){//拿到最小值return minStack.peek();}}

经过上面代码的分析：我们可以看出来：一个栈达不到目的，就用两个栈！！