栈练习题(逆波兰表达式,有效括号,出入栈次序匹配,最小栈)

基础知识:

中缀表达式和后缀表达式(逆波兰式)

中缀表达式转后缀表达式

后缀表达式求结果

有效括号

栈的压入,弹出序列

最小元素栈

基础知识:

栈:是一种先入后出的数据结构,它的底层是由数组实现的

入栈:push(),出栈pop(),查看栈顶元素peek()

中缀表达式和后缀表达式(逆波兰式)

中缀表达式:我们日常所使用的加减乘除表达式
后缀表达式:计算器在计算的时候,是把我输入的中缀表达式转化成后缀表达式进行计算的

中缀表达式转后缀表达式

例:中缀表达式: a + b*c +(d*e+f)*g ,转换成后缀表达式

第一步: 从左向右先乘除后加减给中缀表达式加括号

第二步: 把每个运算符都移动到相对应的括号外面(每个运算符都有自己的括号)

后缀表达式求结果

例: 求123* + 45*6 + 7*的结果

解题方法:

遍历表达式,遇到数字就入栈,遇到运算符出栈俩个元素,栈顶元素作为右操作数,,第二个元素作为左操作数,求出运算结果,并把结果入到栈中,以此类推,遍历完表达式

用代码实现:

力扣剑指Offer 036

https://leetcode.cn/problems/8Zf90G/

代码

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for(int i = 0;i<tokens.length;i++){if(tokens[i].equals("+")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2+num1);continue;}if(tokens[i].equals("-")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2-num1);continue;}if(tokens[i].equals("*")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2*num1);continue;}if(tokens[i].equals("/")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2/num1);continue;}int ret = Integer.parseInt(tokens[i]);stack.push(ret);}return stack.peek();}
}

思路:就是刚刚上面求后缀表达式的思路

有效括号

力扣: https://leetcode.cn/problems/valid-parentheses/submissions/

思路:

创建一个栈,遍历给定字符串,当为左括号就入栈,当为右括号时先看栈是否为空,如果为空返回false,如果不为空,判断这俩个左右括号是否匹配,如果匹配就让这个栈顶元素出栈,依次类推,遍历整个字符串....遍历完成之后,判断栈是否为空,如果不为空(说明左括号多了),返回false,如果为空,则所有的括号都匹配上了返回 true

代码

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack();for(int i = 0;i<s.length();i++){if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){stack.push(s.charAt(i));}else{if(stack.isEmpty())return false;char ret = stack.peek();if(ret=='('){if(s.charAt(i) == ')'){stack.pop();continue;}else{return false;}}if(ret=='['){if(s.charAt(i) == ']'){stack.pop();continue;}else{return false;}}if(ret=='{'){if(s.charAt(i) == '}'){stack.pop();continue;}else{return false;}}}}if(stack.isEmpty()){return true;}return false;}
}

栈的压入,弹出序列

https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/description/

思路:创建一个栈,遍历压入序列初始下标为i,把压入数组一个一个压入到栈中,判断这个数是否和弹出序列数组(初始下标为j).,是否相等,如果相等就弹出栈顶元素,j++,继续判断新的栈顶元素和新的弹出序列数组[j]是否相等,相等同样弹出栈顶元素,依次类推....遍历结束后判断栈中是否还有元素,如果有说明不可行,返回false,如果栈为空,则返回true

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack();int j = 0;for(int i = 0;i<pushed.length;i++){stack.push(pushed[i]);while(j<pushed.length && !stack.isEmpty() && stack.peek()==popped[j]){stack.pop();j++;}}if(stack.isEmpty()){return true;}return false;}
}

最小元素栈

设计一个push,pop,peek()操作,并能在常数时间类检索到最小元素的栈

创建俩个栈,一个是普通栈,一个是最小栈

push操作:先把元素入到普通栈,再判断最小栈是否为空,如果为空就入栈,然后再判断入栈的元素和最小栈的栈顶元素的大小,如果入栈的元素小于或等于最小栈的栈顶元素,就把这个元素也入到最小栈,此时最小栈里面放的元素一定都是最小值

pop操作,弹出普通栈的栈顶元素,再判断弹出的这个元素是否是最小栈的栈顶元素,如果是就把最小栈的栈顶元素也弹出

top操作,栈顶元素,也就是普通栈的栈顶元素

getMin操作,得到最小值,,,,最小栈的栈顶元素就是最小值

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.isEmpty()){minStack.push(val);return;}if(val<=minStack.peek()){minStack.push(val);}}public void pop() {if(stack.peek().equals(minStack.peek())){minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}