【OJ】stack刷题

题目

• 1. 155. 最小栈
  • 1.1 分析
  • 1.2 代码
• 2. JZ31 栈的压入、弹出序列
• • 2.1 分析
  • 2.2 代码
• 3. 150. 逆波兰表达式求值
• • 3.1 分析
  • 3.2 代码

1. 155. 最小栈

在这里插入图片描述

1.1 分析

利用两个栈，一个栈a负责入数据和出数据，另一个_min负责放存入数据中目前最小的数。 如果_min中没有数据，那么a入数据的时候，它也入。但是_min里面放的是a中目前最小的数据，所以如果数据小于_min的top所放的数据时也插入。那么相等时候的的数据_min插不插入呢？

在这里插入图片描述

当然val和_min.top()数据相同时候也插入。因为再删除数据的时候，当a栈顶出栈的时候,_min栈顶同时也得出栈，这样才能保证_min.top()里面能够保存的是最小值。 所以pop得这样写：

题目要求返回最小值，那么就是返回_min.top()：

在这里插入图片描述

1.2 代码

2. JZ31 栈的压入、弹出序列

在这里插入图片描述

2.1 分析

这里用了两个栈，想要匹配出栈的顺序，最简单的方法就是： 先把入栈序列入栈，如果出现入栈序列和出栈序列的栈顶元素相同，那么两边就同时出数据，直到入栈序列和出栈序列的栈顶元素不匹配，或者出栈序列为空。 想要知道最后匹不匹配就直接判断一下入栈序列是否为空。为空就是已经匹配，否则就不匹配。

在这里插入图片描述

2.2 代码

3. 150. 逆波兰表达式求值

在这里插入图片描述

3.1 分析

逆波兰表达式就是后缀表达式，而我们一般用的是中缀表达式。 举个例子：把中缀表达式换成后缀表达式

在这里插入图片描述

用例1来分析一下：

在这里插入图片描述

在没有遇到第一个算符之前，就把数据入栈，当遇到运算符，就把它前面两个数2和1出，计算出来结果就是2+1=3，然后再把这个3再入栈；当再一次遇到表达式时候，又把它的前面两个数出栈做对应的运算之后，在把算出的结果入栈，最后输出栈顶元素就可以了。

在这里插入图片描述

在这里插入图片描述

3.2 代码

有问题请指出，大家一起进步！！!