玩具网站模板,方象科技服务案例,网络舆情监测 toom,wordpress模版侵权目录 前言#xff1a;
1.进栈过程中可以出栈的选择题
2.将递归转化为循环
3.逆波兰表达式求值
4.有效的括号
5. 栈的压入、弹出序列
6. 最小栈 前言#xff1a;
数据结构想要学的好#xff0c;刷题少不了#xff0c;我们不仅要多刷题#xff0c;还要刷好题#x…目录 前言
1.进栈过程中可以出栈的选择题
2.将递归转化为循环
3.逆波兰表达式求值
4.有效的括号
5. 栈的压入、弹出序列
6. 最小栈 前言
数据结构想要学的好刷题少不了我们不仅要多刷题还要刷好题为此我开启了一个必做好题锦集的系列此为第一篇选择题篇该系列会不定期更新敬请期待
栈Stack的详解_WHabcwu的博客-CSDN博客 1.进栈过程中可以出栈的选择题 1. 若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 A选项进出入栈顺序 push(1)-pop() 出1 push(2)-push(3)-push(4)-pop() 出4; pop() 出3; pop() 出2; B C D步骤相同通过分析可知C明显错误 选C 2.将递归转化为循环 比如逆序打印链表 使用栈的方法解决 public void printfList(Node head) {if (head null) {return;}Node curhead;StackNode stack new Stack();while (cur!null){stack.push(cur);curcur.next;}while(!stack.empty()){System.out.println(stack.pop().val);}} 3.逆波兰表达式求值 逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/ 要想彻底的掌握这道题必先清楚的理解后缀表达式 总结 1遍历数字依此压栈 2遇到 - * / 就出栈2数第一次出栈的数做为右操作数 第二次出栈的数做为左操作数 3再把2运算的数压栈 4重复123 故代码
class Solution {public int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String x : tokens) {if (!isoperation(x)) {stack.push(Integer.parseInt(x));} else {int x1 stack.pop();int x2 stack.pop();switch (x) {case :stack.push(x2 x1);break;case -:stack.push(x2 - x1);break;case *:stack.push(x2 * x1);break;case /:stack.push(x2 / x1);break;}}}return stack.pop();}public boolean isoperation(String x) {if (x.equals() || x.equals(-) || x.equals(*) || x.equals(/)) {return true;}return false;}
} 4.有效的括号 有效的括号https://leetcode.cn/problems/valid-parentheses/ class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char xs.charAt(i);if(x(||x{||x[){stack.push(x);}else{if(stack.empty()){return false;}char ystack.peek();if(y(x)||y{x}||y[x]){stack.pop();}else{return false;}}}if(!stack.empty()){return false;}return true;}} 解析 1遍历给定的字符串由于后遇到的左括号要先闭合因此我们可以将这个左括号放入栈顶。 2当我们遇到一个右括号时我们可以取出栈顶的左括号并判断它们是否是相同类型的括号栈为空返回flase,不为空但不是相同的类型也返回 false。 (3)在遍历结束后如果栈中没有左括号,返回 false。 5. 栈的压入、弹出序列 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型一维数组 * param popV int整型一维数组 * return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {StackInteger stack new Stack();int j0;for (int i 0; i pushV.length; i) {stack.push(pushV[i]);while(jpopV.length!stack.empty()stack.peek().equals(popV[j])){stack.pop();j;}}return stack.empty();}
}
解析 6. 最小栈 最小栈https://leetcode.cn/problems/min-stack/ import java.util.Stack;public class MinStack {private StackInteger stack;private StackInteger minstack;public MinStack() {this.stack new Stack();this.minstack new Stack();}public void push(int val) {stack.push(val);if (minstack.empty()) {minstack.push(val);} else {if (minstack.peek() val) {minstack.push(val);}}}public void pop() {if(!stack.empty()){int x stack.pop();if (x minstack.peek()) {minstack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minstack.peek();}
} 解析
辅助栈法
(1)一个用来正常存放数据-stack
(1)一个用来存放最小数据-minstack private StackInteger stack; private StackInteger minstack; push
stack无差别入栈,对于minstack进行判断若为空直接入栈若不为空则需要与栈顶元素进行比较若小于等于则入栈。
其余过于简单无需多讲。 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
