栈的练习题
一、 逆波兰表达式求值
- 平时使用是算式是中缀表达式
- 逆波兰表达式是一种后缀表达式，算符写在后面。
优点：
1.去掉括号后表达式无歧义
2.适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
3.中缀转后缀：加上括号，将对应的运算符放在括号外
1.题目
2.思路
- 通过栈来实现，遍历数组，如果取得是运算符，从栈顶取两个元素参与运算，
- 如果不是运算符，就将元素压栈
3.解题步骤
- 1.new一个Integer类型的栈
- 2.遍历字符串数组，
- 3.写一个方法判断当前取的字符串是不是运算符
- 4.如果不是运算符，进行压栈
- 5.如果是运算符，就取出栈顶的两个元素，
- 6.根据运算符的类型，在 switch语句中运算，将结果压栈
- 7.最后栈中只有一个最终结果，取出并返回
4. 代码
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String x : tokens) {//遍历字符串数字
if (!isOperation(x)) {//判断当前字符串是不是运算法
stack.push(Integer.parseInt(x));//如果不是运算符，将字符串转化为Integer类型并压栈
} 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();//栈中只有一个结果
}
private boolean isOperation(String x) {
if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
return true;
}
return false;
}
二、括号匹配
1.题目
2.思路
1.左括号压栈，遇到匹配的右括号，对应的左括号出栈
2.如果左括号多，遍历完后，栈不为空，不匹配
3.如果右括号多，字符串遍历不完，栈就空了，不匹配
4.遍历完字符串，且栈是空的，说明符合条件
3.解题步骤
- 1.遍历字符串依次取出字符
- 2.如果是左括号，压栈，栈里面存的都是左括号
- 3.否则就是右括号，如果栈此时为空，证明右括号超出
- 4.栈不为空，查看栈顶元素是否与取的符号相匹配，如果匹配，出栈，不匹配返回false
- 5.最后直接返回栈是否为空的判断，栈为空说明所有括号都匹配成功，不为空证明左括号超出
4. 代码
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.isEmpty()) {//如果栈是空的
return false;//说明右括号多
}
char ch2 = stack.peek();//查看栈顶的左括号
if (ch2 == '[' && ch == ']' || ch2 == '{' && ch == '}' || ch2 == '(' && ch == ')') {
stack.pop();//如果左括号和右括号匹配，存的左括号出栈
}else {
return false;//不匹配
}
}
}
return stack.isEmpty();//如果栈是空的，返回true，否则返回false
}
三、出入栈顺序匹配
1.题目
2.思路
遍历数组，每次循环从push数组中向栈里压进一个元素，在pop数组中进行比较
如果相等，出栈，继续压进push数组的下一个元素
最后栈为空，说明数组中的顺序相匹配
3.解题步骤
- 1.给栈中压入一个元素
- 2.查看栈顶的元素是否等于popV数组中的值
- 3.加入循环的条件：j不能越界，避免越界异常,要pop元素,栈不能是空的,避免空指针异常
- 4.如果相等，出栈，j后移
- 5.不相等，没进入循环，i向后移动，在栈中重新压入新的元素与j匹配
- 6.最后数组遍历完后，栈为空说明符合题意
4. 代码
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder(int[] pushV, int[] popV) {
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().equals(popV[j])) {
//j< popV.length j不能越界，避免越界异常
// 要pop元素,栈不能是空的,避免空指针异常
//查看栈顶的元素是否等于popV数组中的值
stack.pop();//相等，出栈
j++;//j向后移动
}//不相等，没进入循环，i向后移动，在栈中重新压入新的元素与j匹配
}
return stack.isEmpty();
}
}
四、最小栈
1.题目
2.思路
1.用两个栈，在普通栈压进元素的时候，与最小栈的栈顶元素比较
2.如果小于最小栈的栈顶元素，将该元素压进最小栈，当做当前的最小值
3.如果栈中删除了最小的元素，最小栈同样移除，最小栈改变
3.解题步骤
- 1.push:给stack压进元素，同时判断如果最小栈为空，压进该元素，如果不为空，将该元素与最小栈的栈顶比较，小于等于的数放进最小栈
- 2.pop:在栈中取出元素时，要比较是否与最小栈的栈顶元素相等，如果相等，同时取出
- 3.top:当栈不为空的时候，返回栈顶元素
- 4.getMin：返回最小栈的栈顶元素；
4. 代码
class MinStack {
private Stack<Integer> stack;
private 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 {
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();
}
}
五、栈、虚拟机栈、栈帧的区别
- 栈是一种数据结构
- 函数在虚拟机栈上开辟内存
- 开辟的内存叫做栈帧
点击移步博客主页，欢迎光临~文章来源：https://www.toymoban.com/news/detail-719667.html
文章来源地址https://www.toymoban.com/news/detail-719667.html
到了这里，关于栈的OJ题（逆波兰表达式求值+括号匹配+出入栈顺序匹配+最小栈）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
